Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
581
questions
0
votes
3
answers
79
views
Compute a commutative and associative operation on n-2 arguments efficiently
Considering a function $f$ such that:
$$ f(x_1, x_2, x_3) = f(f(x_1, x_2), x_3) = f(x_1, f(x_2, x_3)) $$
and
$$ f(x_1, x_2) = f(x_2, x_1) $$
and a set $X = \{ x_1, \dots, x_n \}$; how to compute
$$f(...
- 103
-1
votes
1
answer
46
views
Complexity of T(n)=2T(n-1)
I built a recursion tree like this:
0
/ \
0 0
/\ /\
... ...
So the tree has height n, and width $2^n$.
But if the sum of all levels is $\sum_{i=0}^{n}...
- 1
0
votes
1
answer
76
views
Show that the function that counts the number of occurrences of 6 in a natural number is recursive primitive
I have to show that given $f:\mathbb{N}\rightarrow\mathbb{N}$ the function that returns the number of times $6$ appears in the input (for example $f(436546)=2$) is primitive recursive.
The exercise ...
- 11
0
votes
1
answer
41
views
Does a closed formula exist for each recurrent formula?
I'm interested in a question that probably lies close to the very concept of recursion. I have no idea whether my statement is true or false, neither I have tools to check it, so I'll just ask the ...
- 13
1
vote
2
answers
71
views
Why is a recurrence of $2N_{h-2}$ equal to $2^{h/2}$?
I was watching video 7. Binary Trees, Part 2: AVL, where professor Erik Demaine stated that $$2N_{h-2} = 2^{h/2\text{ (or maybe with floor or something... maybe it's ceiling)}}$$ where $N$ stands for ...
1
vote
1
answer
188
views
A recursive relation for the number of well formed nested parentheses of length $n$ and depth $\leq d$
Consider a function $C(n, d)$ which counts the number of well formed, i.e, balanced, parenthetical 'words' of length $n$ and maximal nested depth $\leq d$.
That is, $(())$ has $n = 4, d = 2$. $()((())(...
- 11
1
vote
1
answer
127
views
Am I drawing the recursion trees correctly?
I guess I've already figured out what is a recursion tree and how to construct one. Inspired by Figure 2.5 of "Introduction to Algorithms, 3rd Edition by CLRS", I drew some recursion trees ...
- 588
0
votes
1
answer
59
views
Recursive function - proof by induction
Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists.
I've encountered the following function:
$f([])=[]$ (empty list)
$f([x])=[x]$, for $x \in \Sigma$
$f(x:L)=f(L)$, for $x \in \Sigma$ and $...
- 1
2
votes
1
answer
82
views
Trying to understand the basic about recurrence trees
I have little background on recurrence trees, and I am working on the following exercise:
Exercise. Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we ...
- 189
1
vote
3
answers
271
views
Recursive algorithm for adding numbers from 1 to n with O(1) time complexity
So I have a recursive algorithm which sums up the numbers from 1 to n plus one (hence the return 1):
...
- 13
0
votes
0
answers
33
views
Prove that a predicate is not computable
Prove that the following predicate is not computable:
$P_e(n) =
\begin{cases}
1 & \textrm{if } \phi_n(n) = e \\
0 & \textrm{otherwise}
\end{cases}$
Could someone explain how to approach ...
1
vote
0
answers
81
views
Recursive algorithm running time?
I would like your opinion on how to detect the T(n) (Running Time) for the following recursive algorithm.
Charm is an algorithm for discovering frequent closed itemsets in a transaction database. A ...
0
votes
1
answer
26
views
Termination condition for max of array using divide and conuqer approach
I want termination proof of divide and conquer approach to find max of array,I want equational proof in form of lemma.Below is my attempt.I have got accepted everything in dafny ,it is only pointing ...
user139614
-3
votes
1
answer
93
views
Recursion problem T(n)=3T(n/3)+3n
I just need help solving this problem. I know I'm supposed to be using the Master's Theorem but I don't know where to start
0
votes
1
answer
315
views
Time complexity of merging two lists while preserving order
I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
- 9
0
votes
0
answers
47
views
What is the standard definition of recursive automata (or state machines)?
I found this paper:
https://courses.engr.illinois.edu/cs373/fa2009/recaut.pdf
But it looks like recursion is done along an edge. I would have thought you have state machines nested inside nodes. ...
- 495
3
votes
1
answer
304
views
Skyline problem with triangular buildings
This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites.
The following are two variations from the usual Skyline problem:
Report ...
- 289
1
vote
1
answer
402
views
Tower of Hanoi variation - Split into two towers of odd and even disks
Suppose we have three rods A, B and C, and rod A ...
- 119
0
votes
0
answers
26
views
recursive function without intermediate variables
The question was to convert this recursive code with intermediate variables to a functional program code without any intermediate variables.
...
0
votes
0
answers
27
views
Simple examples of Recursive Enumerable Functions
My understanding of Recursively Enumerable Functions is that they're recursive functions, but for some values of the arguments you put into the function they will stop and give an answer, and for ...
7
votes
2
answers
3k
views
Is the Berkeley tutorial on Fibonacci trees using wrong figures?
I'm confused about the figures in a Berkeley tutorial on Fibonacci trees, which depicts fibtree(2) as
and fibtree(3) as
I thought fibtree(3) looks like the following
(the figure is adapted from ...
- 588
0
votes
1
answer
208
views
Implementing a correct `let rec in` interpreter in Haskell with `eval` and `sub` semantics
I'm implementing the toy fb-lang from the principles of programming language book. It's a small interpreted language that uses eval(uate) expression function and <...
- 109
0
votes
0
answers
23
views
Unusual approach to tabulation algorithm
Consider simple tabulation algorithm firstly for Fibonacci numbers.
We will use the dictionary as a cache (and Python as example PL):
...
- 111
13
votes
4
answers
4k
views
Why is tail recursion better than regular recursion?
There is the axiom you should always prefer tail-recursion over regular recursion whenever possible. (I'm not considering tabulation as an alternative in this question).
I understand the idea by why ...
- 251
0
votes
0
answers
176
views
Space complexity for divide-and-conquer
Here's a simple question but I'm not sure there is a simple answer. This came up in an undergraduate algorithms class.
Consider the following divide-and-conquer algorithm $A$ (here, $x_1, \ldots, x_n$ ...
- 101
1
vote
1
answer
82
views
Solve recurrence where the base case's time complexity is a function of the original input size
I'm trying to analyse the time complexity of the following algorithm for generating the power set:
...
- 123
0
votes
1
answer
55
views
How to count the leaves of a tree without a outside function counter?
I got bombed in a interview because I was asked to write an algorithm which would count the leaves of a tree, I did this:
...
- 251
-1
votes
1
answer
111
views
Finding the number of ways to reach a particular position in a grid from a starting position (given some cells which are blocked)
I came across this question in a job interview and I couldn't solve it.
In a n*m matrix some cells are blocked.The robot can only move in direction of (x-1,y+2) or <...
0
votes
1
answer
93
views
How can we get upper bound in terms of Big Oh notation using Master theorem?
The recursion is:
T(n) = 5T(n/2) + O(n)
I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
- 138
0
votes
1
answer
73
views
How does primitive recursion handle mutual recursion?
My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this.
Is this true?
Thanks, friends :)
- 23
0
votes
1
answer
36
views
Recursive Bijections Between Countably Infinite Sets
The textbook I am currently studying (Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers ...
0
votes
1
answer
316
views
Is top-down dynamic programming always recursive?
I think top-down dynamic programming is mostly recursive (at least when we use memoization). For instance, solving the rod-cutting problem by this algorithm:
...
- 411
1
vote
1
answer
110
views
Making use of one function to recursively find n/3 of another
Given an algorithm M that computes the median of an array A in O(n) time, describe an O(n) algorithm to repeatedly call M in order to find the element of rank n/3 in A.
This is a problem I am tasked ...
- 21
2
votes
1
answer
213
views
Are recursion and a stack equivalent in terms of inplementing DFS?
It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem:
...
- 1,081
0
votes
0
answers
56
views
is there a theory consider on infinitely many recursion?
of course there is a theory that how many recursive calling the same system to solve problems, this theory is "recursion theory", If i know correctly.
and recursion theory is computability ...
- 23
1
vote
1
answer
258
views
How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?
I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these ...
- 111
0
votes
1
answer
195
views
Recursive Prefix-Sums K times
I have been wondering about the following question for quite some time:
You are given an array $x$. Define f(x) as the prefix sums of this array.
For example, f([1,0,1]) = [1,1,2] and f(f([1,0,1])) = [...
- 234
0
votes
1
answer
210
views
Tic-Tac-Toe in PSPACE
Why is a game like Tic-Tac-Toe in PSPACE? For example for a nxn grid you have nxn! possible game tree paths (duplicates and illegal moves aside), then don't you need (n^2)! memory slots?
- 19
2
votes
0
answers
61
views
What are the fixed-points of the Y combinator?
Since the Y combinator itself is a function (albeit a higher-order one), I was wondering what the fixed-points of Y itself are.
- 121
0
votes
1
answer
321
views
Multiplying two integers by dividing each into 3 parts
Integer Multiplication: $x$ and $y$ are two n-bit integers, where $n=3^k$ for some $k>0$. We break $x$ into three parts $a$, $b$, $c$, each with $n/3$ bits; and $y$ into three parts $d$, $e$, $f$, ...
- 101
0
votes
1
answer
176
views
Question on Erickson 'momselect' algorithm
In the Erickson Algorithms textbook (file:///C:/Users/G068078/OneDrive%20-%20Kaiser%20Permanente/Algorithms_Technique_and_Theory_CS_388G/Undergraduate_CS331/Algorithms-JeffE.pdf)
it has pseudocode for ...
1
vote
0
answers
92
views
2
votes
1
answer
82
views
Calculate the number of "count inversions" of sub arrays
Recently, I encountered the following problem:
Given an array $A$ of length $n$ $(0\le n\le 2^{17})$. Let $f(l, r, x)$ denotes the number of occurrences of $x$ in the subarray $a[l\ldots r]$. Find ...
0
votes
0
answers
339
views
Total work done at a recursion tree level
In the proof of Master theorem in Dasgupta's Algorithms the author says that the total work done at a recursion tree level is
$$a^k \times O\left(\frac{n}{b^k}\right)^d$$
where $a$ is the branching ...
- 123
-3
votes
2
answers
46
views
Solve $\sum_{i=0}^{\log_3 n-1}i\times 3^i$
I want to find the answer for $$\sum_{i=0}^{\log_3 n-1}i\times 3^i$$
Can you please explain?
I this a geometric series?
0
votes
2
answers
97
views
Are the definitions of loop in CS and in programming (standard/common) identical?
Are the definitions of loop in CS and in programming (standard/common) identical?
If not, what is the main difference / what are the main differences?
1
vote
2
answers
272
views
Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?
Why is there no algebraic definition of algorithm besides recursive functions?
If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link?
...
- 495
0
votes
0
answers
43
views
Recursive approach of longest common subsequence
I tried to solve Longest common subsequence problem using recursion, however as I later discovered, my thinking approach was wrong.
I took 2 strings say s1 and s2 with lengths l1 and l2, s1="...
- 1
1
vote
1
answer
50
views
How to perform AND on binary "recursive repeating sequences"?
Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related ...
- 71
1
vote
1
answer
45
views
Induction on recursive formula
I have this recursive formula
$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)$$
$$T\...
- 231