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.
|(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)
(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)