In plain English, what is recursion?
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?
More information is being shared on this subject at Resources for improving your comprehension of recursion?
Recursion is when a function can call itself. "If you totally understand namespaces and scope and how parameters are passed to a function, then you know recursion already. I can show examples, but you should be able to figure out how they work on your own." Students generally struggle with recursion not so much because it's confusing, but because they don't have a firm grasp of variable scope/namespace. Before diving into recursion, make sure the students can properly trace through a program where you've purposely given variables at different scopes the same name to confuse them.
There is a famous book that tackles the difficult problem of recursion *in the real world*: https://en.wikipedia.org/wiki/Gödel,_Escher,_Bach
To explain recursion, I use a combination of different explanation, usually to both try to:
- explain the concept,
- explain why it matters,
- explain how to get it.
An expression such that each term is generated by repeating a particular mathematical operation.
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:
- a mathematical function...
- ... that calls itself to compute a value corresponding to an n-th element...
- ... and which defines some boundaries.
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
printf. They also know about control loops.
I usually resort to a few repetitive and simple programming problems until they get it:
- the factorial operation,
- an alphabet printer,
- a reversed alphabet printer,
- the exponentation operation.
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:
- The Fibonacci numbers,
- The Greatest Common Divisor,
- The 8-Queens problem,
- The Towers of Hanoi game,
- And if you have a graphical environment (or can provide code stubs for it or for a terminal output or they can manage that already), things like:
- And for for practical examples, consider writing:
- a tree traversal algorithm,
- a simple mathematical expression parser,
- a minesweeper game.
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:
- GNU - "GNU's Not Unix"
- Nagios - "Nagios Ain't Gonna Insist On Sainthood"
- PHP - "PHP Hypertext Preprocessor" (and originall "Personal Home Page")
- Wine - "Wine Is Not an Emulator"
- Zile - "Zile Is Lossy Emacs"
- HURD - "HIRD of Unix-Replacing Daemons" (where HIRD is "HURD of Interfaces representing Depth")
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 named
nin 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.
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.
f(x) = g(x) + h(x)where
g(x) = f(x) + l(x)and
ljust 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.
I am reading your answer after seeing it after almost 5th or 6th time. It was nice but too long for attracting other users here I think. I learned many things about teaching recursion here. As a teacher, would you please evaluate my idea for teaching recursion- http://programmers.stackexchange.com/questions/25052/a-nice-explanation-for-recursion/25098#25098
@Gulshan, I think this answer is about as comprehensive as any is going to be and is easily 'skimmed' by a casual reader. Hence, it gets a `static unsigned int vote = 1;` from me. Forgive the static humor, if you will :) This is the best answer so far.
@Gulsan: only the one who wants to learn is willing to take the time to do is properly :) I don't really mind. Sometimes, a short answer is elegant and conveys a lot of useful and necessary information to get started or explain a general concept. I just wanted a longer answer for that one, and considering the OP mentions a question for which I was awarded the "correct" answer and asks a similar one, I tought it appropriate to deliver the same sort of answer. Glad you learned something.
@Gulshan: Now regarding your answer: the first point confused me a lot, I have to say. I like that you describe the concept of recursive functions as something that changes state incrementally over time, but I think that your way of presenting is a bit strange. After reading your 3 points, I wouldn't expect many students to suddenly be able to solve Hanoi. But it might just be a wording issue.
I've come across of good way of showing that the same variable can have different values in differing depths of recursion: consider having students write down the steps they're taking, and the values of variables, in following some recursive code. When they reach a recursion, have them start again on a new piece. Once they reach an exit condition, have them move back to the previous piece. This is essentially emulating a call stack, but it's a good way to show these differences.
@AndyBursh: Yes, that's what I call the "stack-as-drawers" diagram. An another approach is to have them take small sheets of paper, and write each state of a new card, and pile them up, thus literally representating the stacked values for the same variable name.
@DeadMG: :) I understand it may not necessarily be the best approach. This is the standard way things were done in my engineering school. Very intensive C/UNIX for the first 2 years (and it's C89), then eventually picking up other stuff (C++, Java, Perl) during year 2 and 3, and some other stuff and more freedom to use other languages for years 4 and 5 (C#). We have a rather strict approach.
@DeadMG: Problem with starting with C is that it puts people off. The good thing is that you start with the basics, and that in this school we absolutely don't care about putting people off, as it's meant for very motivated people with a passion for programming. They like it or leave. Wherever and whenever I teach, I try to keep that alive as much as possible, though in classic university programs some students don't really want to be here, so you need to be more lenient for them. I try to adapt my course to pass this spirit to the motivated ones, while keeping it OK for the others.
@DeadMG: Also, starting with C allows you to then be able to bridge or make relatively educated assumptions (that you should verify whenever possible though) about how higher-level languages work, like understanding array and string differences in Java vs C :) But I agree with you, sometimes it's better to start with fun languages, and I advocate that as well sometimes especially if motivation is lacking, like I was trying to convey in this othe question about how to keep learning.