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

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 
about the phobias of CS academics...hmm.)

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