Recursion is the process of solving a problem in terms of smaller versions of the same problem. Since the problem gets smaller each time, the process eventually terminates in a problem (the “base case”) that can be solved directly. Be sure of three things:
- The problem gets smaller each time.
- You include a solution for the base case.
- Each case is handled correctly.
That’s really all there is to it.
But what about visualizing how the code runs? You don’t have to. And that’s the point: sometimes a recursive solution is easier precisely because you don’t have to understand in detail how it executes. Graham explains in his Lisp book why tracing the code execution is unnecessary if not harmful.
Students learning about recursion are sometimes encouraged to trace all the invocations of a recursive function on a piece of paper. … This exercise could be misleading: a programmer defining a recursive function usually does not think explicitly about the sequence of invocations that results from calling it. … How do you visualize all those invocations? You don’t have to.
{ 9 comments… read them below or add one }
Nate Kohl 03.30.10 at 07:26
That’s interesting, I’m not convinced: While it’s true that people already comfortable with recursion don’t explicitly think about the sequence of invocations in a recursive call, things may be quite different for beginning programmers.
I seem to recall a certain amount of disbelief after encountering recursion for the first time. Maybe it’s a matter of how different people learn, but I remember that seeing a small but complete trace of a recursive call did wonders to convince me that the whole thing would work. It was only after seeing the guts of how it worked that I felt comfortable with the more formal “inductive” explanation.
John 03.30.10 at 07:56
Kate, you have a good point. Maybe an instructor should give a couple examples that trace the execution to help persuade the skeptical, then point out that worrying about such details may hold you back in the long run.
Jason 03.30.10 at 09:14
I was initially inclined to disagree here, too, but I wonder if a difference of background is behind the disagreement. I’m guessing that you were already a mathematician when you learned computer programming. I wonder if that accounts for your greater comfort with viewing a recursive function as a concise description of an algorithm, without having initially felt the need to see the full series of invocations that leads to its result.
Aaron 03.30.10 at 10:37
Isn’t it also important to note that recursion has to reduce the problem set using the same algorithm on each set?
That’s the defining characteristic, but it’s also a good rule of thumb that when the recursive algorithm is too complex you might want to look for a non-recursive solution. Or when it is to costly, you might want to look for shortcuts outside your recursion. And don’t forget that recursion is sometimes good up to a point. You can recursively reduce a set to the point where it can be managed more easily (e.g. in memory) with a direct method, such as a linear search.
Tomas 04.01.10 at 14:50
It’s obvious: The secret to understanding recursion is knowing how to combine understanding of the first half of recursion with the understanding of the second half.
David 01.18.11 at 11:46
Recursion is an elegant means by which to describe an algorithm, but it hides the assumption about infinite memory that running-time-efficiency algorithms make.
Jon Skeet 04.11.11 at 10:40
Visualizing the trace doesn’t always help to understand the *correctness* of an algorithm, but I find it incredibly helpful to understand the *complexity* of an algorithm… and that’s clearly important in many scenarios.
Typically visualizing the trace doesn’t help in terms of correctness when the algorithm is extremely declarative – and recursive solutions are often very declarative, in my experience. Often the recursive form mirrors how you would *describe* the problem in the first place, so it’s “obviously” correct.
Daan van Berkel 04.11.11 at 12:11
When I introduced students to the notion of recursion or, for that matter, induction, I appealed to the following visualization.
Imagine a very (very) long line of people in which you take part. You are told that everybody is in the line is responsible for solving the problem of a specific size. Furthermore, every person is lazy but cooperative. Specifically, you are lazy but cooperative.
How would you perform your task of solving the problem of a specific size? Reduce the problem to problems of smaller size and delegate them to the person who is responsible for the specific sizes.
How they solve their problem is their problem. I do not really care. But in the end I get a result from the participants and I can assembly to present my answer.
For me this is far more powerful then to trace the code.
Kamal Rawat 09.13.11 at 00:33
A very good article about recursion is at http://www.mindcracker.com/Story/359/a-question-a-day-understanding-recursion.aspx