Recursive Concepts
Recursion in programming is when a function (or method) calls itself.
An example is calculating the factorial of a number:
6! = 6 x 5 x 4 x 3 x 2 x 1 = 120,
but 6! also equals 6*5!,
but 5! also equals 5*4!,
and 4! also equals 4*3!,
and so on...
until 1!=1*0!, where 0!=1
Therefore, this is a recursive process that can be programmed. The program below is an example that will provide you with a better understanding of recursion. Be sure to follow the steps very, very carefully.
The best way to understand recursion is to do a tracing exercise on this program. Good luck!
Example
public class Recursion
{
public static void main(String[] args) throws IOException
{
int number = 5;
int answer = factorial(number);
//the method factorial is called, the parameter number is used
System.out.println(answer);
}
//Method: factorial
//Purpose: to calculate the factorial of a given number
//Parameters: a number
//Return: the factorial of a given number
public static double factorial(int n) //this is the recursive method
{
if (n == 0)
return 1; //if n=0, 0!=1
else
return n * factorial(n - 1);
//the above line calls its own method
//this is known as a recursive call
}
}
System Output
120
Note: In any recursive process, there must be a non-recursive termination statement (same as with looping). This termination statement will ensure that the recursion does end. Otherwise, the program will run infinitely and the program will come to a crash! KAAAABBBBBBBOOOOOOOOOOOOOOOOOOOOOOOMM!
Recursive Tracing
As you can see, recursion is extremely tedious and repetitive to fully trace by hand. As a result, most programmers just work through the first 2 to 3 steps, and because the middle steps are repeated in the same fashion, a pattern will often be formed. However, the last few steps have to be thought out as well to ensure the outcome is as planned.
If you're really stuck on a recursive problem, however, you may have to trace the whole program from beginning to end to see where the problem lies. When tracing a recursive program, you should use a slightly different technique (below) than from what is shown in the Tracing Tutorial.
In a recursive call, each time the function is called you essentially have a new set of variables, although they have the same names. For your first function call, start off by drawing a box, and in that box give all your variables and your return statement a column. If your variables change in that function call, cross them out and re-label them as you would in any other program. When you have your second function call, you draw a new box, re-labeling all of the variables. The basic premise in recursive tracing is that every time you have a new function call, you draw a new box.
| |
n |
return |
Our function call was factorial(5), so n becomes 5.
Then we see where our program goes. |
 |
5 |
|
|
|
| n |
return |
There is another function call to factorial, this time calling n-1; therefore, we make a new box, labelling
n as 4. |
|
4 |
|
|
|
| n |
return |
This keeps going until n reaches 0. |
|
3 |
|
|
|
| n |
return |
Notice the arrows leading from one function call to another. For every arrow going down, you'll see there's a matching one going back up.
|
|
2 |
|
|
|
| n |
return |
|
1 |
|
|
|
| n |
return |
This is where things get interesting. When n reaches 0, the function returns 1.
Take a look at the next diagram.
|
| |
0 |
1 |
| |
n |
return |
|
|
|
5 |
|
 |
|
|
|
| n |
return |
|
4 |
|
|
|
|
|
| n |
return |
|
3 |
|
|
2 |
|
|
| n |
return |
|
2 |
2*1 |
|
1 |
|
|
| n |
return |
|
1 |
1*1 |
|
1 |
The last call returns a 1, the second last call returns a 1, the third last call returns a 2, etc. until the walkthrough is complete. Try finishing it yourself (Hint: the first call should return 120). |
|
|
| n |
return |
| |
0 |
1 |
|
|
Multiple Function Calls
Sometimes there can more than one recursive call in a function. This makes things more complicated, but not impossible. Label all the arrows with a circled number to indicate which function call they came from, and you should be fine. Remember, for every arrow leading down to a function call, there should be one going back up. This will help you keep track of where your program is going.
Example
public class TowersOfHanoi
{
public static void main (String args [])
{
int start = 1;
int aux = 2;
int end = 3;
towers(4, start, aux, end);
}
/* Notice that towers has no return statement. When tracing, the goal
is to see what the function prints. */
public static void towers (int n, int start, int aux, int end)
{
if (n != 0)
{
towers (n-1, start, end, aux); // first recursive call
System.out.println(start + " --> " + end);
towers (n-1, aux, start, end); // second recursive call
}
}
}
System Output
1 --> 3
1 --> 2
3 --> 2
1 --> 3
2 --> 1
2 --> 3
1 --> 3
Try tracing this by hand. It may be tricky, but it's excellent practice.
Related Links
For more information on recursion, check out some useful links:
 |
Towers of Hanoi |
A description of the recursive problem. A very cool concept. |
|
|
|
|
