Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
561
questions
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.
- 11
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 ...
- 93
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?
- 147
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$ ...
- 21
-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 ...
- 111
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.
...
- 51
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 ...
- 29
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 ...
- 21
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
Assigning $m$ balls to $n$ buckets - recursive algorithm
I came across the following problem and the answer to that problem:
Given $m$ balls and $n$ bins, find out how many ways to assign the balls to the bins. Notice the bins have no order: for example, $(...
- 11
1
vote
1
answer
784
views
Given price and number of pages of each book, What is the maximum number of pages you can buy?
You are in a book shop which sells n different books. You know the price and number of pages of each book.
You have decided that the total price of your purchases will be at most x. What is the ...
- 147
1
vote
0
answers
55
views
How to solve 2 variable recursion?
T(m,n) = T(m-1,n) + T(floor(m/2), n-1)
Base conditions
T(m,n) = 1 when n = 0
T(m,n) = 0 when m < n
Edited: Below is the code for which I want to know the time complexity in terms of m and n.
<...
0
votes
2
answers
547
views
What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$
I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this ...
- 115
2
votes
1
answer
81
views
Number of Function Calls In Recursive Code
I am new to recursion. I am doing some practice questions and I was wondering what the technique is for going from some recursive code to identifying the number of function calls it makes.
...
- 21
2
votes
1
answer
73
views
Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial
This question is about section 2.3 of Wilf's ``Algorithms and Complexity''
https://www.math.upenn.edu/~wilf/AlgoComp.pdf
in which he analyses the complexity of a recursive computation of the ...
- 278
2
votes
1
answer
116
views
What is the closed-form expression for $T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1$ where $T_1 = 1 ?$ [closed]
Problem:
Find the closed-form expression for$$
T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1
\tag{1}
$$where $T_1 = 1 .$
Calculating this sum I came up with the following result:
$$
T_n = 8^{\left(...
- 23
2
votes
1
answer
146
views
Is there purely recursive functions? [duplicate]
Is there any problem that can be only solved with recursion, and not with iteration? (haven't been able to find anything online).
If there isn't any, is there a reason why?
Thanks in advance!
- 23
2
votes
1
answer
120
views
Computability: Proving a predicate is not recursively enumerable
Let P(p) <=> for each x, comp(p,x) is defined.
Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
- 51
0
votes
1
answer
107
views
Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm
I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1} = app \quad \& \quad r(j) \leq p $ and (...
- 159
1
vote
1
answer
932
views
Recursive definition for the length of a string?
I found a couple of answers online but I don't quite understand why the answer is right:
The length of a string is:
If a string has no characters, then its length is 0.
Otherwise, the length of the ...
- 165
0
votes
0
answers
165
views
Write the Brute Force Recursive Code to generate the longest substring containing k distinct vowels
Given a string s we have to find the length of the longest substring of s which contain exactly K distinct vowels.
This is the problem statment given on geeksforgeeks
Input : s = “artyebui”, k = 2
...
- 101
1
vote
1
answer
288
views
Avoiding "side effects" in recursive functions
I am writing a function to find the intersection between two sets.
The non-functional requirements of the assignment include avoiding "side effects".
...
- 113
0
votes
0
answers
13
views
T(n) = T(n-1) +3n^2 - 2n +1 [duplicate]
I was wondering how do I solve this, I've been trying any possible way to but I've failed:
$$\begin{align*} T(n) &= T(n-1) +3n^2 - 2n +1 ,& n \ge 1 \\
T(0) &=2 &\\
\end{align*}$$
8
votes
1
answer
3k
views
Worst-case input for median-of-medians with groups of size 3
Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a ...
- 4,391
0
votes
2
answers
1k
views
prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves
I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction
*Edit: my professor had a significant typo in this assignment, I have attempted ...
- 185
0
votes
0
answers
40
views
Is the time complexity of this function O(n^3)? And O(n) for its memoized solution?
Given this naive recursive function:
...
- 101
1
vote
0
answers
131
views
Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?
McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960).
...
- 133
3
votes
1
answer
894
views
Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive
I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous.
I couldn't make up my mind on this statement. How can a grammar which is both ...
- 321
2
votes
1
answer
761
views
Can memoization be applied to any recursive algorithm?
I am new to the concepts of recursion, backtracking and dynamic programming.
I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there ...
- 131
0
votes
0
answers
352
views
Dynamic Programming solution for finding shortest distance to travel between points
So consider a person located at point $c$ (let's say $c=140$). Given a set of other points, for example, $P = \{100, 50, 190\}$. The cost of traveling to a point $P_i$ is then $|c-P_i|$. Points can be ...
- 27
0
votes
1
answer
519
views
Recursively edit 2-D array using backtracking
I have a 2-D array which contain 3 types of elements:
C (Contaminant)
R (Rock)
W (Water)
The rule is that:
contaminant can seep through water but not through rocks.
Let's say I have the ...
- 111
2
votes
2
answers
511
views
Recursion to DP Solution
There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll ...
user100141
2
votes
1
answer
37
views
Maximum Expected Fishing Day (Recurrence Relation)
John joined a meetup where organize day long fishing trip once a
month. The organizers are vary poor at planning, so will organize
fishing on a random day of the month without any advance notice.
...
- 91
8
votes
4
answers
428
views
What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?
We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
- 203
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
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