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