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?
In plain English, what is recursion
recursion
Related Solutions
does this trait [no job done on the way down] warrant that elimination is possible,
No. A simple example: visiting a binary-tree in post order: no work is done on the way down, yet you need a stack (there are ways to encode that stack in the tree by temporarily modifying the tree, but the stack is fundamentally there).
Yet, there are ways to remove non-terminal recursions without using a stack. But those I know are using additional properties, and notably the one that some operations can be carried in another order than the one used for the recursive version. That's true for your Fibonacci example (where you also are using the fact that some operations are redundant), and your merge sort one. Detecting that this property holds can be difficult (it could change the stability and error characteristic of a floating point algorithm for instance).
At least two of them are systematic enough that it would be possible to get compilers implementing them (I know that the first has been implemented in compilers).
the introduction of accumulator parameters. Some cases of non-terminal recursion can be turned into a terminal recursion by introducing an additional parameters and using the associativity of the operation still to be done. That's the case for a recursive factorial or list-length function:
int len(list l) { if (l == NIL) return 0; else return 1 + len(tail(l)); }can be replaced with
int len_aux(list l, int acc) { if (l == NIL) return acc; else return len_aux(tail(l), acc+1); } int len(list l) { return len_aux(l, 0); }There are algorithms showing how to do automatically.
the next technique I've used (but don't remember having seen described in the context of an optimization pass for a compiler) is using memoization as an intermediary step (and thus is valid only for pure function). That is you consider that you are caching the result of the function in a table indexed with its parameters and then see that the table can be computed in another order, sometimes reducing the number of values that need to be kept. That method would be applicable to your Fibonacci program.
Being able to remove recursion for your merge example is even more complex: it is not a pure function but one which mutate state. You can think and deduce that it is possible to change the order of operations to made them suitable for a non-recursive implementation without needing a stack, but such a small description can be useful for a human, expanding it to an algorithm to be implemented in a compiler would need some additional work.
Best Answer
To explain recursion, I use a combination of different explanation, usually to both try to:
For starters, Wolfram|Alpha defines it in more simple terms than Wikipedia:
Maths
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.
Coding Examples
For the rest, it's actually a detailed version of what I presented in the Addendum of my answer for the question you pointed to regarding pointers (bad pun).
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
writeorprintf. They also know about control loops.I usually resort to a few repetitive and simple programming problems until they get it:
Factorial
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.
Alphabets
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).
Exponentiation
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:
Harder
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.
Helpers
A Reference
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.
Level/Depth
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.
Recursive Acronyms
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:
Recursive:
Mutually Recursive:
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
nor (whatever your variable's name) different every time? Beginners usually have a problem understanding what a variable and a parameter are, and how to things namednin your program can have different values. So now if this value is in the control loop or recursion, that's even worse! Be nice and do not use the same variable names everywhere, and make it clear that parameters are just variables.End Conditions
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.
Mutual Recursion
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.
f(x) = g(x) + h(x)whereg(x) = f(x) + l(x)andhandljust do stuff.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.