# Questions tagged [recursion]

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

561 questions
Filter by
Sorted by
Tagged with
1 vote
1 answer
38 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
1 answer
51 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 ...
2 votes
1 answer
11k 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 ...
• 153
1 vote
2 answers
167 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,960
2 votes
2 answers
865 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)$, ...
• 21
3 votes
1 answer
394 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 the ...
• 31
3 votes
1 answer
191 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
3 answers
156 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
2 answers
71 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$ ...
-2 votes
1 answer
239 views

...
3 votes
1 answer
75 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 ...
• 4,775
1 vote
0 answers
149 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 ...
0 votes
2 answers
404 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
2 answers
113 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
0 answers
294 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 ...
• 11
0 votes
2 answers
218 views

### Iteration vs Recursion question in Lisp method

I am curious if the following method would be called iterative or recursive: ...
2 votes
1 answer
163 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 ...
• 71
1 vote
1 answer
578 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: ...
• 153
1 vote
1 answer
705 views

### Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum

count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum. This is my recursive algorithm, what is wrong here?: ...
• 147
2 votes
2 answers
129 views

### How to use Master Theorem with strange format of $b$ parameter?

I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as: $$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$ How can I apply the Master Theorem to ...
2 votes
2 answers
117 views

### Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
2 votes
1 answer
242 views

### Are all foldable data structures also recursive?

I was checking what Wikipedia has to say on reduce. It says: In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order ...
• 133
1 vote
1 answer
229 views

2 votes
1 answer
130 views

### Is there a relation between the size of the domain/range of a function and its computability?

This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately. I think there is no relation with the range as the range of the ...
0 votes
1 answer
85 views

### Recursive factorial algorithm

I'm struggling to understand this factorial algorithm. ...
0 votes
2 answers
961 views

### Merge sort and quicksort recursion tree depth

1) I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about ...
• 101