# Questions tagged [recursion]

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

563 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
236 views

\begin{align*} T &= 1 \\ T &= 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 ... 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 ... 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. ... 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 ... 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,...
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?
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. ...
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) ...