Factorial!

Perhaps the simplest example of recursion is the factorial function. In mathematical notation factorial is represented by the symbol !

Factorial can be defined as follows:

0! = 1,
n! = n(n-1)! for n > 0

This function is said to be defined recursively. The first condition needed for recursion definition is the base case. This is the point at which the recursive calls will stop. In the factorial example this will be when zero factorial (0!) is reached.

So for all cardinals greater than zero the problem of finding factorial is reduced to finding the factorial of a smaller number and then multiplying. This process of breaking the factorial problem down into finding a smaller factorial and multiplying until the smaller number is 0, i.e. the base case where the function does not make another call to itself but instead returns one. Using the Java applet on this page you can step through the factorial algorithm at work.

1. In area A the Java source code for the recursive algorithm
   used to find the factorial is displayed.  As the algorithm executes
   the current line of execution is highlighted. 
2. This animation shows pictorially how this algorithm finds
   the factorial of a given number.  Each time that a recursive call
   is made by the algorithm in A the animation is updated thus animating the
   action of the algorithm. Each time a recursive call is made a green box
   is appended showing the problem faced by that recursive call.  When
   the base case is reached (i.e. the factorial of 1) the recursive calls
   begin to return values this is animated by displaying the amount returned
   and by changing the colour of a box signifying a returned call to red.
3. This is the the levels of recursion.  This bar graph
   shows the current level of recursion, (i.e. the number of recursive calls
   on the stack) 
4. Gives a textual explanation of  the line currently under
   execution in A.  Use the speed control bar (E) to slow down the algorithm
   so that you can read each message and follow the "code walk through" at
   your own pace.
5. This speed control allows you to speed up and slow down the
   rate at which the algorithm executes. 
6. Here you can enter an integer value to find the factorial. 
   Notice that when a value of greater than 21 is entered the factorial calculated
   is a large negative number, can you explain why this might be?