The idea of recursion is not very common in real world. So, it seems a bit confusing to the novice programmers. Though, I guess, they become used to the concept gradually. So, what can be a nice explanation for them to grasp the idea easily?
To explain recursion, I use a combination of different explanation, usually to both try to:
If your student (or the person you explain too, from now on I'll say student) has at least some mathematical background, they've obviously already encountered recursion by studying series and their notion of recursivity and their recurrence relation.
A very good way to start is then to demonstrate with a series and tell that it's quite simply what recursion is about:
Usually, you either get a "huh huh, whatev'" at best because they still do not use it, or more likely just a very deep snore.
At this stage, my students usually know how to print something to the screen. Assuming we are using C, they know how to print a single char using
I usually resort to a few repetitive and simple programming problems until they get it:
Factorial is a very simple math concept to understand, and the implementation is very close to its mathematical representation. However, they might not get it at first.
The alphabet version is interesting to teach them to think about the ordering of their recursive statements. Like with pointers, they will just throw lines randomly at you. The point is to bring them to the realization that a loop can be inverted by either modifying the conditions OR by just inverting the order of the statements in your function. That's where printing the alphabet helps, as it's something visual for them. Simply have them write a function that will print one character for each call, and calls itself recursively to write the next (or previous) one.
FP fans, skip the fact that printing stuff to the output stream is a side effect for now... Let's not get too annoying on the FP-front. (But if you use a language with list support, feel free to concatenate to a list at each iteration and just print the final result. But usually I start them with C, which is unfortunately not the best for this sort of problems and concepts).
The exponentiation problem is slightly more difficult (at this stage of learning). Obviously the concept is exactly the same as for a factorial and there is no added complexity... except that you have multiple parameters. And that is usually enough to confuse people and throw them off at the beginning.
Its simple form:
can be expressed like this by recurrence:
Once these simple problems have been shown AND re-implemented in tutorials, you can give slightly more difficult (but very classic) exercises:
Note: Again, some of these really aren't any harder... They just approach the problem from exactly the same angle, or a slightly different one. But practice makes perfect.
Some reading never hurts. Well it will at first, and they'll feel even more lost. It's the sort of thing that grows on you and that sits in the back of your head until one day your realize that you finally get it. And then you think back of these stuff you read. The recursion, recursion in Computer Science and recurrence relation pages on Wikipedia would do for now.
Assuming your students do not have much coding experience, provide code stubs. After the first attempts, give them a printing function that can display the recursion level. Printing the numerical value of the level helps.
The Stack-as-Drawers Diagram
Indenting a printed result (or the level's output) helps as well, as it gives another visual representation of what your program is doing, opening and closing stack contexts like drawers, or folders in a file system explorer.
If your student is already a bit versed into computer culture, they might already use some projects/softwares with names using recursive acronyms. It's been a tradition going around for some time, especially in GNU projects. Some examples include:
Have them try to come up with their own.
Similarly, there are many occurrences of recursive humor, like Google's recursive search correction. For more information on recursion, read this answer.
Pitfalls and Further Learning
Some issues that people usually struggle with and for which you need to know answers.
Why, oh God Why???
Why would you do that? A good but non-obvious reason is that it is often simpler to express a problem that way. A not-so-good but obvious reason is that it often takes less typing (don't make them feel soooo l33t for just using recursion though...).
Some problems are definitely easier to solve when using a recursive approach. Typically, any problem you can solve using a Divide and Conquer paradigm will fit a multi-branched recursion algorithm.
What's N again??
Why is my
How do I determine my end condition? That's easy, just have them say the steps out loud. For instance for the factorial start from 5, then 4, then ... until 0.
The Devil is in the Details
Do not talk to early abut things like tail call optimization. I know, I know, TCO is nice, but they don't care at first. Give them some time to wrap their heads around the process in a way that works for them. Feel free to shatter their world again later on, but give them a break.
Similarly, don't talk straight from the first lecture about the call stack and its memory consumption and ... well... the stack overflow. I often tutor students privately who show me lectures where they have 50 slides about everything there's to know about recursion when they can barely write a loop correctly at this stage. That's a good example of how a reference will help later but right now just confuses you deeply.
But please, in due time, make it clear that there are reasons to go the iterative or recursive route.
We've seen that functions can be recursive, and even that they can have multiple call points (8-queens, Hanoi, Fibonacci or even an exploration algorithm for a minesweeper). But what about mutually recursive calls? Start with maths here as well.
Starting with just mathematical series makes it easier to write and implement as the contract is clearly defined by the expressions. For instance, the Hofstadter Female and Male Sequences:
However in terms of code, it is to be noted that the implementation of a mutually recursive solution often leads to code duplication and should rather be streamlined into a single recursive form (See Peter Norvig's Solving Every Sudoku Puzzle.
|show 7 more comments|
Recursion is a function that calls itself.
How to use it, when to use it and how to avoid bad design are important to know, which requires you to try it out for yourself, and understand what happens.
The most important thing you need to know is to be very careful to not get a loop that never ends. The answer from pramodc84 to your question has this fault: It never ends...
The most classic example to use recursion, is to work with a tree with no static limits in depth. This is a task that you must use recursion.
|show 5 more comments|
Okay i am going to try to keep this simple and concise.
Recursive function are functions that call themselves. Recursive function consist of three things:
Best ways to write recursive methods, is to think of the method that you trying to write as a simple example only handling one loop of the process you want to iterate over, then add the call to the method itself, and add when you want to terminate. Best way to learn is to practice like all things.
Since this is programmers website I will refrain from writing code but here is a good link
if you got that joke you got what recursion means.
|show 1 more comment|
Recursive programming is the process of progressively reducing a problem in to easier to solve versions of itself.
Every recursive function tends to:
When step 2 is before 3, and when step 4 is trivial (a concatenation, sum, or nothing) this enables tail recursion. Step 2 often must come after step 3, as the results from the subdomain(s) of the problem may be needed in order to complete the current step.
Take the traversal of a straight forward binary tree. The traversal can be made in pre-order, in-order, or post-order, depending on what is required.
Pre-order: B A C
In-order: A B C
Post-order: A C B
|show 3 more comments|
The OP said that recursion doesn't exist in the real world, but I beg to differ.
Let's take the real world 'operation' of cutting up a pizza. You've taken the pizza out of the oven and in order to serve it up you have to cut it in half, then cut those halves in half, then again cut those resultant halves in half.
The operation of cutting the pizza you performing again and again until you've got the result you want (the number of slices). And for arguments sake let's say that an uncut pizza is a slice itself.
Here's an example in Ruby:
def cut_pizza(existing_slices, desired_slices) if existing_slices != desired_slices # we don't have enough slices yet to feed everyone, so # we're cutting the pizza slices, thus doubling their number new_slices = existing_slices * 2 # and this here is the recursive call cut_pizza(new_slices, desired_slices) else # we have the desired number of slices, so we return # here instead of continuing to recurse return existing_slices end end pizza = 1 # a whole pizza, 'one slice' cut_pizza(pizza, 8) # => we'll get 8
So the real world operation is cutting a pizza, and the recursion is doing the same thing over and over until you have what you want.
Operations you'll find that crop up that you can implement with recursive functions are:
I recommend writing a program to look for a file based on it's file name, and try to write a function that calls itself until it's found, the signature would look like this:
So you could call it like this:
It's simply programming mechanics in my opinion, a way of cleverly removing duplication. You can rewrite this by using variables, but this is a 'nicer' solution. There is nothing mysterious or difficult about it. You'll write a couple of recursive functions, it'll click and huzzah another mechanical trick in your programming tool box.
Extra Credit The
Recursion is a tool a programmer can use to invoke a function call on itself. Fibonacci sequence is the textbook example of how recursion is used.
Most recursive code if not all can be expressed as iterative function, but its usually messy. Good examples of other recursive programs are Data Structures such as trees, binary search tree and even quicksort.
Recursion is used to make code less sloppy, keep in mind it is usually slower and requires more memory.
|show 1 more comment|
I like to use this one:
How do you walk to the store?
If you're at the entrance to the store, simply go through it. Otherwise, take one step, then walk the rest of the way to the store.
It's critical to include three aspects:
We actually use recursion a lot in daily life; we just don't think of it that way.
|show 1 more comment|
The best example that I would point you to is C Programming Language by K & R. In that book (and I am quoting from memory), the entry in index page for recursion (alone) lists the actual page where they talk about recursion and the index page as well.
Recursion n. - A pattern of algorithm design where an operation is defined in terms of itself.
The classic example is finding the factorial of a number, n!. 0!=1, and for any other natural number N, the factorial of N is the product of all natural numbers less than or equal to N. So, 6! = 6*5*4*3*2*1 = 720. This basic definition would allow you to create a simple iterative solution:
However, examine the operation again. 6! = 6*5*4*3*2*1. By the same definition, 5! = 5*4*3*2*1, meaning that we can say 6! = 6*(5!). In turn, 5! = 5*(4!) and so on. By doing this, we reduce the problem to an operation performed on the result of all previous operations. This eventually reduces to a point, called a base case, where the result is known by definition. In our case, 0!=1 (we could in most cases also say that 1!=1). In computing, we are often allowed to define algorithms in a very similar way, by having the method call itself and pass a smaller input, thus reducing the problem through many recursions to a base case:
This can, in many languages, be further simplified using the ternary operator (sometimes seen as an Iif function in languages that don't provide the operator as such):
The example I use is a problem I faced in real life. You have a container (such as a large backpack you intend to take on a trip) and you want to know the total weight. You have in the container two or three loose items, and some other containers (say, stuff sacks.) The weight of the total container is obviously the weight of the empty container plus the weight of everything in it. For the loose items, you can just weigh them, and for the stuff sacks you could just weigh them or you could say "well the weight of each stuffsack is the weight of the empty container plus the weight of everything in it". And then you keep going into containers into containers and so on until you get to a point where there are just loose items in a container. That's recursion.
You may think that never happens in real life, but imagine trying to count, or add up the salaries of, people in a particular company or division, which has a mixture of people who just work for the company, people in divisions, then in the divisions there are departments and so on. Or sales in a country that has regions, some of which have subregions, etc etc. These sorts of problems happen all the time in business.
Recursion can be used to solve a lot of counting problems. For example, say you have a group of n people at a party (n > 1), and everyone shakes everyone else's hand exactly once. How many handshakes take place? You may know that the solution is C(n,2) = n(n-1)/2, but you can solve recursively as follows:
Suppose there are just two people. Then (by inspection) the answer is obviously 1.
Suppose you have three people. Single out one person, and note that he/she shakes hands with two other people. After that you have to count just the handshakes between the other two people. We already did that just now, and it is 1. So the answer is 2 + 1 = 3.
Suppose you have n people. Following the same logic as before, it is (n-1) + (number of handshakes between n-1 people). Expanding, we get (n-1) + (n-2) + ... + 1.
Expressed as a recursive function,
f(2) = 1
In life (as opposed to in a computer programme) recursion rarely happens under our direct control, because it can be confusing to make happen. Also, perception tends to be about the side effects, rather than being functionally pure, so if recursion is happening you might not notice it.
Recursion does happen out here in the world though. A lot.
A good example is (a simplified version of) the water cycle:
This is a cycle that causes its self to happen again. It is recursive.
Another place you can get recursion is in English (and human language in general). You might not recognise it at first, but the way we can generate a sentence is recursive, because the rules allow us to embed one instance of a symbol in side another instance of the same symbol.
From Steven Pinker's The Language Instinct:
That is a whole sentence that contains other whole sentences:
The act of understanding the full sentence involves understanding smaller sentences, which use the same set of mental trickery to be understood as the full sentence.
To understand recursion from a programming perspective it's easiest to look at a problem that can be solved with recursion, and understand why it should be and what that means you need to do.
For the example I will use the greatest common divisor function, or gcd for short.
You have your two numbers
You should already be able to see that this is a recursive function, as you have the gcd function calling the gcd function. Just to hammer it home, here it is in c# (again, assuming 0 never gets passed in as a parameter):
In a programme, it is important to have a stopping condition, otherwise you function will recur forever, which will eventually cause a stack overflow!
The reason to use recursion here, rather than a while loop or some other iterative construct, is that as you read the code it tells you what it is doing and what will happen next, so it is easier to figure out if it is working correctly.
|show 5 more comments|
Here is a real world example for recursion.
Let them imagine that they have a comic collection and you're going to mix it all up into a big pile. Careful -- if they really have a collection, they may instantly kill you when you just mention the idea to do so.
Now let them sort this big unsorted pile of comics with the help of this manual:
The nice thing here is: When they are down to single issues, they have the full "stack frame" with the local piles visible before them on the ground. Give them multiple printouts of the manual and put one aside each pile level with a mark where you currently are on this level (ie. the state of the local variables), so you can continue there on each Done.
That's what recursion basically is about: Performing the very same process, just on a finer detail level the more you go into it.
Josh K already mentioned the Matroshka dolls. Assume that you want to learn something that only the shortest doll knows. The problem is that you can't really talk to her directly, because she originally lives inside the taller doll which on the first picture is placed on her left. This structure goes like that (a doll lives inside the taller doll) until ending up only with the tallest one.
So the only thing that you can do is to ask your question to the tallest doll. The tallest doll (who doesn't know the answer) will need to pass your question to the shorter doll (which on the first picture is on her right). Since she also doesn't have the answer she needs to ask the next shorter doll. This will go like that until the message reaches the shortest doll. The shortest doll (who is the only one who knows the secret answer) will pass the answer to the next taller doll (found on her left), which will pass it to the next taller doll... and this will continue until the answer reaches its final destination, which is the tallest doll and finally... you :)
This is what recursion really does. A function/method calls itself until getting the expected answer. That's why when you write recursive code it's very important to decide about when recursion should terminate.
Not the best explanation but it hopefully helps.
Recursion is a very concise way to express something that has to be repeated until something is reached.
Not plain english, not really real life examples, but two ways of learning recursion by playing:
A nice explanaition of recursion is literally 'an action that reoccurs from within itself".
Consider a painter painting a wall, it's recursive because the action is "paint a strip from ceiling to floor than scoot over a little to the right and (paint a strip from ceiling to floor than scoot over a little to the right and (paint a strip from ceiling to floor than scoot over a little to the right and ( etc )))".
His paint() function calls itself over and over again to make up his bigger paint_wall() function.
Hopefully this poor painter has some kind of stop condition :)
|show 1 more comment|
protected by Josh K Feb 15 '11 at 13:45
This question is protected to prevent "thanks!", "me too!", or spam answers by new users. To answer it, you must have earned at least 10 reputation on this site.