Java

TOPIC 33 – RECURSION

LESSON NOTE

DEFINITION

Recursion is a problem solving technique that deals with expressing a problem in terms of one or more simpler versions of itself until a base case is reached.

REAL WORLD EXAMPLE

Let’s consider the job of sorting a stack of papers. A person generally starts by taking the top paper, dealing with it or placing it in a proper location. The stack is now smaller (simpler case). This continues until the stack is completely gone (base case).

We could write the instructions for the above situation as such:

Sorting a Stack of Papers (n pages):

Take first page and place it in its proper storage location.

If pages remain in stack
{
Apply instructions on Sorting a Stack of Papers (n-1 pages)

}

Notice how the instructions on sorting a stack of papers actually references itself (red text) but with less pages. That is a simpler case. And that is recursion.

RECURSION IN PROGRAMMING

The most important and challenging step of understanding the use of recursion as a programming technique is to be able to redefine a problem using a recursive definition. This is a challenging concept to master and practice will help a lot!

In programming, recursion occurs whenever a function calls itself. We call this a recursive function call, or simply, a recursive call.

EXAMPLE – SIMPLE RECURSION

The function countdown(int n) outputs all numbers from n down to 1 on the screen.

public static void countdown(int n)
{

System.out.println(n);

if (n > 1)
{

countdown(n-1);

}

}

The above function can be called from main with a call such as

countdown(5);

and will output to screen the following:

5

4

3

2

1

EXPLANATION

The function countdown calls itself so it is a recursive function.

It is very important that you take time to understand the code. As long as n is greater than 1, the function keeps on calling itself creating a loop-like execution. The looping ends only once n is equal to 1.

ESCAPE CASE (aka BASE CASE)

In the example above, the recursive call only occurs while n > 1. The situation when the recursive call is not used is referred to as the escape case or the base case. So, in the above example, the escape case occurs when n equals 1.

For recursion to work, an escape case is required in order to stop the looping process.

STACK OVERFLOW ERROR

Students trying to use recursion for the first time often forget to code in an escape case. This leads to an endless looping execution with continuous recursive calls to the recursive function. However, this will not go on infinitely because one can only do so many function calls inside one another before Java throws a StackOverflowError.

To explain what a Stack Overflow Error is, we need to first look at what happens when a function is called. When a function call occurs, Java needs to store certain details about where the function was called from so that it can return to that location after the function is done. All this information is placed inside a memory structure called a stack. If you call many functions one inside the other, all of this data starts to fill the stack. And at one point, the stack is completely filled up and adding more information causes an error.

EXAMPLE

We will now look at a recursive function and try to understand what it will do.

Let's consider the following function:

//PRECONDITION: The variable a should be

//greater than zero.

public static int something(int a, int b)

{

if (a == 1)

{

return b;

}

else

{

return b + something(a-1, b);

}

}

The first thing we do is confirm that it is in fact a recursive function. We see that the statement inside the else has a function call back to the same function which means it's recursive.

This function can end in two ways. The first is inside the if statement. It ends with the value b. This is not recursive so this is an escape case. The second way it ends is with the recursive call inside the else.

So to figure out what this function will do, we simply pretend to call the function with made up values for a and b. Initially, it is usually best to pick values that match with the escape case.

So we will start with a test where a equals 1.

Test #1

We will examine what something(1,5) would return. Note that we chose to test a=1 and b=5.

Since a equals 1, the if statement condition will be true. So we immediately return b which is 5.

So, something(1,5) returns 5.

Test #2

The first test was very easy because I chose a=1. We will do the same again with b set to 9. Similarly, the return b statement is executed and we return 9.

So, something(1,9) returns 9.

Test #3

Ok. We have the situation when a is 1 down. The result will be whatever b is. Let's move on to a different value for a. Let's work with a equals 2 and b equals 8.

Let's work with values a=2 and b=8. So we want to evaluation something(2,8).

This is very different now. The condition of the if statement is false and we go inside the else statement.

We execute the line return b + something(a-1,b); at the end of the code.

So, we are returning 8 + something(1,8). But before we can return any value, we have to calculate what something(1,8) gives us. Thankfully, from our work in the previous tests, we know that it will give us 8.

So we are return 8 + 8 which is 16.

In conclusion, something(2,8) returns 16.

Test #4

Let's try something(3,5) to see what we get.

When we execute the bottommost statement in the function, we return

5 + something(2,5)

So we know that something(3,5) is equal to 5 + something (2,5).

Now, we evaluate what something (2,5) gives us. Again, the bottommost statement is executed.

We get something(2,5) is equal to 5 + something (1,5).

And from our above tests, we know that something(1,5) is 5.

We can now put all of the statements above together like equations.

something(3,5) = 5 + something(2,5)
something(2,5) = 5 + something(1,5)
something(1,5) = 5

So, by combining the bottom two equations from above, we get that:

something(2,5) = 5 + 5 = 10.

And then by combining that result with the top equation, we get:

something(3,5) = 5 + 10 = 15

CONCLUSION

After the four tests, we can be quite confident on what this function is doing. It is simply multiplying the value of a by b. So, something(4,9) would give us 36.

And of course, the function should be called something like multiply() instead of something().

FACTORIAL OF A NUMBER

The factorial of a number n is defined as the product of n times all over positive numbers smaller than n. We use the exclamation mark for the factorial symbol.

So, four factorial (usually written as 4!) is equal to:

4! = 4 x 3 x 2 x1 = 24

and, 8! is equal to:

8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40 320

In general, n! is equal to:

n! = n x (n-1) x (n-2) x … x 2 x 1

RECURSIVE DEFINITION OF FACTORIAL

We can also define the factorial of a number n recursively. We need to be able to express the value of factorial by a simpler case. The continual application of simplification needs to eventually lead to a base case.

We can recursively define n! in the following way:

n! = n * (n-1)! for all n > 1

1! = 1

Using the above definition we can find 4! by doing the following steps:

4! = 4 * (4-1)!

= 4 * 3! We reapply the rule for 3!

= 4 * 3 * (3-1)!

= 4 * 3 * 2! We reapply the rule for 2!

= 4 * 3 * 2 * (2-1)!

= 4 * 3 * 2 * 1! We use base case for 1!

= 4 * 3 * 2 * 1

= 24

We will look at implementing the factorial function in java in our lesson work.