The fibonacci sequence 0 1 1 2 3 5 8 13, ... may be generated by the recursive definition:
(define fibonacci
(lambda (n)
(if (< n 2)
n
(+
(fibonacci (- n 1))
(fibonacci (- n 2))))))
When analyzing this recursive definition, it is useful to define a related function,
fib-work, whose value, given an input n, is the number of times fibonacci is called
when evaluating (fibonacci n). It is easy to show that fib-work may be defined
as:
(define fib-work
(lambda (n)
(if (< n 2)
1
(+ 1
(fib-work (- n 1))
(fib-work (- n 2))))))
fib-work, itself, generates the values of a kind of fibonacci sequence. If it is our goal to
evaluate either of these functions for inputs greater than 25 to 30, it is necessary to convert
these definitions to definitions which result in iterative processes. A recursive definition
for fib-work which results in an iterative process is given by the definition:
(define fib-work-iter
(lambda (n) (fib-work-iter-helper 1 1 n)))
(define fib-work-iter-helper
(lambda (a b count)
(if (= count 0)
b
(fib-work-iter-helper (+ 1 a b) a (- count 1)))))
Suppose f is a compound expression and e is a sub expression of f. The
continuation of e in f is that function of a single input x, (lambda (x) ...) which
contains the execution in f which remains to be done after evaluating the sub expression e.
This means that the value of the entire expression f may be obtained by evaluating
((lambda (x) ...) e). Continuations allow a compound expression to be factored
into an expression e which is evaluated first and a function which may be called with the
resulting value of e as an input.
The idea of a continuation may be used to define tail recursive functions. A function is tail recursive if the continuation of each recursive reference in the definition is the identity function.
Analysis of fib-work-iter reveals that the work of this definition is done by the recursive definition fib-work-iter-helper which has one recursive use of fib- work-iter-helper whose continuation is the identity function. Hence, fib-work- iter is tail recursive which means that its process is iterative. Here we are assuming that any tail recursive definition will be optimized by the Scheme system so that an iterative process will be generated. This will be true of any standard Scheme implementation. The end result of all of this is that fib-work-iter will easily evaluate the fib-work function for the input value 100. Indeed,
> (fib-work-iter 100) 1146295688027634168201