I have the following mathematical expression:
; f(n) = f(n - 1) + f(n - 2) where n >= 2
; f(n) = n where n < 2`
Which I translated into a normal recursive LISP call:
(define (f n)
(cond ((< n 2) n)
(else (+ (f (- n 1))
(f (- n 2))))))
How would I translate the above into a tail-recursive procedure? I'm not used to functional programming so I'm struggling a bit.
(The following code is written and tested in Racket.)
Start with the naive version:
;; fib : nat -> nat
(define (fib n)
(cond [(= n 0) 0]
[(= n 1) 1]
[else (+ (fib (- n 1)) (fib (- n 2)))]))
As we develop new versions, we can use test to see if they agree with the initial fib (at least on the numbers 0 through 9).
;; test : (nat -> nat) -> boolean
;; Check that the given function agrees with fib on 0 through 9
(define (test f)
(for/and ([i (in-range 10)])
(= (f i) (fib i))))
First, the crucial observation that enables everything else is that when we compute (fib N), we have computed (fib (- N 1))... but we discard it, and so we have to recompute it again later. That's why naive fib is exponential-time! We can do better by keeping it around, say with an auxiliary function that returns a list:
;; fib2list : nat -> (list nat nat)
;; (fib2list N) = (list (fib (- N 1)) (fib N))
(define (fib2list n)
(cond [(= n 1) (list 0 1)]
[else (let ([resultN-1 (fib2list (- n 1))])
(let ([fibN-2 (first resultN-1)]
[fibN-1 (second resultN-1)])
(list fibN-1
(+ fibN-2 fibN-1))))]))
;; fib2 : nat -> nat
(define (fib2 n)
(cond [(= n 0) 0]
[else (second (fib2list n))]))
(test fib2) ;; => #t
The fib2list function stops at 1, so fib2 handles 0 as a special (but uninteresting) case.
We can rewrite this in continuation-passing style (CPS) to make it tail recursive:
;; fib3k : nat ((list nat nat) -> nat) -> nat
(define (fib3k n k)
(cond [(= n 1) (k (list 0 1))]
[else (fib3k (- n 1)
(lambda (resultN-1)
(let ([fibN-2 (first resultN-1)]
[fibN-1 (second resultN-1)])
(k (list fibN-1
(+ fibN-2 fibN-1))))))]))
;; fib3 : nat -> nat
(define (fib3 n)
(cond [(= n 0) 0]
[else (fib3k n (lambda (resultN)
(let ([fibN-1 (first resultN)]
[fibN (second resultN)])
fibN)))]))
(test fib3) ;; => #t
Now instead of making a non-tail recursive call, fib3k calls itself with an extended continuation that takes a list result. The continuation k of (fib3k N k) is called with a list equivalent to (list (fib (- N 1)) (fib N)). (Thus if the first argument is (- n 1), the continuation argument is named resultN-1, etc.)
To start everything off, we provide an initial continuation that takes the result resultN; the second element is equal to (fib N), so we return that.
Of course, there's no reason to keep packaging things up as a list; we can just make the continuation take two arguments:
;; fib4k : nat (nat nat -> nat) -> nat
(define (fib4k n k)
(cond [(= n 1) (k 0 1)]
[else (fib4k (- n 1)
(lambda (fibN-2 fibN-1)
(k fibN-1
(+ fibN-2 fibN-1))))]))
;; fib4 : nat -> nat
(define (fib4 n)
(cond [(= n 0) 0]
[else (fib4k n (lambda (fibN-1 fibN) fibN))]))
(test fib4) ;; => #t
Notice that there are only two variants of continuation in the program---they correspond to the two occurrences of lambda in the code. There's the initial continuation, and there's a single way of extending an existing continuation. Using this observation, we can transform the continuation functions into a context data structure:
;; A context5 is either
;; - (initial-context)
;; - (extend-context context5)
(struct initial-context ())
(struct extend-context (inner))
Now we replace the expressions that created continuation functions (ie, the lambdas) with uses of the context constructors, and we replace the (single) site that applied a continuation function with a new explicit apply-context5 function that does the work previously done by the two lambda expressions:
;; fib5ctx : nat context5 -> nat
(define (fib5ctx n ctx)
(cond [(= n 1) (apply-context5 ctx 0 1)]
[else (fib5ctx (- n 1)
(extend-context ctx))]))
;; apply-context5 : context5 nat nat -> nat
(define (apply-context5 ctx a b)
(match ctx
[(initial-context)
b]
[(extend-context inner-ctx)
(apply-context5 inner-ctx b (+ a b))]))
;; fib5 : nat -> nat
(define (fib5 n)
(cond [(= n 0) 0]
[else (fib5ctx n (initial-context))]))
(test fib5) ;; => #t
(When compilers do this, they call it defunctionalization or closure conversion, and they do it to turn indirect jumps into direct jumps.)
At this point, it's really obvious that the context data type is totally boring. In fact, it's algebraically equivalent to the natural numbers! (A natural number is either zero or the successor of a natural number.) So let's just change the context data type to use natural numbers rather than some heap-allocated structure.
;; A context6 is just a natural number.
;; fib6ctx : nat context6 -> nat
(define (fib6ctx n ctx)
(cond [(= n 1) (apply-context6 ctx 0 1)]
[else (fib6ctx (- n 1)
(+ ctx 1))]))
;; apply-context6 : context6 nat nat -> nat
(define (apply-context6 ctx a b)
(cond [(= ctx 0)
b]
[else
(apply-context6 (- ctx 1) b (+ a b))]))
;; fib6 : nat -> nat
(define (fib6 n)
(cond [(= n 0) 0]
[else (fib6ctx n 0)]))
(test fib6) ;; => #t
But now it's obvious that fib6ctx just counts ctx up as it counts n down to 1. In particular:
(fib6ctx N M) = (fib6ctx 1 (+ N M -1))
= (apply-context6 (+ N M -1) 0 1)
and so
(fib6ctx N 0) = (apply-context6 (+ N -1) 0 1)
So we can get rid of fib6ctx entirely.
;; apply-context7 : nat nat nat -> nat
(define (apply-context7 ctx a b)
(cond [(= ctx 0)
b]
[else
(apply-context7 (- ctx 1) b (+ a b))]))
;; fib7 : nat -> nat
(define (fib7 n)
(cond [(= n 0) 0]
[else (apply-context7 (- n 1) 0 1)]))
(test fib7) ;; => #t
And that's the traditional iterative version of Fibonacci, except that apply-context7 is usually called fib-iter or something like that, and most versions count up instead of down and hope they get the comparison right so they don't get an off-by-one error.
You are talking about established example of tail recursive transformation for computing Fibonacci numbers. You can find excellent description with code samples at this chapter of SICP.
