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

 From: Yavuz Arkun (yarkun at gmail.com) Date: Fri Jan 4 17:24:55 EST 2008 Previous message: Problem with recursion? (was [plt-scheme] Re: Novice needs help writing function ) Next message: Problem with recursion? (was [plt-scheme] Re: Novice needs help writing function ) Messages sorted by: [date] [thread] [subject] [author]

```Marco Morazan wrote:
>> 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.
>
>
Heh, I didn't say anything about stacks or assembly level thinking, but
everyone thinks that I meant that. (I wonder if that reveals anything

In this case the "computer" that I am emulating is like the stepper that
Robby linked a few post back, i.e. works in terms of scheme functions,
variables etc. And as you calculate the fibonacci recursively, you do
need to keep track of where you are and what the passed actual parameter
values are, as shown nicely  in the same post using a pen-and-paper
approach.
>> 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.
>
Again, no stack, just the need to track of the values of the actual
parameters. And, yes, it is not difficult to learn at the end, as
millions of programmers have. The OP was about why recursion is
difficult to teach. Since as a (virtual) student I cannot answer to
that, I contributed my personal view about why it is difficult to learn.
It is (minimally) difficult to grasp at first because it requires the
inductive leap, whereas the iterative versions do not.

Drawing on the students' prior exposure to mathematical induction could
help understanding, of course, but shouldn't come at the cost of ending
up with obviously inefficient code, because that would unfairly
associate "recursion" with "inefficiency" in students' minds.

Yavuz

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

```

 Posted on the users mailing list. Previous message: Problem with recursion? (was [plt-scheme] Re: Novice needs help writing function ) Next message: Problem with recursion? (was [plt-scheme] Re: Novice needs help writing function ) Messages sorted by: [date] [thread] [subject] [author]