Non-tail call to tail call coversion - Scheme Fibonacci example with recursion tree
After thought from a discussion i had with Felix Terkhorn, made write this blog to show the awesome display of tail-call optimization of scheme using scheme trace. I implemented this optimization when i did my scheme compiler for Prof Dybvig's class.
Here on display is also the conversion of non-tail call to a tail call. Most common example for this is Factorial which can be seen here, but i took Fibonacci as an example because it requires little more thinking. Take a look at the following Fibonacci implementation. We know if lambda is placed in tail context the lambda body will also be in tail context. Also if cond/if is placed in tail context the then and else branches will also be in tail context. But the recursion to fib is placed as args to +. Although + is in the tail context the args to + are not. This is displayed when we calculate (fib 13) and we can see the stack growing and shrinking in the recursion tree.
Now take a look at the re-written tailfib function and its trace. you would notice the tail call optimization as the stack does not grow in the recursion tree. In other words its an iteration. Here the idea is to use an accumulator similar to that of the Factorial example, but in Fibonacci you need two such accumulators because it is a second order recurrence with reference to two previous states. Which updating the accumulators in the reverse order as if you started with the initial condition you would decrement the counter. This placement of accumulators allow us to position tailfib function in tail context of the cond special form, thus making it a tail recursion.
Here on display is also the conversion of non-tail call to a tail call. Most common example for this is Factorial which can be seen here, but i took Fibonacci as an example because it requires little more thinking. Take a look at the following Fibonacci implementation. We know if lambda is placed in tail context the lambda body will also be in tail context. Also if cond/if is placed in tail context the then and else branches will also be in tail context. But the recursion to fib is placed as args to +. Although + is in the tail context the args to + are not. This is displayed when we calculate (fib 13) and we can see the stack growing and shrinking in the recursion tree.
Now take a look at the re-written tailfib function and its trace. you would notice the tail call optimization as the stack does not grow in the recursion tree. In other words its an iteration. Here the idea is to use an accumulator similar to that of the Factorial example, but in Fibonacci you need two such accumulators because it is a second order recurrence with reference to two previous states. Which updating the accumulators in the reverse order as if you started with the initial condition you would decrement the counter. This placement of accumulators allow us to position tailfib function in tail context of the cond special form, thus making it a tail recursion.
>(define fib (lambda (n)
(cond
( (= n 0) 0)
( (= n 1) 1)
( else (+ (fib (- n 1)) (fib (- n 2)))))))
>(fib 7)
13
> (trace fib)
(fib)
> (fib 7)
|(fib 7)
| (fib 5)
| |(fib 3)
| | (fib 1)
| | 1
| | (fib 2)
| | |(fib 0)
| | |0
| | |(fib 1)
| | |1
| | 1
| |2
| |(fib 4)
| | (fib 2)
| | |(fib 0)
| | |0
| | |(fib 1)
| | |1
| | 1
| | (fib 3)
| | |(fib 1)
| | |1
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | 2
| |3
| 5
| (fib 6)
| |(fib 4)
| | (fib 2)
| | |(fib 0)
| | |0
| | |(fib 1)
| | |1
| | 1
| | (fib 3)
| | |(fib 1)
| | |1
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | 2
| |3
| |(fib 5)
| | (fib 3)
| | |(fib 1)
| | |1
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | 2
| | (fib 4)
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | |(fib 3)
| | | (fib 1)
| | | 1
| | | (fib 2)
| | | |(fib 0)
| | | |0
| | | |(fib 1)
| | | |1
| | | 1
| | |2
| | 3
| |5
| 8
|13
13
>(define tailfib (lambda (n F-1 F-2)
(cond
( (= n 0) 0)
( (= n 1) F-1)
( else (tailfib (- n 1) (+ F-1 F-2) F-1)))))
>(define fib(lambda (n)
(tailfib n 1 0)))
>(trace tailfib)
>(fib 7)
|(tailfib 7 1 0)
|(tailfib 6 1 1)
|(tailfib 5 2 1)
|(tailfib 4 3 2)
|(tailfib 3 5 3)
|(tailfib 2 8 5)
|(tailfib 1 13 8)
|13
13Labels: convert, example, fibonacci, nontail call, nontail recursion, recursion tree, scheme, tail call, tail recursion
posted by Chathura Herath | 6:50 PM
|
109 comments
