12.3 The Factorial Function

To compute the product of the integers 1 to k using the divide and conquer approach, we have, as in Section 12.1, two cases.

1. Base case.

   When there are no integers to be multiplied, the result should be one.

2. Smaller, but identical, problem.

   When there are k (k>0) integers, the solution may be written as k*factorial(k-1).

Following are the Scheme and J programs for computing the product of the integers 1 to k.

(define factorial
  (lambda(n)
    (if (= n 0)
      1
      (* n (factorial (- n 1))))))

Program factorial (Scheme Version)

factorial =: monad define script
if. y. = 0
  do. 1
  else. y. * factorial y. - 1
end.
)

Program factorial (J Version)

As in Section 12.1, we can trace the execution of factorial.

> (trace factorial)
#<unspecified>
> (factorial 6)
"CALLED" factorial 6
 "CALLED" factorial 5
  "CALLED" factorial 4
   "CALLED" factorial 3
    "CALLED" factorial 2
     "CALLED" factorial 1
      "CALLED" factorial 0
      "RETURNED" factorial 1
     "RETURNED" factorial 1
    "RETURNED" factorial 2
   "RETURNED" factorial 6
  "RETURNED" factorial 24
 "RETURNED" factorial 120
"RETURNED" factorial 720
720