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
1
vote
2
answers
154
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
77
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
52
views
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
99
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
72
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
128
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
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
2
answers
86
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
114
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
1
vote
1
answer
99
views
Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion
We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly
proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
- 111
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
-4
votes
1
answer
94
views
Why is incompleteness important?
Or take Russel's paradox. Either the barber does or doesn't shave himself -- that's all there is. How you describe it is an artificial construct.
Godel's theorem is like dividing by zero and declaring ...
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
1
vote
0
answers
77
views
Bottom-up well-balanced mergesort
If you implement mergesort top-down you can always split the input of length $n$ into one of length $\lfloor n / 2\rfloor$ and one of length $\lceil n / 2 \rceil$. This ensures that all merges are ...
- 14k
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
1
vote
2
answers
182
views
How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?
The provided recurrence relation is as follows:
$$ T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2 $$
The goal is to express the solution in terms of the asymptotic notation $\Theta$. Unfortunately,...
- 367
0
votes
1
answer
181
views
1
vote
1
answer
152
views
Complexity of recursive function using Master theorem
this code aims to determine whether there exists a contiguous subarray starting from index 0 in the given array A whose elements sum up to the target value S.
can we apply Master theorem to find out ...
- 59
2
votes
2
answers
281
views
1
vote
2
answers
119
views
Bound $T$ asymptotically tight | Recursive trees
Let $\alpha \in (0, 1),\space l \geq 2$ and $T: \mathbb{N}\rightarrow\mathbb{R}^+$ such that, $T(n) = \begin{cases} n^l + T(\alpha n) + T((1-\alpha)n) & : n > 1 \\1 : n=1 \end{cases}$
Bound $...
- 113
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
0
votes
1
answer
82
views
What is the "big theta" order of the solution of T_n = T_(n/2) + log n, n > 0?
What method(s) could be used to solve this? I am still new to this stuff and would appreciate detailed justification for every step as well as some intuition and the examination of all possible viable ...
- 13
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
0
answers
62
views
USACO Ski Course Design
So I was doing this problem, but it led me to a different solution. The actual solution is this:
Problem -
Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation ...
0
votes
4
answers
527
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
1
vote
1
answer
206
views
Restore the original array after merge Sort based on it's steps
i'm trying to write an algorithm to reconstruct the original array from the sorted one. considering input value is a string of 1s and 2s which 1 means in merging part of merge sort, element from left ...
- 67
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
2
answers
129
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 ...
- 141
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 ...
1
vote
1
answer
112
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
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
2
votes
1
answer
101
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
802
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
2
answers
247
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
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
3
answers
327
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 ...
- 173
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
3
answers
145
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 ...
- 153
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
0
votes
1
answer
375
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 ...
- 201
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
1
vote
1
answer
155
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 ...
- 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
1
vote
2
answers
146
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}{...
- 111
-2
votes
1
answer
103
views
0
votes
1
answer
86
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 “...
- 182
2
votes
2
answers
223
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
0
votes
2
answers
146
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 ...
- 123