Understanding recursion

Question

Guys I'm having major trouble understanding recursion at school. Whenever the prof is talking about it I seem to get it but as soon as I try it on my own it completely blows my brains. I was trying to solve Towers of Hanoi all night and completely blew my mind. My textbook has only about 30 pages in recursion so it is not too useful. Does anyone know of books or resources that can help clarify this topic?

Answer 1

30 pages seems like more than enough to explain the basic concepts - so I'm not sure more reading will enlighten you further. What languages are you learning? May be worth learning a little bit of one of the functional languages (e.g. F#) which bring recursion more to the fore.

Answer 2

Which book are you using?

The standard textbook on algorithms that is actually good is Cormen & Rivest. My experience is that it teaches recursion quite well.

Recursion is one of the harder parts of programming to grasp, and while it does require instinct, it can be learned. But it does need a good description, good examples, and good illustrations.

Also, 30 pages in general is a lot, 30 pages in a single programming language is confusing. Don't try to learn recursion in C or Java, before you understand recursion in general from a general book.

Answer 3

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.

Answer 4

Recursion

Method A, calls Method A calls Method A. Eventually one of these method A's won't call and exit, but it's recursion because something calls itself.

Example of recursion where I want to print out every folder name on the hard drive: (in c#)

public void PrintFolderNames(DirectoryInfo directory)
{
    Console.WriteLine(directory.Name);

    DirectoryInfo[] children = directory.GetDirectories();

    foreach(var child in children)
    {
        PrintFolderNames(child); // See we call ourself here...
    }
}

Answer 5

Step through a simple recursive method in the debugger. It should be clearer what's going on.

Answer 6

Do you understand how the math expression n! works? That's recursive.

Try to program an equivalent function in the language you're using.

Answer 7

Hi,

When working with recursive solutions, I always try to:

• Establish the base case first i.e. when n = 1 in a solution to factorial
• Try to come up with a general rule for every other case

Also there are different types of recursive solutions, there's the divide and conquer approach which is useful for fractals and many others.

It would also help if you could work on simpler problems first just to get the hang of it. Some examples are solving for the factorial and generating the nth fibonacci number.

For references, I highly recommend Algorithms by Robert Sedgewick.

Hope that helps. Good luck.

Answer 8

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.

Answer 9

I'll try to explain it with an example.

You know what n! means? If not: http://en.wikipedia.org/wiki/Factorial

3! = 1 * 2 * 3 = 6

here goes some pseudocode

function factorial(n) {
  if (n==0) return 1
  else return (n * factorial(n-1))
}

So let's try it:

factorial(3)

is n 0?

no!

so we dig deeper with our recursion:

3 * factorial(3-1)

3-1 = 2

is 2 == 0?

no!

so we go deeper! 3 * 2 * factorial(2-1) 2-1 = 1

is 1 == 0?

no!

so we go deeper! 3 * 2 * 1 * factorial(1-1) 1-1 = 0

is 0 == 0?

yes!

we have a trivial case

so we have 3 * 2 * 1 * 1 = 6

i hope the helped you

Answer 10

A recursive function is simply a function that calls itself as many times as it needs to do so. It's useful if you need to process something multiple times, but you're unsure how many times will actually be required. In a way, you could think of a recursive function as a type of loop. Like a loop, however, you'll need to specify conditions for the process to be broken otherwise it'll become infinite.

Answer 11

http://javabat.com is a fun and exciting place to practice recursion. Their examples start fairly light and work through extensive (if you want to take it that far). Note: Their approach is learn by practicing. Here is a recursive function that I wrote to simply replace a for loop.

The for loop:

public printBar(length)
{
  String holder = "";
  for (int index = 0; i < length; i++)
  {
    holder += "*"
  }
  return holder;
}

Here is the recursion to do the same thing. (notice we overload the first method to make sure it is used just like above). We also have another method to maintain our index (similar to the way the for statement does it for you above). The recursive function must maintain their own index.

public String printBar(int Length) // Method, to call the recursive function
{
  printBar(length, 0);
}

public String printBar(int length, int index) //Overloaded recursive method
{
  // To get a better idea of how this works without a for loop
  // you can also replace this if/else with the for loop and
  // operationally, it should do the same thing.
  if (index >= length)
    return "";
  else
    return "*" + printBar(length, index + 1); // Make recursive call
}

To make a long story short, recursion is a good way to write less code. In the latter printBar notice that we have an if statement. IF our condition has been reached, we will exit the recursion and return to the previous method, which returns to the previous method, etc. If I sent in a printBar(8), I get ****. I am hoping that with an example of a simple function that does the same thing as a for loop that maybe this will help. You can practice this more at Java Bat though.

Answer 12

A recursive function is like a spring you compress a bit on each call. On each step, you put a bit of information (current context) on a stack. When the final step is reached, the spring is released, collecting all values (contexts) at once!

Not sure this metaphor is effective... :-)

