Recursion – How to Mentally Keep Track of Recursive Processes

recursion

I have great trouble doing recursion, especially trying to visualize it. A great example is the aging wine problem described in the top answer of this link: https://www.quora.com/Are-there-any-good-resources-or-tutorials-for-dynamic-programming-besides-the-TopCoder-tutorial. In the example, you are tasked with finding the optimal sequence of wine to sell given the wine's initial prices and the fact that the prices double each year.

int p[N]; // read-only array of wine prices
// year represents the current year (starts with 1)
// [be, en] represents the interval of the unsold wines on the shelf
int profit(int year, int be, int en) {
  // there are no more wines on the shelf
  if (be > en)
    return 0;
  // try to sell the leftmost or the rightmost wine, recursively calculate the 
  // answer and return the better one
  return max(
    profit(year+1, be+1, en) + year * p[be],
    profit(year+1, be, en-1) + year * p[en]);
}

Above, I have a hard time visualizing. First I think what the function returns at the end of the recursion, which is a 0, then I try to calculate the value that is returned from the second to last recursion. I can do this for several steps until I get lost.

Best Answer

Don't try to descend the stack in your head. That way madness lies. By the magic of mathematic induction, every recursive invocation below you can be assumed to be debugged and already working thanks to the programmer who is the future you. Treat it like a call to a library function that you don't have the source code to. If it helps you to work it out, comment it out temporarily and replace it with its results for a test case of reasonable size.

In other words, you don't need to be able to follow the complete algorithm. All you need to know is how to make the problem slightly smaller so you can call an algorithm that already works thanks to recursive you, and write a trivial base case. I can't stress that enough. Trust that the recursive call already works. Once you do that, recursive algorithms become way easier.

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:

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.

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 write or 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

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.

Recursive Definition of the Factorial Operation

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:

Simple Form of the Exponentiation Operation

can be expressed like this by recurrence:

Recurrence Relation for the Exponentiation Operation

Harder

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:
- Koch's Snow Flake Fractal,
- Sierpinski's Triangle.
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.

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:

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"

Mutually Recursive:

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 n or (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 n in 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) where g(x) = f(x) + l(x) and h and l just 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:

Hofstadter's Male and Female 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.

Recursion without factorial, Fibonacci numbers etc

Directory / File structures are the best example of a use for recursion, because everyone understands them before you start, but anything involving tree-like structures will do.

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}

Best Answer

Related Solutions

In plain English, what is recursion

Maths

Coding Examples

Helpers

Pitfalls and Further Learning

Recursion without factorial, Fibonacci numbers etc

Related Topic