What is the best way to learn recursion?

Question

When I started in programming I started with c++ and was doing recursion in my second semester in a data structures class. I don't even remember how we started it, I think it was linked lists, but its a concept that I picked up easily and can jump into quickly, even when I haven't written any recursive code in quite some time. What is the best way to explain recursion to someone who doesn't understand it? What kind of simple examples could you show to someone to demonstrate the concept and quick exercises they could practice with to get the hang of it?

Answer 1

First you have to learn recursion.

Answer 2

First, learn recursion!

Ooh! Beaten by two seconds!

Answer 3

I'd say a good example could be stepping recursively through a multiple level array. That was probably my first foray into recursive functions.

Answer 4

Infinite recursion == Stack Overflow :-)

Answer 5

Anything to do with tree structures makes it easy to explain recursion. For example, tracing a family tree. Find your parents, and for each of them, find their parents. The algorithm recurses.

Answer 6

There is another question dealing with this topic.

I learnt recursion by writing code to draw a fractal tree, in logo*. I found it a fun introduction. Logo is actually a very nice language for a learner, especially regarding recursion.

* http://en.wikipedia.org/wiki/Logo_(programming_language)

(damn urls-with-brackets-in-them bug)

Answer 7

The book Common Lisp: A Gentle Introduction to Symbolic Computation has an entire chapter (chapter 8) on recursion. The dragon stories in there might help. They are ideal for beginners.

Answer 8

Tree traversal is the simplest way to show recursion. You can show how easy it is to do depth first, bredth first, left first, right first etc with a very simple function.

Traverse( node )
{
    if ( null == node ) return;
    // left first
    Traverse( node.left );
    print( node );
    Traverse( node.right );
}

You just need to change the order of print and Traverse functions to change the type of traversal.

Answer 9

I feel like I have been saying using this book as an answer all day, but The Little Schemer is a fun and easy way to learn recursion really well.

Jelly stains!

Answer 10

Some of the standard exercises/demonstrations:

• Implement a function that computes a factorial. (Try this both the iterative way and the recursive way.)

• Compute numbers in the Fibonacci series.

• Implement Towers of Hanoi.

• Implement a mathematical expression evaluator that allows parentheses.

• Implement Quicksort.

Answer 11

The way I learned recursion was through a haskell course. The method that sticks with me the most is multiplication using recursion.

So suppose we have a function mult which multiplies two numbers

mult n 0 = 0 -- anything times 0 is zero
mult n 1 = n -- anything times 1 is itself
mult n m = mult n (m - 1) + n -- recur: add m, and then multiply by n-1

We have defined 3 cases, two which stops the recursion (known as base cases) and one which calls mult again (the recursive case). As long as the recursive case progresses towards one of the base cases then this function will eventually return.

So mult 3 3 would follow this recursion:

mult 3 3
   mult 3 (3-1) + 3
      mult 3 (2-1) + 3
         3 #return 3 since we have mult 3 1
      3+3
   6 + 3
= 9

Answer 12

I learned it by writing code that displays threaded/nested comments. I had tried learning it before but didn't really get it until I actually had to use it.

Answer 13

If you understand recursion, you're done. Otherwise go read this StackOverflow question...

Answer 14

Buy a book of functional programming and warp your mind.

Answer 15

One of the simplest examples I have seen is calculating a factorial

 unsigned int factorial(unsigned int n) 
 {
     if (n <= 1) return 1;
     return n * factorial(n-1);
 }

Answer 16

I agree with Matt's answer. I always found tree structures well suited to explaining recursion. The definition of the tree itself is recursive as are the algorithms to traverse and perform operations on them.

I think using recursive definitions as opposed to algorithms make the concept a bit easier to grasp because they are typically terse and have little to do with actual code. Factorials and other mathematical formulas fall into this category as well.

Answer 17

Start learning lisp. You don't have to set out to make a huge program in lisp, but you can redo simple things. Like if you have a crazy loop, try turning it into a recursive function in lisp. or you can try to do simple things like x^y.

If you don't want to learn lisp try rewriting a very small program or old homework assignment only not using any loops, just recursion.

Note: in most languages, you are better off using a loop then recursion. Loops are easier for new programmers to understand as well.

Answer 18

I like to explain recursion to non programmers by picturing they want to build a Lego castle with 300 pieces. The problem is, they don't know how to build it with 300 piece, so they start by ease up the problem or "recursive" call the easier problem, build the castle with 299 pieces and look how they put the final peace to the castle. Now they call themselves recursively again to solve the castle with 298 pieces and so on until there is only the castle with 2 pieces, which is the only castle they can solve immediately. After building the castle with 2 pieces, they now can build it with 3 pieces and so on.

