How to make your recursive procedures run more quickly by taking advantage of a notion called tail recursion.
In writing recursive procedures, you may have noticed that there
are two general strategies for dealing with the result of the
recursive call: (1) you can just return the result; or (2) you can
do something with the result. For example, the
procedure just returns the result of the recursive call and the
add-to-all procedures do
something with the result (multiply by something and cons to it,
;;; STANDARD POSTCONDITIONS: ;;; Unless specified otherwise, procedures ;;; (1) do not modify their parameters ;;; (2) do not read any input ;;; (3) do not write any output ;;; Procedure: ;;; member? ;;; Parameters: ;;; A value ;;; A list of values ;;; Purpose: ;;; Determines if the value is in the list ;;; Produces: ;;; #t if it is, #f otherwise ;;; Preconditions: ;;; The parameters have the appropriate types. ;;; Postconditions: ;;; Just the standard ones (define member? (lambda (val values) (cond ( ; Nothing is in the empty list ((null? values) #f) ; If it's the first element, it's in the list ((equal? val (car values)) #t) ; Otherwise, look through the rest of the list (else (member? (val (cdr values)))))))) ;;; Procedure: ;;; factorial ;;; Parameters: ;;; n, a non-negative integer ;;; Purpose: ;;; Computes n! = 1*2*3*...*n ;;; Produces: ;;; n!, a positive integer ;;; Preconditions: ;;; n is a non-negative integer [unchecked] ;;; Postconditions: ;;; Just the standard ones (define factorial (lambda (n) (if (<= n 0) 1 (* n (factorial (- n 1)))))) ;;; Procedure: ;;; add-to-all ;;; Parameters: ;;; value, a number ;;; values, A list of numbers ;;; Purpose: ;;; Creates a new list by adding value to each member of values. ;;; Produces: ;;; A new list of numbers with the desired characterisitc. ;;; Preconditiosn: ;;; value is a number [unchecked] ;;; values is a list of numbers [unchecked] ;;; Postconditions: ;;; Just the standard ones (define add-to-all (lambda (value values) (if (null? values) null (cons (+ value (car values)) (add-to-all value (cdr values))))))
If you think about how you might simulate these by hand, you'll notice that it's harder to deal with the second type of procedures because you have to spend extra effort remembering "the stuff left to do after the recursive call is done".
In previous labs, we've seen several examples illustrating the idea of separating the recursive kernel of a procedure from a husk that performs the initial call. Sometimes we've done this in order to avoid redundant precondition tests, or to prevent the user from bypassing the precondition tests. In other cases, we saw that the recursion can be written more naturally if the recursive procedure has an additional argument, not supplied by the original caller.
We can use husk-and-kernel techniques to make some non-tail-recursive procedures tail recursive.
(define factorial ; Define a kernel that "accumulates" the previous multiplications ; as a second parameter. Now we're computing n*(n-1)*...*(m+1)*m! (letrec ((kernel (lambda (m acc) ;; (if (<= m 0) (* 1 acc) (kernel (- m 1) (* acc m)))))) (lambda (n) (kernel n 1))))
There is yet another reason for adopting tail recursion, and it has to do with efficiency. An implementation of Scheme is required to perform tail-call elimination -- to implement procedure calls in such a way that, if the last step in procedure A is a call to procedure B (so that A will simply return to its caller whatever value is returned by B), the memory resources supporting the call to A can be freed and recycled as soon as the call to B has been started. To make this possible, the implementer arranges for B to return its value directly to A's caller, bypassing A entirely. In particular, this technique is required to work when A and B are the same procedure, invoking itself recursively (in which case the recursion is called tail recursion), and even if there are a number of recursive calls, each of which will return to its predecessor the value returned by its successor. In the implementation, each of the intermediate calls vanishes as soon as its successor is launched.
However, this clever technique, which speeds up procedure calling and
sometimes enables Scheme to use memory very efficiently, is guaranteed to
work only if the procedure call is the last step. For instance,
tail-call elimination cannot be used in the
sum procedure as
we defined it in an earlier lab:
(define sum (lambda (ls) (if (null? ls) 0 (+ (car ls) (sum (cdr ls))))))
The recursive call in this case is not a tail call, since, after it returns its value, the first number on the list still has to be added to that value.
As you might expect, it is possible to write a tail-recursive version of
sum, just as we wrote a tail-recursive factorial:
(define sum (letrec ((sum-kernel (lambda (ls running-total) (if (null? ls) running-total (sum-kernel (cdr ls) (+ (car ls) running-total)))))) (lambda (ls) (sum-kernel ls 0)))
The idea is to provide, in each recursive call, a second argument, giving the sum of all the list elements that have been encountered so far: the running total of the previously encountered elements. We call these second argument the accumulator.
When the end of the list is reached, the value of the accumulator (the
running total) is returned; until then, each recursive call strips one
element from the beginning of the list, adds it to the running total,
and finally calls itself recursively with the shortened list
and the augmented running total. The ``finally'' part is important:
sum-kernel is tail-recursive.
Here is a summary of the execution of a call to this version of
(sum (list 97 85 34 73 10)) --> (sum-kernel (list 97 85 34 73 10) 0) --> (sum-kernel (list 85 34 73 10) 97) --> (sum-kernel (list 34 73 10) 182) --> (sum-kernel (list 73 10) 216) --> (sum-kernel (list 10) 289) --> (sum-kernel null 299) --> 299
Note that the additions are performed on the way into the successive calls
sum-kernel, so that when the base case is reached no
further calculation is needed -- the value of the second argument in that
last call to
sum-kernel is returned without further
modification as the value of the original call to
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Readings/tail-recursion.html
Source text last modified Mon Oct 30 11:48:16 2000.
This page generated on Mon Oct 30 11:52:02 2000 by Siteweaver. Validate this page's HTML.
Contact our webmaster at email@example.com