Explanation of the Fibonacci tail recursion according to the scheme?
I am trying to understand tail recursion in Scheme and I am having a hard time understanding what is going on in a path for example using tail recursion for Fibonacci ...
if it is code for tail recursion or iterative Fibonacci:
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
I can essentially understand what's going on on each line except here:
(fib-iter 1 0 n))
what is actually going on in this line? I cannot find an explanation anywhere. I'm new to Scheme and the syntax is still pretty confusing.
Or can anyone please explain what is happening on each line? this is my basic understanding, but I'm not sure if I'm correct:
(define (fib n) ;;define the function fib and variable n
(fib-iter 1 0 n)) ;;?? no idea
(define (fib-iter a b count) ;;define function fib-iter, variables a, b and count
(if (= count 0) ;;if the count is equal to 0,
b ;;return b
(fib-iter (+ a b) a (- count 1)))) ;;recursively calling function fib-iter with 3 parameters (a+b), a and (count - 1)
thank!
source to share
There fib
is a typo in the procedure (no opening parentheses) and should be identified as follows:
(define (fib n)
(fib-iter 1 0 n))
Having said that, the iterative procedure fib
uses a helper called fib-iter
to implement the actual iteration. This line:
(fib-iter 1 0 n)
It is just calling the helper the first time. As you know, the Fibonacci series starts with the values 0
for n=0
and 1
for n=1
and that it is the values that we pass as parameters that we start the iteration loop along with the value n
, which is the number of iterations we want to do before stopping.
From now on, it a
will contain the fibonacci value for n-1
, and b
will contain the fibonacci value for n-2
, and each subsequent step in the iteration will take care of updating a
and b
, until n
it becomes equal to zero, at which point we will stop and return the result.
It might be easier to imagine what happens if we write the same algorithm in an imperative style. Here's one example in Python using an explicit loop construct and the same variable names. This is equivalent to the Scheme implementation:
def fib(n):
count = n
a, b = 1, 0
while count != 0:
a, b = a + b, a
count = count - 1
return b
source to share
There is a bug in the code; fib
there should be a procedure:
(define (fib n)
(fib-iter 1 0 n))
What happens is it calls fib-iter
with the initial values a (= 1), b (= 0) and count (= the fibonacci number you want, the formal parameter n
is - fib
).
Adding a print 'statement to fib-iter
shows what happens in this example for (fib 7)
:
a=1 b=0 count=7 ; initial values as given by `fib` a=1 b=1 count=6 a=2 b=1 count=5 a=3 b=2 count=4 a=5 b=3 count=3 a=8 b=5 count=2 a=13 b=8 count=1 a=21 b=13 count=0 13 ; the returned value for `(fib 7)`
source to share