Questions tagged [recursion]
Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.
563
questions
2
votes
2
answers
2k
views
Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle
I have asked this exact question on StackOverflow. I did not get the answer that I was looking for. Please read this question fully before answering. Thank You.
For static pattern database(5-5-5), see ...
- 261
11
votes
3
answers
879
views
Do "inductively" and "recursively" have very similar meanings?
Do "inductively" and "recursively" mean very similar?
For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having ...
- 4,785
76
votes
4
answers
72k
views
What is tail recursion?
I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the ...
- 1,181
4
votes
1
answer
797
views
How to show that f(x) is primitive recursive?
Let
$$f(x)=\begin{cases} x \quad \text{if Goldbach's conjecture is true
}\\ 0 \quad \text{otherwise}\end{cases}$$
Show that f(x) is primitive recursive.
I know a primitive recursive ...
- 2,173
3
votes
3
answers
236
views
Optimize a linear recurrence
$$\begin{align*}
T[1] &= 1 \\
T[2] &= 2 \\
T[i] &= T[i-1] + T[i-3] + T[i-4] & \text{for \(i \gt 2\)} \\
\end{align*}$$
I have to calculate $T[N]$, but $N$ is too big ($\approx ...
- 31
3
votes
3
answers
1k
views
How to write a recursive function that with certain time complexity
I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like
...
- 785
6
votes
2
answers
2k
views
How to go from a recurrence relation to a final complexity
I have an algorithm, shown below, that I need to analyze. Because it's recursive in nature I set up a recurrence relation.
...
- 63
1
vote
1
answer
410
views
Recursion for runtime of divide and conquer algorithms
A divide and conquer algorithm's work at a specific level can be simplified into the equation:
$\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$
where $n$ is the size of ...
user1422
33
votes
6
answers
72k
views
What is most efficient for GCD?
I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers.
But in practice you can code this algorithm in various ways. (In my case,...
- 2,171
26
votes
5
answers
46k
views
When to use recursion?
When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?
- 579
15
votes
6
answers
4k
views
Examples of sophisticated recursive algorithms
I was explaining the famous deterministic linear-time selection algorithm (median of medians algorithm) to a friend.
The recursion in this algorithm (while being very simple) is quite sophisticated. ...
- 151
10
votes
3
answers
4k
views
Algorithm to test whether a binary tree is a search tree and count complete branches
I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) ...
- 435
22
votes
2
answers
3k
views
Recursive definitions over an inductive type with nested components
Consider an inductive type which has some recursive occurrences in a nested, but strictly positive location. For example, trees with finite branching with nodes using a generic list data structure to ...
