Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

This question already has an answer here:

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?

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
    
@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

2 Answers 2

up vote 5 down vote accepted

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)
share|improve this answer
1  
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
1  
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
1  
@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):
    do_something(tree.node_payload)
    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()
       do_something(tree.node_payload)
        if tree.left_child != None: stack.push(tree.left_child)
        if tree.right_child != None: stack.push(tree.right_child)

Exercise: write a recursive program that sums the elements of a tree of integers multiplied by their depth. Write an iterative program that does the same thing.

share|improve this answer
1  
You, sir, are a sadist. –  vonbrand Feb 21 '13 at 3:26
1  
@vonbrand Nah. I didn't ask him to write the iterative version first. –  Gilles Feb 21 '13 at 5:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.