Simple Recursion

Recursion in programming means a method calls itself. To build a method like this, you need a base case—a value for which we know the answer, and that forms the basis of the rest of the recursion’s general cases (cases that we process in order to reduce our problem to a base case). A method calling itself is a pretty wild concept, but it makes much more sense once we get a few basic recursive techniques under our belt.

Maybe the most common recursion is a simple calculation of a factorial. A factorial is simply the product of a whole number multiplied by all its whole number neighbors that are less than itself and greater than zero (factorial 0 returns 1). Essentially it is our target number multiplied by its next smallest whole number neighbor, stopping at 1. For a factorial of 3, we would write 3! = 3 * 2* 1 = 6.

When we call the factorial method, factorial(n) where n is greater than a base case, factorial does not know what factorial(n-1) will return until a base case is hit somewhere down the stack. We keep recursively calling until we get to a base case then the method calls start to resolve.

So with the code below, let’s say we call factorial(3). The stack looks something like: factorial (3)–calls factorial(2)—calls factorial(1)–factorial(1) returns 1[Base case hit!]—Factorial(2) returns 2*1 (2)—Factorial 3 returns 3 *2 = 6. Factorial(3) was the first method called, but the last one resolved.



public class RecursiveExample
{
  //This factorial method multiplies an integer by the
  //next integer smaller than itself and returns the result.
  //If zero is passed in, one is returned.
  public int factorial (int n)
  {
    //Base case--if n == 0 we are finished--return one
    if (n == 0)
    {
      return 1;
    }

    //Base case--if n == 1 we are finished--return one
    else if (n == 1)
    {
      return n;
    }

    //General case--if n > 1 we need to multiply it by the factorial of
    //its next smallest neighbor.
    else if (n > 1)
    {
      return n * factorial(n-1);
    }

    System.err.println("Input Error!");

    return -1;
    }
  }

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s