We would like to illustrate the important programming pattern of recursion using the classical example to compute the faculty of a number, in our case the faculty of 5.
5! = 1 * 2 * 3 * 4 * 5
This expression can be rewritten like this:
5! = 5 * 4 * 3 * 2 * 1
The same holds true for the faculty of 4:
4! = 4 * 3 * 2 * 1
Comparing the expression to calculate the faculty of 5 with the expression to calculate the faculty of 4 reveals that the faculty of 4 is included in the faculty of 5. This allows us to rewrite our original expression:
5! = 5 * 4!
We may as well rewrite the expressions for the faculties of the other numbers:
4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1
Using A++ notation we can write therefore:
(define twenty4 (mult four six)) (faculty five) (mult five (faculty four)) (mult five (mult four (faculty three))) (mult five (mult four (mult three (faculty two)))) (mult five (mult four (mult three (mult two (faculty one))))) (mult five (mult four (mult three (mult two one)))) (mult five (mult four (mult three two ))) (mult five (mult four six)) (mult five twenty4) 120
We assume that the abstractions `mult' for multiplication, `add' for addition and the numbers from 1-6 have been defined. How this can be done will be shown later in section basic:numbers.
The lines above demonstrate how the faculty of a number can be calculated by first calculating the faculty of the preceding number. This approach can of course be repeated on the next lower level until the number 1 is reached. The faculty of 1 does not have to be calculated because it is equal to 1 by definition.