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 ...
• 261
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
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
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
236 views

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. ...
• 151
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