Mastery aspect (HL):

Recursion, obviously

Recursion is a method of implementing program loops that involves a method calling itself. In order to understand this more fully we need to consider a couple of related concepts first.

If the procedure then calls another procedure another return address is placed on the stack.

This method calls another - obtainInt.

This method, in turn, calls displayMessage

This Applet runs until there is no more stack space available (depends on how much memory your computer has)

On this page: [ runtime stack | Proper recursion | Worked example | exercises ]

Method Calls and the Runtime Stack
When a method calls another method as a program is running, the details of the first method need to be saved somewhere. for example the address of the program line following the method call is placed on a run-time stack as a return address.

The values associated with any local identifiers must also be saved.

Let's see how information can be stored on a run-time stack for the following sequence of method calls:

1 public void main()
2 {
3   int x, y, z;
4   x = obtainInt("Please input number 1");
5   y = obtainInt("Please input number 2");
6   z = x + y;
7 }
8 public int obtainInt(String m)
9 {
10   displayMessage( m );
11   item = Integer.parseInt( someTextField.getText() );
12   return item;
13 }
14 public void displayMessage(String message)
15 {
16   someLabel.setText(message);
17 }

When the first call is made to method obtainInt at line 4, the address of the next statement:

5 y = obtainInt("Please input number 2");

is pushed onto the run-time stack to be executed when the end of procedure obtainInt is encountered.

Since obtainInt then calls displayMessage:

10 displayMessage( m );

the return address of obtainInt (line 11) and the values of any local variables (the String m) are also pushed onto the runtime stack.

After the displayMessage method is executed the return address (obtainInt - line 11) is popped from the stack together with the values of any local variables.

It is perfectly possible for a method to call itself using this technique and for the value of any local variable in any one call to be preserved. Consider the following program:

//
// Non-productive recursion
//
import java.applet.*;
import java.awt.*;
import java.awt.event.*;

public class BreakDown extends Applet implements ActionListener
{
  TextArea display = new TextArea( 10, 20 );
  Button pushMe = new Button("Push");

 public void actionPerformed(ActionEvent thisEvent)
  {
    breakTheComputer(1);
  }
  /**
  * Method to demonstrate some features of
  * recursion - not good in this case!
  */
  public void breakTheComputer(int count)
  {
    display.append(" " + count + "\n");
    breakTheComputer(count + 1);
  }
  public void init()
  {
    add( display );
    add( pushMe );
    pushMe.addActionListener(this);
  }
}

Back to top

Proper recursion

breakTheComputer() is a recursive method, one that calls itself; however it lacks an important feature of all (useful) recursive procedures, it never stops executing until there is no more space on the stack causing a run-time error.

/**
* Counting up
*/
import java.applet.*;
import java.awt.*;
import java.awt.event.*;

public class PrintUpTo extends Applet implements ActionListener
{
  TextArea display = new TextArea( 10, 20 );
  Button pushMe = new Button("Push");

  public void actionPerformed(ActionEvent thisEvent)
  {
    printUpTo(1);
  }
  /**
  * Method to demonstrate some features of
  * recursion - good in this case!
  */
  public void printUpTo(int count)
  {
    if (count < 25)
    {
      display.append(" " + count + "\n");
      printUpTo(count + 1);
    }
  }
  public void init()
  {
    add( display );
    add( pushMe );
    pushMe.addActionListener(this);
  }
}

This Applet will print the numbers 24 down to 1 in the TextArea.

This is because at the first call with count =1, the if statement causes another call to printUpTo() with count at 2, then another with count at 3 and so on.

As these values are pushed on to the stack so is the address of the closing brace } statement, ready to be popped of the stack together with the value of number when the recursion finally "bottoms out" with number at 25.

So the 24 stacked up display.append statements are then executed. Had we written the program like this:

public void printUpTo(int count)
{
  if (count < 25)
  {
    printUpTo(count + 1);
    display.append(" " + count + "\n");
  }
}

We would have got a different result.

Exercise

Verify that changing the order of the two statements in printUpTo produces a different result. Explain why.

Back to top

A Worked Example
On the face of it we could have produced a much simpler Applet to display numbers from 1 to 24 or even from 24 to 1 using a for .. do loop or other iterative method.

Recursion can produce elegant solutions to problems in a limited number of cases. First some more examples to help understanding of the concept:

Consider the case of calculating the factorial of a given number. A factorial can most easily be defined by a couple of examples:

4 factorial, written 4! is 4 x 3 x 2 x 1

7 factorial written 7! is 7 x 6 x 5 x 4 x 3 x 2 x 1

and so on, in general,

n! = n x (n-1) x (n-2) x (n-3) ... x 1

or looked at recursively

n! = n x (n-1)!

However, this is not the whole story or we could get something like:

3! = 3 x 2!

2! = 2 x 1!

1! = 1 = 0!

0! = 0 * -1!

and so on without end. T herefore we need a base case - something to tell us when to stop. For factorials we stop at 0, ie the base case is

0! = 1 (by definition)

Thus 1! = 1 x 0!, but 0! = 1 by definition, therefore 1! = 1 x 1 = 1. And so on.

So a complete definition (applying factorials only to positive integers) is:

0! = 1

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

This translates fairly easily into a recursive method, as follows:

/**
* Method to return a factorial
*
* pre: n >= 0
* post: the factorial is returned if there is no overflow condition
*
* @param n the number to calculate a factorial of
* @return the factorial
*/
public int factorial(int n)
{
  if (n == 0)
  {
    return 1;
  }
  else
  {
    return n * factorial(n - 1);
  }
}

Back to top

Exercises

A power function can be defined as follows:

power(x, n) is equivalent to x^n

where x is a real number and n is an integer. The ^ symbol indicates an exponent.

Of course, we see that:

x^n = x * x^(n-1) and so on.

or recursively:

x^n = x when n = 1

x^n = x * x^(n-1) when n > 1

1) Write the recursive method power(x, n).

2) Evaluate power (1.2, 3)

The Fibonacci sequence can be defined as follows:

FIBO(1) = 1

FIBO(2) = 2

FIBO(n) = FIBO(n-1) + FIBO(n-2) for all n > 2

1) Write the recursive function FIBO

2) Evaluate FIBO(8)

The following example, involving two variables, is unlikely to appear in examination questions (although it did occur in the distant past).

Ackermann's function A(m,n) is defined as follows:

ACKER(m,n) = n + 1 if m = 0

ACKER(m,n) = A(m-1,1) if n = 0

ACKER(m,n) = A(m-1, A(m, n-1)) otherwise

3) Write the recursive function ACKER

4) Evaluate ACKER(3,2)

Back to top

Special note

Related: [ Java home | Previous: queues | Next: trees ]

A lot of dossiers seen by the examiners give very poor/trivial examples of recursion.

Many times we see the use of recursion to obtain a value until some validation condition (eg a range check) is passed. It can't be emphasized too strongly that this is a poor, trivial and usually incorrect way of demonstrating mastery of recursion.

See the May 2006 Subject Report for further information.

Available online at the Online Curriculum Centre.

Questions or problems related to this web site should be addressed to Richard Jones who asserts his right to be identified as the author and owner of these materials - unless otherwise indicated. Please feel free to use the material presented here and to create links to it for non-commercial purposes; an acknowledgement of the source is required by the Creative Commons licence. Use of materials from this site is conditional upon your having read the additional terms of use on the about page and the Creative Commons Licence. View privacy policy.