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

OK, how you choose to remember values for the way back from the
recursion is up to you. A stack was my way of describing that
mechanism. Nonetheless, my point was that we need not think about
remembered values. Robby has given you a nice example. It's now up to
you to try writing recursive functions without trying to explicitly
think about remembering values.

The stepper is a wonderful tool if this kind of visualization is
useful to you. I for one try to get students to think about the
problem and, if applicable, the shape of their data and to rely very
little on the stepper.

Cheers,

Marco



On Jan 4, 2008 5:24 PM, Yavuz Arkun <yarkun at gmail.com> wrote:
> 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
> >
> >
>
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>