Understanding recursion [closed]

Question

How do you empty a vase containing five flowers?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing four flowers.

How do you empty a vase containing four flowers?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing three flowers.

How do you empty a vase containing three flowers?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing two flowers.

How do you empty a vase containing two flowers?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing one flower.

How do you empty a vase containing one flower?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing no flowers.

How do you empty a vase containing no flowers?

Answer: if the vase is not empty, you take out one flower but the vase is empty so you're done.

That's repetitive. Let's generalize it:

How do you empty a vase containing N flowers?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing N-1 flowers.

Hmm, can we see that in code?

void emptyVase( int flowersInVase ) {
  if( flowersInVase > 0 ) {
   // take one flower and
    emptyVase( flowersInVase - 1 ) ;

  } else {
   // the vase is empty, nothing to do
  }
}

Hmm, couldn't we have just done that in a for loop?

Why, yes, recursion can be replaced with iteration, but often recursion is more elegant.

Let's talk about trees. In computer science, a tree is a structure made up of nodes, where each node has some number of children that are also nodes, or null. A binary tree is a tree made of nodes that have exactly two children, typically called "left" and "right"; again the children can be nodes, or null. A root is a node that is not the child of any other node.

Imagine that a node, in addition to its children, has a value, a number, and imagine that we wish to sum all the values in some tree.

To sum value in any one node, we would add the value of node itself to the value of its left child, if any, and the value of its right child, if any. Now recall that the children, if they're not null, are also nodes.

So to sum the left child, we would add the value of child node itself to the value of its left child, if any, and the value of its right child, if any.

So to sum the value of the left child's left child, we would add the value of child node itself to the value of its left child, if any, and the value of its right child, if any.

Perhaps you've anticipated where I'm going with this, and would like to see some code? OK:

struct node {
  node* left;
  node* right;
  int value;
} ;

int sumNode( node* root ) {
  // if there is no tree, its sum is zero
  if( root == null ) {
    return 0 ;

  } else { // there is a tree
    return root->value + sumNode( root->left ) + sumNode( root->right ) ;
  }
}

Notice that instead of explicitly testing the children to see if they're null or nodes, we just make the recursive function return zero for a null node.

So say we have a tree that looks like this (the numbers are values, the slashes point to children, and @ means the pointer points to null):

     5
    / \
   4   3
  /\   /\
 2  1 @  @
/\  /\
@@  @@

If we call sumNode on the root (the node with value 5), we will return:

return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

Let's expand that in place. Everywhere we see sumNode, we'll replace it with the expansion of the return statement:

sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + 0 + 0
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + sumNode(null ) + sumNode( null ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + 0 + 0 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 
 + 3  ;

return 5 + 4 
 + 2 
 + 1 
 + 3  ;

return 5 + 4 
 + 3
 + 3  ;

return 5 + 7
 + 3  ;

return 5 + 10 ;

return 15 ;

Now see how we conquered a structure of arbitrary depth and "branchiness", by considering it as the repeated application of a composite template? each time through our sumNode function, we dealt with only a single node, using a single if/then branch, and two simple return statements that almost wrote themsleves, directly from our specification?

How to sum a node:
 If a node is null 
   its sum is zero
 otherwise 
   its sum is its value 
   plus the sum of its left child node
   plus the sum of its right child node

That's the power of recursion.

---

The vase example above is an example of tail recursion. All that tail recursion means is that in the recursive function, if we recursed (that is, if we called the function again), that was the last thing we did.

The tree example was not tail recursive, because even though that last thing we did was to recurse the right child, before we did that we recursed the left child.

In fact, the order in which we called the children, and added the current node's value didn't matter at all, because addition is commutative.

Now let's look at an operation where order does matter. We'll use a binary tree of nodes, but this time the value held will be a character, not a number.

Our tree will have a special property, that for any node, its character comes after (in alphabetical order) the character held by its left child and before (in alphabetical order) the character held by its right child.

What we want to do is print the tree in alphabetical order. That's easy to do, given the tree special property. We just print the left child, then the node's character, then right child.

We don't just want to print willy-nilly, so we'll pass our function something to print on. This will be an object with a print( char ) function; we don't need to worry about how it works, just that when print is called, it'll print something, somewhere.

Let's see that in code:

struct node {
  node* left;
  node* right;
  char value;
} ;

// don't worry about this code
class Printer {
  private ostream& out;
  Printer( ostream& o ) :out(o) {}
  void print( char c ) { out << c; }
}

// worry about this code
int printNode( node* root, Printer& printer ) {
  // if there is no tree, do nothing
  if( root == null ) {
    return ;

  } else { // there is a tree
    printNode( root->left, printer );
    printer.print( value );
    printNode( root->right, printer );
}

Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );

In addition to the order of operations now mattering, this example illustrates that we can pass things into a recursive function. The only thing we have to do is make sure that on each recursive call, we continue to pass it along. We passed in a node pointer and a printer to the function, and on each recursive call, we passed them "down".

Now if our tree looks like this:

         k
        / \
       h   n
      /\   /\
     a  j @  @
    /\ /\
    @@ i@
       /\
       @@

What will we print?

From k, we go left to
  h, where we go left to
    a, where we go left to 
      null, where we do nothing and so
    we return to a, where we print 'a' and then go right to
      null, where we do nothing and so
    we return to a and are done, so
  we return to h, where we print 'h' and then go right to
    j, where we go left to
      i, where we go left to 
        null, where we do nothing and so
      we return to i, where we print 'i' and then go right to
        null, where we do nothing and so
      we return to i and are done, so
    we return to j, where we print 'j' and then go right to
      null, where we do nothing and so
    we return to j and are done, so
  we return to h and are done, so
we return to k, where we print 'k' and then go right to
  n where we go left to 
    null, where we do nothing and so
  we return to n, where we print 'n' and then go right to
    null, where we do nothing and so
  we return to n and are done, so 
we return to k and are done, so we return to the caller

So if we just look at the lines were we printed:

    we return to a, where we print 'a' and then go right to
  we return to h, where we print 'h' and then go right to
      we return to i, where we print 'i' and then go right to
    we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
  we return to n, where we print 'n' and then go right to

We see we printed "ahijkn", which is indeed in alphabetical order.

We manage to print an entire tree, in alphabetical order, just by knowing how to print a single node in alphabetical order. Which was just (because our tree had the special property of ordering values to the left of alphabetically later values) knowing to print the left child before printing the node's value, and to print the right child after printing the node's value.

And that's the power of recursion: being able to do whole things by knowing only how to do a part of the whole (and knowing when to stop recursing).

Recalling that in most languages, operator || ("or") short-circuits when its first operand is true, the general recursive function is:

void recurse() { doWeStop() || recurse(); } 

Luc M comments:

SO should create a badge for this kind of answer. Congratulations!

Thanks, Luc! But, actually, because I edited this answer more than four times (to add the last example, but mostly to correct typos and polish it -- typing on a tiny netbook keyboard is hard), I can't get any more points for it. Which somewhat discourages me from putting as much effort into future answers.

See my comment here on that: https://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

Your brain blew up because it got into an infinite recursion. That's a common beginner mistake.

Believe it or not, you already understand recursion, you're just being dragged down by a common, but faulty metaphor for a function: a small box with stuff that comes in and out.

Think instead of a task or procedure, such as "find out more about recursion on the net". That's recursive and you have no problem with it. To complete this task you might:

a) Read a Google's result page for "recursion"
b) Once you've read it, follow the first link on it and...
a.1)Read that new page about recursion 
b.1)Once you've read it, follow the first link on it and...
a.2)Read that new page about recursion 
b.2)Once you've read it, follow the first link on it and...

As you can see, you've been doing recursive stuff for a long time without any problems.

For how long would you keep doing that task? Forever until your brain blows up? Of course not, you will stop at a given point, whenever you believe you have completed the task.

There's no need to specify this when asking you to "find out more about recursion on the net", because you are a human and you can infer that by yourself.

Computer's can't infer jack, so you must include an explicit ending: "find out more about recursion on the net, UNTIL you understand it or you have read a maximum of 10 pages".

You also inferred that you should start at Google's result page for "recursion", and again that's something a computer can't do. The complete description of our recursive task must also include an explicit starting point:

"find out more about recursion on the net, UNTIL you understand it or you have read a maximum of 10 pages and starting at www.google.com/search?q=recursion"

To grok the whole thing, I suggest you try any of these books:

• Common Lisp: A Gentle Introduction to Symbolic Computation. This is the cutest non-mathematical explanation of recursion.
• The little schemer.

To understand recursion, all you have to do is look on the label of your shampoo bottle:

function repeat()
{
   rinse();
   lather();
   repeat();
}

The problem with this is that there is no termination condition, and the recursion will repeat indefinitely, or until you run out of shampoo or hot water (external termination conditions, similar to blowing your stack).

If you want a book that does a good job of explaining recursion in simple terms, take a look at Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter, specifically Chapter 5. In addition to recursion it does a nice job of explaining a number of complex concepts in computer science and math in an understandable way, with one explanation building on another. If you haven't had much exposure to these sorts of concepts before, it can be a pretty mindblowing book.

This is more of a complaint than a question. Do you have a more specific question on recursion? Like multiplication, it's not a thing people write a lot about.

Speaking of multiplication, think of this.

Question:

What's a*b?

Answer:

If b is 1, it's a. Otherwise, it's a+a*(b-1).

What's a*(b-1)? See the above question for a way to work it out.

Actually you use recursion to reduce the complexity of your problem at hand. You apply recursion until you reach a simple base case that can be solved easily. With this you can solve the last recursive step. And with this all other recursive steps up to your original problem.