Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
608 questions
0
votes
1
answer
18
views
Find coordinate in ordered-dithering matrix
The Bayer index matrix for ordered dithering can be computed as follows:
...
- 111
-2
votes
1
answer
75
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
1
answer
115
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
71
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
0
votes
1
answer
66
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
1
answer
113
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
3
votes
1
answer
651
views
Can the minimisation operation be seen from a programming language perspective?
If $f$ is a total function $\mathbb N^k\to\mathbb N$, and $g$ is a total function $\mathbb N^{k+2}\to\mathbb N$, then we say that $h:\mathbb N^{k+1}\to\mathbb N$ is definable by primitive recursion ...
- 133
0
votes
1
answer
397
views
Number of ways in which a '?' in a given string can be replaced with numbers from [0-9]
I came across this interesting problem in a test and I couldn't complete it.
There is a string given s which can consists of numbers between 0-9 and '?'. In place of '?' we can insert any of the ...
- 101
2
votes
1
answer
136
views
How to solve the recurrence $ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $ in terms of $\Theta$?
I'm attempting to solve the recurrence relation:
$$ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $$
in terms of its asymptotic behavior ($\Theta$), specifically using the first case of the ...
- 367
0
votes
1
answer
181
views
2
votes
2
answers
280
views
0
votes
0
answers
63
views
Calculating Runtime Complexity: Recursion + Memoization vs Dynamic Programming (with example)
For cases where recursion is used as well as memoization (so that a number of subtrees of what would otherwise be the overall recursive call tree are each replaced to be ...
- 101
3
votes
1
answer
189
views
Useful algorithm not primitive recursive
The Ackermann function is the textbook example of a function which is total recursive but not primitive recursive.
If we want to implement it in some programming language we will need to use a priori ...
- 253
0
votes
4
answers
524
views
Find median in a sorted matrix
Suppose we are given a $n\times n$ matrix that is sorted row-wise and column-wise. We want to find the median in $\mathcal{O}(n\log{n})$.
This is my approach:
We know median is such element that is ...
- 187
2
votes
0
answers
117
views
Implementation of the divide-and-conquer principle for a specific summation formula
I have found two formulas in the work on pages 5 and 6, of which I am trying to develop a recursive implementation. The similarity to the DFT or FFT might be useful here. I divide this question into ...
- 21
0
votes
0
answers
96
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 ...
0
votes
2
answers
144
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 ...
- 187
1
vote
4
answers
800
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
1
answer
118
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
2
answers
73
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 ...
- 173
1
vote
1
answer
100
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 ...
- 301
1
vote
1
answer
144
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 <...
- 123
0
votes
1
answer
115
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 :
...
- 5
-2
votes
1
answer
103
views
2
votes
2
answers
222
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 ...
- 123