Anyway, beyond the classical examples (factorial which is the worst example since it is inefficient and easily flattened, Fibonacci, Hanoi...) which are a bit artificial (I rarely, if ever, use them in real programming cases), it is interesting to see where it is really used.

A very common case is to walk a tree (or a graph, but trees are more common, in general).
For example, a folder hierarchy: to list the files, you iterate on them. If you find a sub-directory, the function listing the files call itself with the new folder as argument. When coming back from listing this new folder (and its sub-folders!), it resumes its context, to the next file (or folder).
Another concrete case is when drawing a hierarchy of GUI components: it is common to have containers, like panes, to hold components which can be panes too, or compound components, etc. The painting routine calls recursively the paint function of each component, which calls the paint function of all the components it holds, etc.

Not sure if I am very clear, but I like to show real world use of teaching material, as it was something I was stumbling upon in the past.

Answer 13

I think this very simple method should help you understand recursion. The method will call itself until a certain condition is true and then return:

function writeNumbers( aNumber ){
 write(aNumber);
 if( aNumber > 0 ){
  writeNumbers( aNumber - 1 );
 }
 else{
  return;
 }
}

This function will print out all numbers from the first number you'll feed it till 0. Thus:

writeNumbers( 10 );
//This wil write: 10 9 8 7 6 5 4 3 2 1 0
//and then stop because aNumber is no longer larger then 0

What bassicly happens is that writeNumbers(10) will write 10 and then call writeNumbers(9) which will write 9 and then call writeNumber(8) etc. Until writeNumbers(1) writes 1 and then calls writeNumbers(0) which will write 0 butt will not call writeNumbers(-1);

This code is essiantially the same as:

for(i=10; i>0; i--){
 write(i);
}

Then why use recursion you might ask, if a for-loop does essentially the same. Well you mostly use recursion when you would have to nest for loops but won't know how deep their nested. For example when printing out iemts from nested arrays:

var nestedArray = Array('Im a string', 
                        Array('Im a string nested in an array', 'me too!'),
                        'Im a string again',
                        Array('More nesting!',
                              Array('nested even more!')
                              ),
                        'Im the last string');
function printArrayItems( stringOrArray ){
 if(typeof stringOrArray === 'Array'){
   for(i=0; i<stringOrArray.length; i++){ 
     printArrayItems( stringOrArray[i] );
   }
 }
 else{
   write( stringOrArray );
 }
}

printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'

This function could take an array which could be nested into a 100 levels, while you writing a for loop would then require you to nest it 100 times:

for(i=0; i<nestedArray.length; i++){
 if(typeof nestedArray[i] == 'Array'){
  for(a=0; i<nestedArray[i].length; a++){
   if(typeof nestedArray[i][a] == 'Array'){
    for(b=0; b<nestedArray[i][a].length; b++){
     //This would be enough for the nestedAaray we have now, but you would have
     //to nest the for loops even more if you would nest the array another level
     write( nestedArray[i][a][b] );
    }//end for b
   }//endif typeod nestedArray[i][a] == 'Array'
   else{ write( nestedArray[i][a] ); }
  }//end for a
 }//endif typeod nestedArray[i] == 'Array'
 else{ write( nestedArray[i] ); }
}//end for i

As you can see the recursive method is a lot better.

Answer 14

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.

Answer 15

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.

Answer 16

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

Answer 17

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 the children, if they're not null, are also nodes.

So to sum the 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 singe 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 is 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 tto 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: http://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

Answer 18

Simple recursive example in Common Lisp:

MYMAP applies a function to each element in a list.

1) an empty list has no element, so we return the empty list - () and NIL both are the empty list.

2) apply the function to the first list, call MYMAP for the rest of the list (the recursive call) and combine both results into a new list.

(DEFUN MYMAP (FUNCTION LIST)
  (IF (NULL LIST)
      ()
      (CONS (FUNCALL FUNCTION (FIRST LIST))
            (MYMAP FUNCTION (REST LIST)))))

Let's watch the traced execution. On ENTERing a function, the arguments are printed. On EXITing a function, the result is printed. For each recursive call, the output will be indented on level.

This example calls the SIN function on each number in a list (1 2 3 4).

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

This is our result:

(0.841471 0.9092975 0.14112002 -0.75680256)

Answer 19

Ouch. I tried to figure out the Towers of Hanoi last year. The tricky thing about TOH is it's not a simple example of recursion - you have nested recursions which also change the roles of towers on each call. The only way I could get it to make sense was to literally visualize the movement of the rings in my mind's eye, and verbalize what the recursive call would be. I would start with a single ring, then two, then three. I actually ordered the game on the internet. It took me maybe two or three days of cracking my brains to get it.

Answer 20

(Puts on the Joke hat, since nobody did it)

If you don't know what recursion is, check out this question

Answer 21

Pete and Repete are in a boat. Pete jumps out. Who is left in the boat.

Repete!

Teller: Pete and Repete are in a boat. Pete jumps out. Who is left?

Repete!