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

P.S. I am not discouraging you from asking for help or insight. I am
sure there are many people on the list that would be happy to respond
after you think about everything that has been stated and, as Matthias
suggested, work through a bit of HtDP.

On Jan 4, 2008 6:15 PM, Marco Morazan <morazanm at gmail.com> wrote:
> 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
> >
>