3674

40
+9  Q:

## What is the best way to learn recursion?

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?

+67  A:

First you have to learn recursion.

You have encountered a StackOverflow
This joke is older than I am.
Isn't this one of the koans in the jargon file...?
+2  A:

First, learn recursion!

Ooh! Beaten by two seconds!

A:

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

A:

Infinite recursion == Stack Overflow :-)

+3  A:

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.

+1  A:

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)

replace '(' with '%28' and ')' with '%29'
+2  A:

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.

+9  A:

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.

+4  A:

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!

The Little Schemer is a great guide to doing recursion well.
+5  A:

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.

http://stackoverflow.com/questions/23930/factorial-algorithms-in-different-languages
Fibonacci is probably the worst example on the planet; exponential time solution for a logarithmic time problem. There are plenty of examples (some of which you also list) where recursion is both clean and fast.
Sorry that I'm such an idiot.
@David: If the goal is to implement a Fibonacci algorithm, I agree with you. But if the goal is to learn recursion, I couldn't disagree more. You just need to make students aware that this is an awfully inefficient calculation designed to teach them how to use recursion.
A:

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
``````
A:

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.

+83  A:

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

+1 for the perfect combination of explanation, example, and wise-ass. :-)
Wouldn't a more complete implementation go along the lines of "If you understand recursion, you're done. Otherwise go read this StackOverflow question.".
Now it's not a stack overflow anymore. Is that a good thing or not?
This is better, because it has an exit condition.
Ideally, you should keep clicking the Back button on your browser after you've understood recursion, in order to understand how the stack deallocation would work ;)
+1 for the base case. @Andrew advanced browsers wouldn't need to use the back button since this is tail recursive.
recursion itself is easy to understand. it is the implementation of it that probably is hard. the example with factorial is easy to understand. but what about more complex one?
+2  A:

+16  A:

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);
}
``````
A:

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.

+1  A:

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.

I think that the "Loops are easier to understand" part is not necessarily true.
+18  A:
That is the best book ever.
I was impressed with DrScheme, it made writing (and debugging) Scheme code really enjoyable for a Non-Schemer like me.
I was really impressed also, first I used the MIT Scheme but unfortunally it made my CPU performance go to 100% all time, then I met DrScheme and it was really better.
A:

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.
A:

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)

A:

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

+5  A:

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.

A:

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

``````function create_text_file(\$path, \$contents) {
}
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).

A:

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.

A:

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.

A:
A:

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
}
``````
A:

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.

+1  A:

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.

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

A:

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

A:

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)

A:

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"
``````
A:

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)
{
{
if ( e.type == Element.Type.Form )
{
}
else
// do something with the element
}
}
``````
A:

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.

+1  A:

At the time of writing google had introduced a link that says "did you mean recursion" but links to the same page. It occasionally disappears if you click it enough.
+2  A:
A:

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.

A:

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!

A:

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.

OK the person who created a loop back to the same page gets 75 votes but I explain a fun way to create recursion in a popular video game among programmers and I get downvoted!!!