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

On Jan 4, 2008 2:43 PM, Yavuz Arkun <yarkun at gmail.com> wrote:
> I didn't mean that I can go down 2 levels in terms of abstraction (e.g.,
> Scheme code -> Scheme interpreter -> assembly operations). I mean that I
> can follow through only a few recursive calls of Fibonacci before
> forgetting where I was. My little brain hurts already.

:)

Here's a way to think about it without having to think about stacks or
loops or pushing or popping or cells or anything like that. Just go
back to grade-school algebra. Plug 'n Chug, as they called it when I
was in school (maybe more recently than many here... but getting
surprisingly distant when I think back one it ...):

definition:
  fib(0)=1
  fib(1)=1
  fib(n+2) = fib(n) + fib(n+1)


example use:

fib(4)
=  ;; by last case in the definition, with n=2
fib(2) + fib (3)

-- lets put that on hold, and compute fib(2) and then come back to it.

fib(2)
= ;; by the last case in the definition, with n=0
fib(0) + fib(1)
= ;; by the first two cases in the definition
1 + 1
=
2

--- coming back to the main computation:

fib(4)
=
fib(2) + fib(3)
= ;; by our factored out computation
2 + fib(3)
= ;; by the last case in the definition, with n=1
2 + fib(1) + fib(2)
= ;; by the second case in the definition
2 + 1 + fib(2)
= ;; by out factored out computation
2 + 1 + 2
=
5

So, you might say to me "but that's just the mathematical way of
thinking, not how computation works" but I would say that stepwise
refinement like that is the essence of how computation works. I took a
shortcut and re-used work in a way that a computer would probably not
figure out how to do (altho I wouldn't be surprised if there have been
optimizations proposed that would discover how to turn the very
expensive fib I wrote above into a fib that used two accumulators) but
that doesn't matter: those are valid steps of reasoning and they have
all been proven to be sound ways of thinking wrt to naive ordering
that most implementations do.

Even better: you can see this in action yourself, if you were to type
in the Scheme version of the definition above and then try it in the
stepper. Here's a screenshot, showing a random step in the middle of
the reduction sequence:

http://people.cs.uchicago.edu/~robby/tmp/fib-stepper.png

Robby