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
87
views
Using inductive hypothesis on recurrence relation?
I have a recurrence relation as follows
$$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$
Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor ...
CommunityBot
- 1
5
votes
4
answers
8k
views
What's the Big O runtime of a DFS word search through a matrix?
The problem is to try and find a word in a 2D matrix of characters:
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent ...
- 101
1
vote
2
answers
91
views
Understanding recursion tree for withdrawal formula
$$
T(n) = T(n-a) + T(a) + cn
$$
Now the solution says that the height of the tree $(h)$ is:
$$
h = \left \lfloor n/a \right \rfloor
$$
And I don't understand why. Maybe I didn't understand the ...
- 8,733
0
votes
0
answers
26
views
How to Remove Left Recursion from this Grammar?
How to remove left recursion in the following Grammar:
S→Bb/a
B→Bc/Sd/e
Im new to this, below is the way I'm doing it:
...
- 1
0
votes
1
answer
60
views
Need help with recurrence relation and postcondition of a function
I just wanted to make sure I'm on the right track regarding this.
Here's the function that I'm dealing with:
...
CommunityBot
- 1
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
...
CommunityBot
- 1
0
votes
2
answers
87
views
Complexity of generating all subsets of size $k$ using recursion
What is the complexity of the following (Python) code, that builds the list L of all subsets of size $k$ of a given set?
...
- 699
0
votes
1
answer
57
views
How is there a paradox in the halting problem when you can trace it and it's very clearly non-halting?
Here's Alan Turing's halting problem in pseudocode:
...
- 6,757
1
vote
1
answer
98
views
How to generate tree variants of a tree using recursion?
I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion?
any help is ...
CommunityBot
- 1
0
votes
1
answer
53
views
How to derive time complexity of the Recurrence Relation - T(n,m) = T(n-1,m) + T(n,m-1) + c
I know that, T(n,m) = T(n-1,m) + T(n,m-1) + c it's the recurrence equation of Longest Common Subsequence algorithm. And the time complexity of the LCS in case of recursive method is O(2^n+m).
The base ...
- 27.4k
0
votes
3
answers
81
views
What are the guidelines/tips for calculating the complexity of a chained-recursive function?
Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions..
Are there any ...
CommunityBot
- 1
0
votes
1
answer
1k
views
Prove Recursive formula (Dynamic programming) N(C,i)
I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following ...
CommunityBot
- 1
0
votes
1
answer
195
views
Time complexity of merging two lists while preserving order
I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
CommunityBot
- 1
0
votes
0
answers
13
views
Finding a ArrayList Connection (representing Subway Lines) with Recursion
I have this ArrayList (called linArray) (and this only) that contains Subway exchange stations (first the station name and then the lines you can exchange to at that station):
...
0
votes
0
answers
25
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 ...
1
vote
1
answer
103
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 ...
CommunityBot
- 1
0
votes
1
answer
54
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 ...
CommunityBot
- 1
0
votes
0
answers
28
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
1
vote
1
answer
100
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 ...
CommunityBot
- 1
0
votes
0
answers
34
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
44
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 ...
- 8,733
0
votes
2
answers
94
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?
- 8,733
1
vote
0
answers
96
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
43
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)...
- 8,733
0
votes
0
answers
33
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
118
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 ...
- 27.4k
0
votes
1
answer
29
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. ...
D.W.♦
- 152k
1
vote
2
answers
346
views
Pancake Sorting Graph Recursive Definition
I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough ...
CommunityBot
- 1
0
votes
3
answers
132
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 ...
- 27.4k
-4
votes
2
answers
31
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 ...
- 8,733
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 ...
D.W.♦
- 152k
0
votes
1
answer
98
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 ...
D.W.♦
- 152k
0
votes
2
answers
45
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). ...
- 12k
-3
votes
1
answer
49
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
- 8,733
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, ...
- 143
0
votes
0
answers
84
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
0
votes
3
answers
941
views
Making a recursive formula for finding amount of ways to spend money on beer
So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this.
The information available is that there are $n$ different ...
- 8,733
1
vote
2
answers
55
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
1
vote
0
answers
39
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
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 ...
- 8,733
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 ...
- 2,440
2
votes
1
answer
76
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.
...
- 831
0
votes
3
answers
78
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(...
- 115
1
vote
1
answer
146
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 ...
- 501
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 $...
- 342
-1
votes
1
answer
45
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}...
- 8,733
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 ...
- 8,733
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\...
- 274k
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 ...
- 2,440