Problem with recursion? (was [plt-scheme] Re: Novice needs help writing function )

From: Marco Morazan (morazanm at
Date: Fri Jan 4 16:31:26 EST 2008

> The number of explicit variables in the recursive version is deceptive.
> When I am trying to understand a program, I put myself in the place of
> the computer and work through the program in my mind. For the iterative
> version, everything I need to remember are explicitly named. For
> recursive algorithms, I need to keep track of the implicit variables as
> well, such as how deep I am into the recursion, and what the
> intermediate values are, because I will need them on my way back.

Gee whiz.....this seems like a terribly painful way to try to
understand a program. In fact, I would discourage such a low-level of
abstraction to explain recursion to new students. If someone needs to
think about what is "remembered" on a stack, then chances are they do
not really understand the recursive program they have written (or
trying to write). I certainly do not tell my fresnmen students that
values are remembered by the computer on a stack.

> Personally, I can manage 1 or 2 levels mentally, and if I use pen and
> paper maybe a few more. After that, I need to take a leap of faith, and
> inductively conclude that if it works for the simplest case, and for the
> one after that, it should work for all cases.

Why do you describe it as a leap of faith? Let me ask, what requires a
bigger "leap of faith" that new students can understand what a base
case and an inductive step are or that they can develop the skills to
manually trace values being stored on a stack to implement recursive
calls? The whole point is to _not_ think in terms of values being
pushed onto a stack! To this one person, that is just too hard.

It seems to me that there is a great deal about abstraction that you
are "sweeping under the rug."


Posted on the users mailing list.