Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
612 questions
1
vote
0
answers
36
views
SWI Prolog Problems with getting all solutions
I am just learning Prolog and wrote a small program to compute the Fibonacci numbers using SWI-Prolog:
...
0
votes
2
answers
45
views
Subtree of Another Tree Complexity: Alternative Solution Analysis
To find out if a tree is a subtree of another, there is an O(m*n) complexity solution that I'm aware of, that looks a bit like:
...
3
votes
1
answer
373
views
determining regular expression for language defined recursively in terms of itself
I teach a Finite Automata course and a student just asked me a question which I thought was very interesting but to which I did not know an answer. Suppose I define a language, $L \subset \{0,1\}^*$ ...
3
votes
1
answer
126
views
Flaw in logic to solution to two generals problem
I am failing to find the flaw in logic to a “partial” solution to the two generals problem and would appreciate help seeing where I went wrong (knowing it’s unsolvable)
There are two generals A and B, ...
- 129
0
votes
1
answer
27
views
Find coordinate in ordered-dithering matrix
The Bayer index matrix for ordered dithering can be computed as follows:
...
- 111
1
vote
2
answers
163
views
How to prove $T(n) = 2T(\lfloor\frac{n}{2}\rfloor) + n$ is $\Omega(n\log n)$?
I know how to prove for $O(n\log n)$, but I'm hitting a roadblock with this one. Here's what I've tried:
The hypothesis is that there exists some $c > 0$ so that $T(n) \geq cn \log n $, by assuming ...
- 11
-2
votes
1
answer
89
views
Are there known formal systems where logic and operators emerge purely from recursive structure?
I’m exploring whether there are any existing formal systems that do not assume logic, types, or operators, but instead allow them to emerge solely from recursive structural transformations.
In the ...
0
votes
0
answers
57
views
0
votes
1
answer
126
views
Finding $c$ and $n_0$ for a recursive equation without a base case
I'm trying to find a solution to the following exercise:
Find constants $n_0$ and $c$ such that for all $n \ge n_0,\hskip 1ex T(n) \le cn\log n$ where
$$T(n) = T\left(\frac{3}{4}n\right) + T\left(\...
- 103
0
votes
1
answer
109
views
How to convert Hyperoperation from recursion to iteration?
I’ve been exploring the hyperoperation sequence, which is typically defined recursively.
According to the same source, hyperoperations can be expressed using iteration, but the examples still appear ...
0
votes
1
answer
93
views
Why doesn't this recursive Fibonacci function in Python give me a recursion depth error?
I have the following Python (3.12) code for finding Fibonacci numbers recursively, and keeping track of how many times the function is called.
...
- 103
1
vote
2
answers
134
views
Calculating complexity for recursive functions with substitution method (Big O notation)
$$
T(n) = \begin{cases}
4T(\frac n 2) + \Theta(n) & n \gt 1\\
1 & n \le 1
\end{cases}
$$
I have to calculate the complexity of an algorithm taking time according to above equations using ...
- 11
0
votes
1
answer
75
views
Bellman Ford: Why do we need to use the same vertex with edgesAllowed - 1 in the bellman ford recursive recurrence
So below is the usual bellman ford recurrence
But why do we need to make a call to OPT(v, i-1) given that the shortest path to the vertex v must include the neighbouring vertex u in its shortest path ...
- 11
0
votes
2
answers
99
views
What is the complexity of this tree recursive integer replacement algorithm?
LeetCode has an Integer Replacement problem defined as follows:
Given a positive integer $n$, you can apply one of the following operations:
If $n$ is even, replace $n$ with $n / 2$.
If $n$ is odd, ...
- 1,592
0
votes
1
answer
127
views
Big O notation of T(n) = T(n/2) + O(log n) using master theorem?
I am aware that the algorithm has 1 recursive call of size n/2 and the non-recursive part takes O(log n) time.
Master theorem formula is T(n) = aT(n/b) + O(n^d). In this case a = 1, b = 2, but I am ...
- 1