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?