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