Design Pattern for Recursive Functions

A design pattern is a stylized way of writing programs of a certain kind. By learning useful design patterns, you can write programs faster and with fewer errors.

A design pattern for recursive functions in Lisp is:

(define (myfun arg)
      (if (basecase? arg)
           (baseanswer arg)
           (combine arg (myfun (smaller arg)))))

In this pattern,

• (basecase? arg) is a test to determine whether arg is a base case for which the answer is known at once.

• (baseanswer arg) is the known answer for the base case.

• (combine arg (myfun (smaller arg))) computes the answer in terms of the current argument arg and the result of calling the function recursively on (smaller arg), a reduced version of the argument.

Exercise: Show how the factorial function corresponds to this design pattern.

Contents    Page-10    Prev    Next    Page+10    Index