Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
374
questions
0
votes
0answers
22 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)$, ...
0
votes
0answers
18 views
File Systems (Operating Systems)
The figure below depicts the structure of a simple inode-based file system. Each rectangle represents a disk block of some fixed block size.
In respect to this diagram, I am asked:
(a): Does this ...
1
vote
0answers
23 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
26 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
17 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
28 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
45 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
46 views
Removing recursion from a function with multiple params
I am given the following function as a brain teaser:
...
1
vote
0answers
18 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
44 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
17 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
32 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
12 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
129 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
37 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
77 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
81 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
106 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
75 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?
1
vote
1answer
21 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
27 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 ...
-2
votes
1answer
30 views
3
votes
1answer
50 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
41 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
46 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
84 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
73 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
51 views
Iteration vs Recursion question in Lisp method
I am curious if the following method would be called iterative or recursive:
...
2
votes
1answer
30 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
85 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:
...
0
votes
1answer
73 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?:
...
2
votes
2answers
43 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
2answers
90 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
1answer
169 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
...
1
vote
1answer
79 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, ...
1
vote
1answer
84 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 ...
1
vote
0answers
37 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
2answers
143 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 ...
2
votes
1answer
56 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.
...
2
votes
1answer
39 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 ...
2
votes
1answer
55 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(...
2
votes
1answer
49 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!
2
votes
1answer
40 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) ?
0
votes
1answer
48 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 (...
0
votes
1answer
64 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 ...
0
votes
0answers
82 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
...
1
vote
1answer
89 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".
...
0
votes
0answers
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*}$$
6
votes
1answer
321 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 ...
