When to use recursion?

Question

When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?

Answer 1

I have taught C++ to undergraduates for about two years and covered recursion. From my experience, your question and feelings are very common. At an extreme, some students see recursion as difficult to understand while others want to use it for pretty much everything.

I think Dave sums it up well: use it where it is appropriate. That is, use it when it feels natural. When you face a problem where it fits nicely, you will most likely recognize it: it will seem like you cannot even come up with a iterative solution. Also, clarity is an important aspect of programming. Other people (and you also!) should be able to read and understand the code you produce. I think it is safe to say iterative loops are easier to understand at first sight than recursion.

I don't know how well you know programming or computer science in general, but I strongly feel that it does not make sense to talk about virtual functions, inheritance or about any advanced concepts here. I have often started with the classic example of computing Fibonacci numbers. It fits here nicely, since Fibonacci numbers are defined recursively. This is easy to understand and does not require any fancy features of the language. After the students have gained some basic understanding of recursion, we have taken another look at some simple functions we have built earlier. Here's an example:

Does a string contain a character $x$?

This is how we did it before: iterate the string, and see if any index contains $x$.

bool find(const std::string& s, char x)
{
   for(int i = 0; i < s.size(); ++i)
   {
      if(s[i] == x)
         return true;
   }

   return false;
}

The question is then, can we do it recursively? Sure we can, here's one way:

bool find(const std::string& s, int idx, char x)
{
   if(idx == s.size())
      return false;

   return s[idx] == x || find(s, ++idx);
}

The next natural question is then, should we do it like this? Probably not. Why? It's harder to understand and it's harder to come up with. Hence it is more prone to error, too.

Answer 2

The solutions to some problems are more naturally expressed using recursion.

For example, assume that you have a tree data structure with two kinds of nodes: leaves, which store an integer value; and branches, which have a left and right subtree in their fields. Assume that the leaves are ordered, so that the lowest value is in the leftmost leaf.

Suppose the task is to print out the values of the tree in order. A recursive algorithm for doing this is quite natural:

class Node { abstract void traverse(); }
class Leaf extends Node { 
  int val; 
  void traverse() { print(val); }
} 
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

Writing equivalent code without recursion would be much more difficult. Try it!

More generally, recursion works well for algorithms on recursive data structures like trees, or for problems that can naturally be broken into sub-problems. Check out, for instance, divide and conquer algorithms.

If you really want to see recursion in its most natural environment, then you should look at a functional programming language like Haskell. In such a language, there is no looping construct, so everything is expressed using recursion (or higher-order functions, but that's another story, one worth knowing about too).

Note also that functional programming languages perform optimized tail recursion. This means that they do not lay down a stack frame unless they do not need to --- essentially, recursion can be converted to a loop. From a practical perspective, you can write code in a natural fashion, but get the performance of iterative code. For the record, it seems that C++ compilers also optimize tail calls, so there is no additional overhead of using recursion in C++.

Answer 3

From someone who practically lives in recursion I will try and shed some light on the subject.

When first introduced to recursion you learn that it is a function that calls itself and is basically demonstrated with algorithms such as tree traversal. Later you find that it is used a lot in functional programming for languages such as LISP and F#. With the F# I write, most of what I write is recursive and pattern matching.

If you learn more about functional programming such as F# you will learn F# Lists are implemented as singly linked lists, which means that operations that access only the head of the list are O(1), and element access is O(n). Once you learn this you tend to traverse data as list, building new list in reverse order and then reversing the list before returning from the function which is very effective.

Now if you start to think about this you soon realize that recursive functions will push a stack frame every time a function call is made and can cause a stack overflow. However, if you construct your recursive function so that it can perform a tail call and the compiler supports the ability to optimize the code for the tail call. i.e. .NET OpCodes.Tailcall Field you will not cause a stack overflow. At this point you start writing any looping as a recursive function, and any decision as a match; the days of if and while are now history.

Once you move to AI using backtracking in languages such as PROLOG, then everything is recursive. While this requires thinking in a manner quite different from imperative code, if PROLOG is the right tool for the problem it frees you of the burden of having to write lots of lines of code, and can reduce number of errors dramatically. See: Amzi customer eoTek

To get back to your question of when to use recursion; one way I look at programming is with hardware at one end and abstract concepts at the other end. The closer to the hardware the problem the more I think in imperative languages with if and while, the more abstract the problem, the more I think in high level languages with recursion. However, if you start writing low level system code and such, and you want to verify that its valid, you then find solutions like theorem provers come in handy, which rely heavily on recursion.

If you look at Jane Street you will see they use the functional language OCaml. While I have not seen any of their code, from reading about what they mention about their code, they are surly thinking recursively.

EDIT

Since you are looking for a list of uses, I will give you a basic idea of what to look for in the code and a list of basic uses which are mostly based on the concept of Catamorphism which is beyond the basics.

For C++: If you define a structure or a class that has a pointer to the same structure or class then recursion should be considered for traversal methods that use the pointers.

The simple case is a one way linked list. You would process the list starting at the head or tail and then recursively traverse the list using the pointers.

A tree is another case where recursion is often used; so much so that if you see tree traversal without recursion you should start asking why? It is not wrong, but something that should be noted in the comments.

Common uses of recursion are:

• sorting
• searching
• map
• fold
• filter

Answer 4

To give you a use case that is less arcane than those given in the other answers: recursion mixes very well with tree-like (Object Oriented) class structures deriving from a common source. A C++ example:

class Expression {
public:
    // The "= 0" means 'I don't implement this, I let my subclasses do that'
    virtual int ComputeValue() = 0;
}

class Plus : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() + right->ComputeValue(); }
}

class Times : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() * right->ComputeValue(); }
}

class Negate : public Expression {
private:
    Expression* expr;
public:
    virtual int ComputeValue() { return -(expr->ComputeValue()); }
}

class Constant : public Expression {
private:
    int value;
public:
    virtual int ComputeValue() { return value; }
}

The above example uses recursion: ComputeValue is implemented recursively. To make the example work, you use virtual functions and inheritance. You don't know what the left and right parts of the Plus class are exactly, but you don't care: it something that can compute its own value, which is all you need to know.

The crucial advantage of the above approach is that every class takes care of its own computations. You separate the different implementations of every possible subexpressions completely: they have no knowledge of each other's workings. This makes reasoning about the program easier and therefore makes the program easier to comprehend, maintain and extend.

Answer 5

The first example used to teach recursion in my beginning programming class was a function to list all the digits in a number separately in reverse order.

void listDigits(int x){
     if (x <= 0)
        return;
     print x % 10;
     listDigits(x/10);
}

Or something like that (I'm going from memory here and not testing). Also, when you get into higher level classes, you'll use recursion a LOT especially in search algorithms, sorting algorithms, etc.

So it may seem like a useless function in the language now, but it is very very useful in the long run.