#lang racket ; Converting a simple recursive function into tail recursive form using ; continuation passing style of computation. ; In general, a simple recursive function can be written this way as a ; combinator of functions that say how to break the problem into smaller ; pieces. For example, this defines factorial recursively: (define AtBase? (lambda (x) (<= x 1))) (define BaseCase (lambda (x) 1)) (define Combine (lambda (x recursion-result) (* x recursion-result))) (define Decomp (lambda (x) (- x 1))) (define fn (lambda (x) (if (AtBase? x) (BaseCase x) (Combine x (fn (Decomp x))) ))) ; note that this is not tail recursive. The inner recursive call ; (fn (Decomp x)) ; is used to combine the result with the data available at the call ; That is, there is work to do after the recursion completes. ; Let's rewrite the function so that we not only do the recursive ; call, but also pass along the work to do on the result of the call. ; That is, we pass on the continuation of work to be done. (define fn-cc-r (lambda (x cc) (if (AtBase? x) ; compute the base case, and then continue (cc (BaseCase x)) ; recurse, and then combine the result, and continue. Note ; this is tail recursive in fn-cc-r (fn-cc-r (Decomp x) (lambda (result) (cc (Combine x result)))) ) )) (define fn-cc (lambda (x) (fn-cc-r x (lambda (result) (begin (print "Hello") (print result)))))) (fn 3) (fn-cc 3)