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.



>(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
13

Trace lambda in Scheme to display recursion tree

When doing recursions in Scheme programming sometime its useful to see the growth of the recursion tree for debugging or even to get an intuition about approaches to improve the algorithm like dynamic programming. Following is a pure recursive insertion sort, obviously not the efficient implementation, yet it illustrate the use of trace procedure.

(define insert (lambda (val sorted)
(if (null? sorted)
(list val)
(if (< val (car sorted))
(cons val sorted)
(cons (car sorted) (insert val (cdr sorted)))))))

(define sort (lambda (vals)
(if (null? vals)
vals
(insert (car vals) (sort (cdr vals))))))

(trace insert)
(trace sort)





(sort '(7 6 5 9 3 4 2 8))
|(sort (7 6 5 9 3 4 2 8))
| (sort (6 5 9 3 4 2 8))
| |(sort (5 9 3 4 2 8))
| | (sort (9 3 4 2 8))
| | |(sort (3 4 2 8))
| | | (sort (4 2 8))
| | | |(sort (2 8))
| | | | (sort (8))
| | | | |(sort ())
| | | | |()
| | | | (insert 8 ())
| | | | (8)
| | | |(insert 2 (8))
| | | |(2 8)
| | | (insert 4 (2 8))
| | | |(insert 4 (8))
| | | |(4 8)
| | | (2 4 8)
| | |(insert 3 (2 4 8))
| | | (insert 3 (4 8))
| | | (3 4 8)
| | |(2 3 4 8)
| | (insert 9 (2 3 4 8))
| | |(insert 9 (3 4 8))
| | | (insert 9 (4 8))
| | | |(insert 9 (8))
| | | | (insert 9 ())
| | | | (9)
| | | |(8 9)
| | | (4 8 9)
| | |(3 4 8 9)
| | (2 3 4 8 9)
| |(insert 5 (2 3 4 8 9))
| | (insert 5 (3 4 8 9))
| | |(insert 5 (4 8 9))
| | | (insert 5 (8 9))
| | | (5 8 9)
| | |(4 5 8 9)
| | (3 4 5 8 9)
| |(2 3 4 5 8 9)
| (insert 6 (2 3 4 5 8 9))
| |(insert 6 (3 4 5 8 9))
| | (insert 6 (4 5 8 9))
| | |(insert 6 (5 8 9))
| | | (insert 6 (8 9))
| | | (6 8 9)
| | |(5 6 8 9)
| | (4 5 6 8 9)
| |(3 4 5 6 8 9)
| (2 3 4 5 6 8 9)
|(insert 7 (2 3 4 5 6 8 9))
| (insert 7 (3 4 5 6 8 9))
| |(insert 7 (4 5 6 8 9))
| | (insert 7 (5 6 8 9))
| | |(insert 7 (6 8 9))
| | | (insert 7 (8 9))
| | | (7 8 9)
| | |(6 7 8 9)
| | (5 6 7 8 9)
| |(4 5 6 7 8 9)
| (3 4 5 6 7 8 9)
|(2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9)