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


16.1 Factorial Example

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.