Questions tagged [recursion]

Questions about objects such as functions, algorithms or data structures that are expressed using "smaller" instances of themselves.

Filter by
Sorted by
Tagged with
2 votes
2 answers

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 ...
Ashwin's user avatar
  • 261
11 votes
3 answers

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 ...
Tim's user avatar
  • 4,785
76 votes
4 answers

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 ...
Geek's user avatar
  • 1,181
4 votes
1 answer

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 ...
Gigili's user avatar
  • 2,173
3 votes
3 answers

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 ...
Love Paper's user avatar
3 votes
3 answers

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 ...
Timeless's user avatar
  • 785
6 votes
2 answers

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. ...
Chris Bond's user avatar
1 vote
1 answer

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 ...
user avatar
33 votes
6 answers

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,...
Jonathan Prieto-Cubides's user avatar
26 votes
5 answers

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?
Taylor Huston's user avatar
15 votes
6 answers

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. ...
elektronaj's user avatar
10 votes
3 answers

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) ...
OghmaOsiris's user avatar
22 votes
2 answers

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 ...
Gilles 'SO- stop being evil''s user avatar

8 9 10 11