Also I explain that recursion always needs two things, nothing more but nothing less:

1. The end condition, when do we end the recursion? in out example it's the castle with 2 pieces. Every bigger castle comes down to the problem solving the castle with two pieces, so this is our end condition.
2. The recursion step, this is the step which we can always take to get to the next bigger problem. In our example adding one piece.

Answer 19

The best article I have ever read, and what really helped me understand recursion was Douglas Crockfords article "The little javascripter" (http://javascript.crockford.com/little.html)

Answer 20

Write a compiler. I guarantee you'll understand recursion after you're finished.

Answer 21

I really liked the way it was explained in my data structures class. The basic idea is to take a large and/or complex problem, and break it down into small, easy to manage pieces. For instance, 9! can be broken down this way:

I don't know what 9! is, but I know it's equal to 9 * 8!
I don't know what 8! is, but I know it's equal to 8 * 7!
...
I don't know what 2! is, but I know it's equal to 2 * 1!
I know that 1! = 1

thus, 2! = 2 * 1 and 3! = 3 * 2 * 1 ... so 9! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362,880

As you break the problem down, you should continue to approach the simplest form of the problem, in this case, 1!. If your algorithm does not approach the simplest case, or "base case", then it will continue forever, or until you reach software/hardware constraints. So, in a factorial function, there are two cases: 1!, and everything else. It looks something like this:

factorial(num)
{
     if (num == 1)
        return 1
     else
        return num * factorial(num - 1)
}

Another fun (although somewhat more complex) problem that is best solved using recursion is the Towers of Hanoi problem.

Answer 22

Write a single function which creates a text file and all the missing parent folders in its path:

function create_text_file($path, $contents) {
  [add your code here]
}
create_text_file("/tmp/folders/which/do/not/exist/somefile.txt", "Hello World");
echo file_get_contents("/tmp/folders/which/do/not/exist/somefile.txt");

I'm not a mathematician so I find this easier to test than number sequences (Fibonacci, factorial).

Answer 23

Give them an example to list all the folders/subfolders of their drive. For those kind of structures, they could appreciate how elegant recursion is.

Answer 24

I learned recursion the following way

1. Code the factorial program using recursion
2. Code fibonacci numbers using recursion

Now do the same without recursion. Try tree traversal, Depth first search later.

In short, You want to learn to code in recursion to learn it.

Answer 25

I find this useful

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=recursionPt1

Answer 26

Please see my answer here:

The best way to learn recursion is to get some experience in a functional programming language such as Haskell or Lisp or Scheme.

(snip)

Another good way is to get some practice in mathematical proofs involving induction.

---

Key concepts relating to recursion:

With recursion you don't need to know how to solve the problem. You just need to know 2 things. 1) how to solve the smallest instance of the problem, and 2) how to break it up into smaller parts.

Equivalently, you just have to keep in mind that you need: 1) a base case and 2) a recursive case.

The base case handles 1 single instance of what you want to do with smallest input.

The recursive case breaks the problem into a subproblem. Eventually this subproblem will reduce to the base case.

Example:

//1+...+n = n*n(+1)/2 = sumAll(n):

int sumAll(int x)
{
  if(x == 0) //base case
    return 0; 
  else
    return sumAll(x-1) + x; //recursive case
}

It is important to understand that the base case is not hard to figure out. It just has to exist. Here is an equivalent solution for x> 0:

//1+...+n = n*n(+1)/2 = sumAll(n):
int sumAll(int x)
{
  if(x == 1) //base case
    return 1; 
  else
    return sumAll(x-1) + x; //recursive case
}

Answer 27

Dang, someone already took the joke. :-)

To be serious, for years I was afraid of recursion and didn't quite understand it. What cured me was taking a class in Lisp, and writing and deubgging largeish programs in it. Now it is one of my favorite techniques. There really is no better way to learn a programming technique than by doing it.

As far as explaining it to someone else? That's tougher. It is just not that natural of a concept for a human being. A particular problem is that there is the concept of a stack implicit in it. But you can't really explain that if your listener doesn't understand a little bit about how a computer's stack pointer works, and what goes on under the scenes when you call a subroutine.

Answer 28

I think it's important to begin with the recognition that recursion is easy.

Far too many books and courses step into the subject by making it scary. There is a headline:

RECURSION

