Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
557
questions
0
votes
0
answers
23
views
Does a bijective function exists behind every recurrence relation?
Consider these 2 questions where recurrence relations can be applied:
Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes ...
0
votes
0
answers
25
views
How to solve recurrences of this type?
$T(n) = 2 T(\lceil \frac{2n}{3} \rceil) + T(\lceil \frac{n}{3} \rceil) + O(n log n)$
From the 3-ary recurrence tree, one can say that $T(n) \geq cnlog^{2}n$ for some constant c, using the shortest ...
- 1
0
votes
0
answers
33
views
Is recursiveness always from bottom to top?
Lets assume dir a has dir b which has dir c.
In a recursive deletion of these directories we ...
0
votes
1
answer
43
views
Complexity of recursive function that calls itself with it's own return value
Given the following code:
int f3(int n)
{
if(n <= 2) return 1;
f3(1 + f3(n-2));
return n - 1;
}
I was trying to find the time complexity and I got this ...
1
vote
0
answers
89
views
How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [closed]
We define the set S as $\{(s_1, f_1), (s_2, f_2), ..., (s_i, f_i)\}$, where each $f_i$ is the frequency that $s_i$ is repeated in the multiset T. How many ways can we partition the multiset T into ...
0
votes
2
answers
38
views
Types and programming languages: strange term construction?
Pierce's Types and Programming Languages has the following definition of terms:
$$S_0=\emptyset$$
$$S_{i+1} = \{true,false,0\} \cup \{succ(t), pred(t),iszero(t)|t \in S_i\} \cup\{if(t_1)then (t_2)...
- 159
0
votes
0
answers
29
views
Programming language implementation challenge: is recursion harder than HOFs, or vice versa?
(Initially this question was on cstheory, but I was told cs would be a better fit, so posting it here.)
All other things being equal, which of the following languages would be more challenging to ...
- 159
1
vote
3
answers
114
views
In theory, is it impossible, or possible (although ridiculously impractical), to inline recursive functions?
In an older question I asked about stack, the statement came up that recursive functions cannot be inlined (link). I am interested in whether this statement is actually true or not. I understand that ...
- 133
0
votes
1
answer
26
views
Implementation of cantor set without recursion
I'm working on the implementation of a cantor set on a 2-dimensional plane. It looks like this. Honestly, There is the obvious algorithm for the cantor set, but it includes a recursive method call. ...
0
votes
3
answers
127
views
is there an O(n^2) approach to this problem?
Given an array of N elements, I need to split it into k subarrays, where k can be between 2 <= k <= N. A sub-array's score is determined by:
(left boundary point - right boundary point of the ...
-4
votes
2
answers
28
views
Let F be a function defined for all nonnegative integers by the following recursive definition
Let F be a function defined for all nonnegative integers by the following recursive
definition.
F(0) = 0, F(1)= 1
F(n + 2) = 2F(n) + F(n +1), n>0
Compute the first six values of F; that is, write ...
- 1
0
votes
0
answers
16
views
How to prune a tree of selective nodes without recursion, using a stack [duplicate]
I can't solve the following problem without recursion. I get that the solution has to do with making a list of nodes to process but that's where I get stuck.
The problem is to remove all nodes from a ...
- 101
0
votes
1
answer
76
views
Minimizing/Maximizing recursion depth for DFS
The idea for this problem comes from GATE CS 2014 Set-3 Q13.
Given a graph, are there any heuristics to figure out a DFS traversal which has minimum/maximum recursion depth?
Consider the graph from ...
- 769
1
vote
1
answer
102
views
Expected runtime of recursive algorithm with optional part
I have a randomized recursive algorithm which expected running time is $T(n)$. In particular, the recursion looks like this: $$ T(n) \leq \mathcal cn + R ,$$ where $R$ is a recursive term that depends ...
- 73
0
votes
1
answer
53
views
Recursive DFS Problem
I have been struggling with this contest problem for awhile now which is found at this link: https://people.eecs.berkeley.edu/~hilfingr/programming-contest/pacific-northwest/2009/b.pdf
Short summary ...
- 1
0
votes
2
answers
40
views
How to find the runtime out of a recursion formula when using divide and conquer
In dived and conquer one uses the following formula to find the runtime: $$T(n) = aT(n/b) + f(n).$$ I am confused with the meaning of the constants $a,b$ as well as by the question how to find f(n). ...
- 113
-3
votes
1
answer
46
views
How to solve T(n)=2T(√n)+(loglogn)^2?
Trying to solve the recurrence, but no clue how to deal with the (loglogn)^2 part
- 1
0
votes
0
answers
34
views
Iterative algorithm for assembly index? [duplicate]
DOI: 10.3390/e24070884 provides pseudocode for computing the assembly index of an object. It is written as recursive algorithm, which might be fine. But I would like to implement an iterative version ...
- 125
0
votes
0
answers
30
views
Defining dynamic programming [duplicate]
Could we say that Dynamic programming is nothing but recursion + Memoization?
Although the formal definition of dynamic programming is that the problem should have an optimal substructure property, ...
- 131
0
votes
0
answers
77
views
Tail call optimization via translating to CPS
I am struggling to wrap my head around this compiler technique, so lets say here's my factorial function
...
- 195
1
vote
0
answers
37
views
The complexity of Steinberg's strip-packing algorithm
In reading the paper "a strip-packing algorithm with absolute performance bound 2", the author gives a recursion formula $T(l)=T(l')+T(l'')+O(min\{l'\log{l'},l''\log{l'}',l\})$, where $l'+l''...
- 11
1
vote
2
answers
54
views
Can a strict right fold be implemented in a single loop?
A strict left fold is straightforward to implement as a loop, rather than with recursion:
...
- 413
2
votes
1
answer
69
views
Runtime complexity of permutation function
I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums.
...
- 21
1
vote
1
answer
121
views
How are regular languages not structurally recursive?
This blog posting states that "regular languages aren't structurally recursive" while
"That's not the case for context-free grammars"
In what sense is the term "structurally ...
- 111
0
votes
3
answers
77
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
44
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
39
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
68
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
141
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
109
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 ...
- 578
0
votes
1
answer
58
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
69
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 ...
- 187
1
vote
3
answers
108
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
30
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
80
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
22
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
79
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
166
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
39
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. ...
3
votes
1
answer
233
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 ...
- 279
1
vote
1
answer
248
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
25
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
15
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 ...
- 578
0
votes
1
answer
106
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
3k
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
148
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
53
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