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

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 2

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 anyfancy 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.