... and then there's a couple of paragraphs telling you to concentrate. In a school/college setting, perhaps there's mutterings from the year above "just wait til you reach recursion".

The fact is, there's nothing to fear. Approach it as such.

All recursion boils down to:

• this job is easy for the simplest case
• if I (a function) don't get handed the simplest case, I can break off a piece that is, handle that, then ask another instance of myself to handle what's left in the same way
• if I keep doing that, I'll end up with nothing more to handle.

For example, sorting a list is a big job. But it's very simple if you say:

• a empty list, sorted, is an empty list
• for any other list, take the first item, return the sorted list of items less than that item, then that item, then the sorted list of items greater than that item

The nice thing is that we can casually toss in the word "sorted" into the 'for any other list' step, because we already know how to sort. Even though we are that implementation.

In Haskell:

qsort []     = []
qsort (x:xs) =      qsort (filter  (< x) xs) 
                 ++ [x] 
                 ++ qsort (filter (>= x) xs)

Answer 29

You could always read this link

Answer 30

The way I learned recursion is through the Flood Fill Algorithm.

Maybe it will help you too.

Answer 31

I learned recursion as a kid, programming Logo. It was an interesting (and fun, at the time) way to learn the concepts of recursion, iteration, parameters, functions, etc. And it did make it easier for me to later get into other stuff such as Pascal, C, etc (except BASIC, that thing sucks and I used it waaaaaaay too much in my youth)

Answer 32

Learning Haskell is a good step, if only because you wind up using it for everything, and its fairly rigorous mathematical background makes reasoning by induction (or coinduction) about your programs fairly natural. That and its syntax largely just gets out of your way and lets you focus almost purely on the recursive aspects of your program.

For example, a recursive solution to the towers of Hanoi is tiny, and you can readily see how the recursion is working.

hanoi _ _ _ _ 0 = []
hanoi f a z x n = hanoi f a x z (n-1) ++ f n a z ++ hanoi f x z a (n-1)

move n a b = concat ["Move disc ", show n, " from ", a, " to ", b, "\n"]

solve = hanoi move "A" "C" "B"

Answer 33

We did Scheme in uni last year, but I didn't fully appreciate recursion until I had a problem that was easiest to solve with a simple tree traversal algorithm. The simplest algorithm I could come up with just happened to loop on elements in a linked list structure and recurse when there was a form element (represented by a separate, isolated linked list).

In java/C# style pseudo code:

void parseTree(elementReader reader)
{
    while( reader.hasNext() )
    {
        Element e = reader.next();
        if ( e.type == Element.Type.Form )
        {
            reader.formStart();
            parseTree(reader);
            reader.end();
        }
        else
            // do something with the element
    }
}

Answer 34

I have always been partial to using the Fibonacci Sequence to explain recursion -- probably 'cause I had a cool adjunct professor who used it. I find the Fibonacci sequence easy to understand in math and trivial to transform into code.

The nth Fibonacci Number can be computed by the formula:

f(n) = f(n-1)+f(n-2)

Where
   f(0) = 0
   f(1) = 1

The equation can easily be transformed into code:

int f(int n) {
   if(n <= 0) return( 0 );
   if(n == 1) return( 1 );
   return( f(n-1) + f(n-2) );
}

Writing this code (with some appropriate output statements and watching how it works gives a good practical example of how recursion works. For the pitfalls and advantages of when to use it... well that's more complicated.

Answer 35

You ask google

Answer 36

This may be the most absurdly feared issue in all of software construction. It's a footnote, not very relevant for most real life projects, many times used with no need by people who think it's cool, and program it with no testing whatsoever and then wonder that their software never ends.

Do your job normally, use the right function for each action, test your code, be clear and know the syntax and semantics of the language you're using, and you'll be ok.

Answer 37

I don't remember what got me clicked, but I think the easiest way to communicate what recursion is is with plain natural language. Solve a problem as an example using plain English.

For example, pose the question "how would you get from here to Rome?". You could then answer it with "If we're at Rome then the problem is solved. Otherwise we take a step towards Rome, and then get to Rome from there". Having taken a step towards Rome, the next step in our solution begs the question: how DO we get to Rome? Well, the above solution explains exactly that! And so we go through it again, and again and again and again until your students click, see the process and understand what's going on.

Once they do I'm sure they'll be excited. After all, so many software projects coined their names after recursion!

Answer 38

I like to create recursion in the game Portal by putting the blue portal in the ceiling and the orange one directly below on the floor, then jumping in.