Basic Recursion

This module covers recursion, a powerful technique in programming. You should already be familiar with loops and have some practice programming with them.

As a review, here's a while loop that will print out the numbers from 0 to 9:

int i = 0;
while(i < 10){
  System.out.println(i);
  i++;
}

Basic Recursion

In programming, a function, or method, often calls other functions. Recursion is simply a function (or method) that calls itself. For example, here's a function that calls itself and prints a number each time:

public void recurse(int i){
    System.out.println(i);
    recurse(i+1);
}

If we now call recurse(0), the function will repeatedly call itself, printing higher numbers each time. It would go on forever like an infinite loop, except the computer runs out of resources and it causes a StackOverflow Error.

To prevent this, we need to add in a stopping condition, or base case, to tell the code to stop:

public void recurse(int i){
    if(i==10){
        //do nothing
    }
    else{
        System.out.println(i);
        recurse(i+1);
    }
}

We can now call recurse(0) and it will print the numbers from 0 to 9.

Question: That's just like the loop before, what's the point of recursion?
Answer: In this case, there's no point. Be patient...

Somewhat useful Recursion

The factorial of a number (used in permutations) is a number multiplied by all the positive integers less than it. The factorial of a number N is written as N! Here's some factorial examples:

	formula	result
1!	1	1
2!	2*1	2
3!	3*2*1	6
4!	4*3*2*1	24
5!	5*4*3*2*1	120

Notice that the Factorial of a number is simply equal to that number multiplied by factorial of the number below it. For example 5! = 5*4! and 4! = 4*3!.

This means you can write a simple recursive function to define factorial:

int factorial(int n)
{
   return n * factorial(n - 1);
}

To prevent this function from going on forever, we need to again add in a base case. If the number involved is 1, we want to return 1 instead of 1 * 0. So we add in a condition:

public int factorial(int n) {
    if(n==1){
        return 1;
    }
    else{
        return n * factorial(n-1);
    }
}

We can now call factorial of positive integers and it will return the correct answer. For example, let's call factorial(5).

The computer will run through the following operations, stacking them up:

factorial(5) = 5*factorial(4)
 factorial(4) = 4*factorial(3)
  factorial(3) = 3*factorial(2)
   factorial(2) = 2*factorial(1)
    factorial(1) = 1

Now that it reached the "base case", it will return the results back up "the stack":

    factorial(1) returns 1
   factorial(2) returns 2*1  //2
  factorial(3) returns 3*2  //6
 factorial(4) returns 4*6 //24
factorial(5) returns 5*24 //120

so the function finally returns 120 for factorial(5).

You can try the visual Java debugger to see the Factorial Function Visualized.

In summary, since the factorial function can be defined recursively ( N! = N * (N-1)! ) it can be coded recursively in the same way. Instead of returning a simple variable, the function calls itself (with a new parameter) and returns the result of that. It's essential to define a "base case" so the function can eventually exit the loop and return the results back up "the stack".

Question: Couldn't the factorial function also be written with a loop instead of a recursive function?
Answer: Yes, but the code wouldn't be as clean, since you would need to create an extra variable. Recursion lets you write better code, and you'll see it's real power in the next page.

Practice Recursion with the challenge below. For extra credit, go to Loopy practice and rewrite the basic math functions using Recursion instead of loops.

public void decrease(int n){
    if(n==0){
        //do nothing
    }
    else{
        System.out.print(n+" ");
        decrease(n-1);
    }
}