Questions tagged [recursion]

Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.

Filter by
Sorted by
Tagged with
0
votes
0answers
21 views

Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem

I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, ...
2
votes
1answer
56 views

Min-coin change problem with limited coins

I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite ...
1
vote
0answers
39 views

Find the fixed point of a recursive functional?

A functional is a function which takes another function as a parameter. The fixed point of a function is an input such that F(x) = x Given an example ...
-1
votes
0answers
15 views

Is there a direct formula to calculate the number of levels of recursion for a merge sort

I'm new to this area and still learning. Is there a direct formula to calculate the total number of recursion steps necessary for a merge sort of size n rather than ...
-1
votes
1answer
37 views

Recursive set for a string

Given the definition: ...
-1
votes
0answers
48 views

Time Complexity of an recursive Algorithm

Goodmorning, I have to analyze the time complexity of this algorithm: Pseudocode: ...
0
votes
1answer
66 views

Explanation of O(n2^n) time complexity for powerset generation

I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward: ...
0
votes
1answer
31 views

Cover interval with minimum sum intervals - DP recursion depth problem

READ ME FIRST: I have just found the official solutions online (have been looking for them for a while, but after posting this I quickly found it), and I'm currently trying to understand it. As I can ...
2
votes
1answer
30 views

Recurrence Relations

I am starting to learn recurrence relations in class and I am having issue with this example: T(N) = 2N - 1 + T(N-1) I am bit confused as to get the base case. I'm sorry if this seems elementary, ...
0
votes
0answers
51 views

How to show that a partial function is recursive?

I try to prove that this function is recursive: $$f(x_1,x_2)= \begin{cases} 2x_1-x_2 & \text{if $x_1 \geqslant \sqrt{x_2}$} \newline \bot & \text{otherwise} \end{cases}$$ I think that I need ...
0
votes
1answer
22 views

Converting a function with single parameter to a function with multiple parameters

I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows: Given a string or a list, do an aggregation operation on each of its elements. Here ...
1
vote
1answer
78 views

How to show that a $\log_2(x)$ is a recursive function?

I have a problem for the comprehension of how to prove that a function $ \log_2 : \mathbb{N} \rightarrow \mathbb{N}$ defined as: $$\log_2 (x)= \begin{cases} y & \text{if $x=2^y$} \newline \bot &...
2
votes
2answers
68 views

Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)

Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the ...
2
votes
1answer
152 views

Count total number of k length paths in a tree

This is a question from a competitive programming competition. Given a tree with n nodes and a number k, find the total number of paths of length k in that tree. I know for a fact that a solution can ...
3
votes
2answers
139 views

Thought process to solve tree based Dynamic Programming problems

I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
1
vote
0answers
18 views

How to compute the general term formula for the number of full binary tree heaps that can be formed with distinct elements?

