Design and Analysis of Algorithms

Computation Models and Design by Refi nement 117

5.1 Consider the following example of a function

f : N → Z defi ned similar to the factorial func-

tion except that multiplication is replaced by

subtraction, which is not associative.

f (n) =

1if0

(1)otherwise

n

nfn

=

⎧

⎨

−−

⎩

(i) Unfold the computation, as in the exam-

ple of factorial(5) in Section 5.2.2

in the text, to show that f (5) = 2.

(ii)

Assume that you were hand-executing

f(n), what properties of f(n) would you

use to avoid deferred computations?

5.2 Show that the number of function calls

required to evaluate factorial(n) is n + 1.

5.3 Show that, in general, if you were previously

able to compute ...