# Tasks in which recursion is either the fastest or only way to produce a result [duplicate]

I've just finished studying recursion at university. One thing that stood out for me however was that in both the lectures and in the practical we completed, all the tasks we were asked to do could be performed faster, and in less code, using iterative means.
This was something the lecturer confirmed.

Could somebody please give me some examples of situations when recursion is a better solution than iterative techniques? Additionally, are there any situations in which recursion is the only way to sole a problem?

-

## marked as duplicate by Juho, vonbrand, Luke Mathieson, AJed, KavehFeb 23 '13 at 7:30

@DaveClarke: You're a star Dave - should I delete this topic then? – Andrew Martin Feb 20 '13 at 20:37
If you think it overlaps too much, then yes. – Dave Clarke Feb 20 '13 at 21:11

There are no questions which can only be solved with recursion. This is because they can be solved with Turing machines, which don't use recursion.

The set of problems which can be solved with a TM are exactly the same as the ones which can be solved with recursion (or its formal model, the Lambda Calculus).

In particular, if you want to simulate recursion iteratively, the way to do this is to use a data structure called a stack (which simulates the call stack for functions).

As for algorithms that can be solved better using recursion, there are tons. I'm surprised that your recursive versions were longer, as recursion usually leads to less code. This is one of the reasons haskell is gaining popularity.

Consider the algorithm quicksort, for sorting lists. In rough pseudocode, it's as follows:

function quicksort(list)
if length(list) <= 1
return list
pivot = first element of list
lessList = []
equalList = []
greaterList = []
for each element in list:
if element < pivot, add to lessList
if element == pivot, add to equalList
if element > pivot, add to greater list
sortedLess = quicksort(lessList)
sortedGreater = quicksort(greaterList)
return sortedLess ++ equalList ++ sortedGreater


where ++ means concatenation.

The code isn't purely functional, but by dividing the list into different parts, and sorting each sublist recursively, we get a very short $O(n\log n)$ sort.

Recursion is also very useful for recursive data structures. Often times you'll have a traversal on trees, of the following form:

function traverseTree(tree)
if (tree is a single node)
do something to that node
else, for each child of tree:
traverseTree(child)

-
Thanks for this. We used recursion for things like Fibonnaci and Triangle numbers, where iterative means were much faster. These are fascinating. – Andrew Martin Feb 20 '13 at 22:41
You'll come across some problems where recursion isn't any slower, because the only non-recursive way to solve them is basically to build your own function call stack. Also, in languages like Lisp or Prolog, which support tail recursion, certain types of recursion can be made as efficient as iterative methods (because a new stack frame doesn't need to be created). – jmite Feb 20 '13 at 22:43
Easier answer: Your CPU is purely sequential, yet C (and Java, and Scheme, even latest FORTRAN) allow recursion. – vonbrand Feb 20 '13 at 23:03
@AndrewMartin, as it turns out, computing Fibonacci numbers using the recurrence directly as written (two function calls) is terrible, but you don't have to do it that way. And as the answer says, there are many, many situations in which a recursive algorithm is simply the only understandable way to express a computation. – vonbrand Feb 20 '13 at 23:09
@AndrewMartin, recursion is an important tool in the programmer's arsenal. Not required every day, but indispensable when you need it. Get familiar with the idea of recursion. – vonbrand Feb 21 '13 at 3:25

Anything that can be implemented through recursion can be implemented through iteration, and vice versa. So there is no task which it is impossible to accomplish without recursion (assuming a programming language that has the usual iterative constructs).

The cost of transforming a recursive program into an equivalent interative one is up to polylogarithmic time in most settings, and close to constant time (depending on the size of the code, but not on the size of the data) in practice. This is because the gist of the transformation from a recursive program to an iterative program is to push a record on a global stack every time a function is called, and pop that record when the function returns. This doesn't make any significant change to running time, other than memory management for the additional stack. So where a recursive program exists, an equally fast equivalent iterative program exists (for reasonable values of “equally”).

For some recursive programs, a transformation to an iterative program can significantly increase the complexity in terms of code maintenance. All that stack management can amount to significant amounts of code, especially to ensure that you have captured the right data in stack records.

A typical example where recursion is natural and avoiding it is cumbersome is tree traversal. Consider a program that manipulates binary trees and must often traverse them. A recursive traversal goes like this:

def traverse(tree):
if tree.left_child != None: traverse(tree.left_child)
if tree.right_child != None: traverse(tree.right_child)


An iterative traversal requires explicit stack maintenance — and this is a simplified example which doesn't maintain local data as it traverses the tree:

def traverse(tree):
stack = new_empty_stack()
stack.push(tree)
while not stack.is_empty():
node = stack.pop()