The number of possible heaps that are full binary trees of height $h$ and can be formed with ($n = 2^h - 1$) distinct elements can be computed by recursion: $$ a_h = {2^h - 2 \choose 2^{h - 1} - 1} a_{...
1
vote
1answer
29 views

Pseudo code of recursive method of printing all permutations of $n$ given integers

I really don't understand this pseudo code. The function prints all permutations of $n$ given integers, assuming that all numbers are different. Is there a way to explain this code more easily as I ...
3
votes
1answer
118 views

Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems

I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences. The first problem I solved was longest palindromic substring ...
3
votes
1answer
72 views

Find a threshold such that one function is always bigger than the other

Given the recursively defined function $c$: $$c(m,n)=\begin{cases}0&\text{for }m=0\\ n^2+n+1&\text{for }m = 1\text{ and }n\ge 0\\ c(m-1, 1)&\text{for }m>1\text{ and }n=0\\ c(m-1,c(m,n-...
2
votes
1answer
66 views

Deriving recursive definition from function specification

Given this function specification, where name xs is bound to a list, # denotes its cardinality and ...
1
vote
0answers
48 views

Egg dropping problem binomial coefficient recursive solution

I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors) In the binomial coefficient solution we construct a function $f(x,n)$, ...
1
vote
0answers
28 views

Finding the closed form of this recurrence

We have the following recurrence $T$: $$ T(n,k) = \left\{ \begin{array}{ll} \alpha n^2 + \beta n + \delta & \quad \text{if }\; n \le k \\ T(\lceil n / 2 \rceil, k)...
1
vote
0answers
32 views

Hanoi towers recursive expression for EVERY algorithm

What the recursive algorithm for moving $n$ disks says, is: If $n > 1$, move $n-1$ discs from A to B. Move the $n$th disk from A to C. If $n > 1$, move $n-1$ discs from B to C. Let $T_n$ be ...
0
votes
1answer
19 views

Recursive Call Inside Argument List (C++) [closed]

So, my professor asked me to implement recursion in different ways to compute $a^n$ (a and n being integers) and rank them according to their space efficiency. Now, here is one of the methods I came ...
0
votes
0answers
47 views

Can every problem that uses recursion be solved using iteration? [duplicate]

We all know iterations and recursions are a powerful thing in programming. But this doubt always troubles me whenever I write an iteration or recursion. Can every recursive problem solved using ...
-4
votes
1answer
67 views

How to find the substitutions that convert the starting sequence into the final sequence? CCC19J5

Here is Canadian Computing Competition 2019 Junior problem 5 on dmoj.ca. You can also see the original problem at cemc.uwaterloo.ca as well. A substitution rule describes how to take a sequence of ...
1
vote
1answer
48 views

Removing recursion from a function with multiple params

I am given the following function as a brain teaser: ...
2
votes
0answers
66 views

Least constraining value heuristic in Sudoku [closed]

I was trying to implement Least Constraining Value Heuristic in Sudoku but wasn't getting the idea on how to do it. Can someone share their idea for the same ?
1
vote
0answers
54 views

How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?

I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$. $V(j, k) = \begin{cases} tj & k \leq 2 \\...
1
vote
2answers
55 views

How can I show h(n) = O( √ n)?

Is there any way to make recursion tree that satisfies the height $h(n) = h(n−\sqrt{n}) + 1$ to show $h(n) = O(\sqrt{n})$?
1
vote
1answer
21 views

Does a recursive call reset to the beginning of the method if the call is in the middle?

Or does it finish the method? Sorry for noob question.
2
votes
1answer
33 views

How does this recursive algorithm work?

One question from the Grokking Algorithms book: Implement a max([]int) function, returning the biggest element in the array. Here's my solution in Golang (adapted ...
0
votes
0answers
14 views

Manage nested recursions in the design of a concatenative language interpreter

I'm in the designing of an interpreter for a stack based concatenative language, and I'm currently stuck with a problem about recursion of some of my concatenative program to calculate factorial: <...
1
vote
1answer
842 views

Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation

I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same ...
1
vote
2answers
49 views

What is an example of a (simple) tail recursive algorithm that doesn't use a helper function?

I know one can compute things using tail recursion with helper functions like: ...
2
votes
2answers
175 views

Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$

So far we have learned Recursion Tree, Substitution Method, and Master's Theorem. I'm not sure how we can find lower AND upper bounds. I know that using Master's Theorem, we get $T(n) = \Theta(n^4)$, ...
3
votes
1answer
106 views

Solve recurrence relation that depends on depth of recursion

The specific problem I'm working on is the puzzle presented in this video. For those who don't want to watch the video, my summary of the puzzle is: A frog is sitting on the edge of a pond facing ...
3
votes
1answer
111 views

Distinct Binary Heaps

I have $n$ elements out of $n-1$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it. My analysis : I started ...
1
vote
3answers
79 views

How can any non-primitive-recursive function like the Ackermann function be implemented on hardware?

If for-loops and function calls both boil down to jump instructions when implemented on a real machine, then how is "The Ackermann function isn't implementable with for-loops" a meaningful phrase?
2
votes
2answers
40 views

Complexity of iterative exponentiation

I've watched multiple videos and read articles about recursion but I'm still confused. I've got this problem here but I'm unsure how to answer it: The following function calculates $x^n$ ...
0
votes
0answers
29 views

Is it still called “recursion” when you're using call-stack as a stack?

The most obvious way to solve a problem of balancing parentheses, like https://leetcode.com/problems/valid-parentheses/, is through a stack (a last-in-first-out (LIFO) datastructure). However, if you ...
3
votes
1answer
52 views

Is this lambda abstraction created as a generator of a recursive function?

In lambda calculus, a recursive function $f$ is obtained by $$ f = Y g $$ where $Y$ is the Y combinator and $g$ is the generator of $f$ i.e. $f$ is a fixed point of $g$ i.e. $f == g f$. In The ...
1
vote
0answers
50 views

Transforming an immutable binary tree without recursion [closed]

I'm struggling on this one. I have a Binary Decision Diagram, which is pretty much tree-like. Each node has a hi and lo node. I need to recurse into the tree, and if some conditions are the case ...
1
vote
1answer
81 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
3
votes
2answers
87 views

Is there any recursive function f whose code is unique?

I am doing some reviewing for the term final on computability and found out this simple exercise. I am very fresh on theoretical computer science so if you do have an answer please make it simple. ...
1
vote
0answers
128 views

How to approach backtracking when using immutable types (Python)? [closed]

In Python when we are building a recursive algorithm that uses backtracking a mutable type such as a list is great to use. It can be modified at each call in our recursion tree, then returned back to ...
0
votes
2answers
66 views

Iteration vs Recursion question in Lisp method

I am curious if the following method would be called iterative or recursive: ...
2
votes
1answer
41 views

Turing Machine equivalence in MinTM proof

The proof with contradiction that $MIN_{\mathrm{TM}}$ is not Turing-recognizable from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows: $C=$ "On ...
1
vote
1answer
131 views

How to find the Big-O for finding combinations of balanced parentheses?

Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be: ...

1
2 3 4 5
8