The normal example for a recursive definition is the factorial function, so
let's not be different.
In school mathematics the symbol ``!'` is used after a number to denote the factorial of that number (and only positive integers have factorials).
*n!* is *n*-factorial, which is defined as follows:

n! = n * (n-1) * (n-2) * ... * 1 (for n >= 1)

So, *4!* is
4*3*2*1,
which is 24.
And, *5!* is
5*4*3*2*1,
which is 120.

Here's the iterative definition of a factorial function (we'll `Raise`

an exception is the number is not positive, but you can safely leave this check out if you are sure the function will be called only with positive numbers):

PROC fact_iter(n) DEF i, result=1 IF n<=0 THEN Raise("FACT") FOR i:=1 TO n result:=result*i ENDFOR ENDPROC result

We've used a `FOR`

loop to generate the numbers one to `n`

(the parameter to the `fact_iter`

), and `result`

holds the intermediate and final results.
The final result is returned, so check that `fact_iter(4)`

returns 24 and `fact_iter(5)`

returns 120 using a `main`

procedure something like this:

PROC main() WriteF('4! is \d\n5! is\d\n', fact_iter(4), fact_iter(5)) ENDPROC

If you're really observant you might have noticed that *5!* is
5*4!,
and, in general, *n!* is
n*(n-1)!.
This is our first glimpse of a recursive definition--we can define the factorial function in terms of itself.
The real definition of factorial is (the reason why this is the real definition is because the `...' in the previous definition is not sufficiently precise for a mathematical definition):

1! = 1 n! = n * (n-1)! (for n > 1)

Notice that there are now two cases to consider.
The first case is called the **base** case and gives an easily calculated value (i.e., no recursion is used).
The second case is the **recursive** case and gives a definition in terms of a number nearer the base case (i.e., *(n-1)* is nearer 1 than *n*, for *n>1*).
The normal problem people get into when using recursion is they forget the base case.
Without the base case the definition is meaningless.
Without a base case in a recursive program the machine is likely to crash!
(See 16.4 Stack (and Crashing).)

We can now define the recursive version of the `fact_iter`

function (again, we'll use a `Raise`

if the number parameter is not positive):

PROC fact_rec(n) IF n=1 RETURN 1 ELSEIF n>=2 RETURN n*fact_rec(n-1) ELSE Raise("FACT") ENDIF ENDPROC

Notice how this looks just like the mathematical definition, and is nice and compact. We can even make a one-line function definition (if we omit the check on the parameter being positive):

PROC fact_rec2(n) RETURN IF n=1 THEN 1 ELSE n*fact_rec2(n-1)

You might be tempted to omit the base case and write something like this:

/* Don't do this! */ PROC fact_bad(n) RETURN n*fact_bad(n-1)

The problem is the recursion will never end.
The function `fact_bad`

will be called with every number from `n`

to zero and then all the negative integers.
A value will never be returned, and the machine will crash after a while.
The precise reason why it will crash is given later (see 16.4 Stack (and Crashing)).

Go to the Next or Previous section, the Detailed Contents, or the Amiga E Encyclopedia.