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
2
answers
41
views
Trying to implement BFS and I am stuck
I am trying to write down a code which would blindly search for a condition using breadth first search.I have been thinking of it for quite some time and I cant figure out how to continue.
On the one ...
0
votes
0
answers
12
views
Better implementations for this dynamic program to solve optimization problem?
In the code below, I describe a problem and provide a backtracking implementation in Python that solves it:
...
- 181
0
votes
0
answers
54
views
Similar problem to Knight's tour
You have board size and one Knight but what is different is that when you move it you have to duplicate the knight and the 2 duplicates have to be in valid position from the knight
This gets repeated ...
1
vote
1
answer
35
views
Complexity of simulations in simulations
This video of a group, who simulated (a very simple version of) Minecraft inside Minecraft itself got me thinking about the performance of such setups.
Another example to what I'm referring to, would ...
0
votes
2
answers
45
views
Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction
Please first take a brief look at my previous question. Here I want to do something similar but for $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$. I know the answer is $T(n)=\Theta(n\log^2{n})$ and I want ...
- 151
2
votes
1
answer
68
views
Checking equality of self-referential lists
Define that an srlist ("self-referential list") over $X$ consists of a list of elements of $X \sqcup \mathrm{srlist}(X).$ So basically, the items can be primitive values, or further self-...
1
vote
4
answers
146
views
Understanding the Recursive Algorithm for Integer Division
In my reference, Page 26, Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, a division algorithm is give as,
\begin{align}
&\text{function divide}(x, y)\\\\
&\...
- 139
1
vote
0
answers
50
views
Diffucuty in understanding code after a recursive call
This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with
the help of print statements (which I've commented).
...
- 11
1
vote
1
answer
54
views
Are there situations where we can decrease the time complexity of a program by increasing its ordinal complexity?
Are there (interesting) situations where we can decrease the time complexity of a program by increasing its ordinal complexity?
For example, is it possible to find a primitive recursive function such ...
- 177
0
votes
3
answers
86
views
When to do proof by structural induction Vs defining a recursive function?
I'm trying to isolate the key differences between induction and recursion so that I am able to know when to use one over the other.
From my understanding, both can be used to prove properties about ...
- 165
0
votes
2
answers
36
views
Can proofs by induction be achieved by defining a recursive function between two recursive objects?
I have two types of objects, X and Y, each are recursive structures, and contain different structures sets of tuples containing sets.. etc. The number of elements in X and Y are is the same.
I need to ...
- 165
1
vote
3
answers
72
views
Having trouble on logic behind recursion
I am struggling to write my own recursive function.I understand how to find the base case but I cant find easily the pattern on the relationship between 2 complicated cases.Do you know any website ...
- 143
0
votes
1
answer
34
views
Are recursive Horn clauses first order?
My understanding is that recursive definitions are considered second-order since they require the fixpoint operator in order to be formulated as "true" definitions. This is even though they ...
- 272
0
votes
1
answer
82
views
Change of associativity for a given right-recursive grammar
In section 3.7.1, of the book titled: Compiler design in C, by Allen I. Holub (made available freely online, by the author here, & the page #19 of errata, here), have on page #176, the mention of ...
- 187
0
votes
0
answers
40
views
Is my mathematical representation of search in binary search tree correct?
You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals <...
- 113
1
vote
1
answer
54
views
Understanding the Internal Stack Frames in a Recursive Function Call
I'm trying to understand how the system's call stack works internally when a
recursive function is called. Specifically, I'm looking at a function that
computes the maximum depth of a binary tree ...
- 113
0
votes
1
answer
29
views
Binary search calculating complexity big o
I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book :
...
- 1
-1
votes
2
answers
67
views
Finding asymptotically tight upper bound of a recursion relation
Find an asymptotic tight upper bound for the following recursion relation: $$T(n)=5T(\frac{n}{5})+\log^2(n)$$
I tried to solve it by applying iteration:
$$T(n)=5T(\frac{n}{5})+\log^2(n)=5(5T(\frac{n}{...
- 99
-2
votes
1
answer
57
views
0
votes
1
answer
33
views
Axiomatically, what characterizes “recursion”?
My question is admittedly simple, but the desire is to have an insightful view on it behind a conventional definition.
In different foundational or axiomatic systems, I have come to consider “...
- 123
1
vote
2
answers
63
views
Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)
The fourth edition of 'Introduction to Algorithms' defines algorithmic recurrences on page 77 as follows:
**Algorithmic recurrences
[...] A recurrence is algorithmic, if for every sufficiently large ...
- 113
0
votes
2
answers
51
views
Clarification of divide-and-conquer recurrence explanation in 'Introduction to Algorithms' (CLRS)
The following excerpt is from page 39 of the 4th edition of 'Introduction to Algorithms' (emphasis added):
2.3.2 Analyzing divide-and-conquer algorithms
[...]
A recurrence for the running time of a ...
- 113
0
votes
0
answers
45
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
68
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:
...
0
votes
1
answer
66
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 ...
- 1
0
votes
2
answers
176
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?
...
- 125
0
votes
0
answers
14
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
26
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
29
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
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
65
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
108
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
46
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)...
- 179
0
votes
0
answers
36
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 ...
- 179
1
vote
3
answers
150
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
39
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
136
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
57
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
1
answer
127
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 ...
- 1,018
0
votes
1
answer
116
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 ...
- 71
0
votes
1
answer
76
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
71
views
Finding the runtime out of a recursion formula when using divide-and-conquer
In divide-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$ and $b$, as well as by the question of how to ...
- 113
-3
votes
1
answer
66
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, ...
- 143
4
votes
1
answer
134
views
Tail call optimization via translating to CPS
I am struggling to wrap my head around this compiler technique, so let's say here's my factorial function
...
- 235
1
vote
0
answers
43
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
60
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
133
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
208
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