Recursion

Recursion is most useful when it is used to solve problems where the structure of the problem repeats. For example, what if you wanted to find out how much space a folder on your computers uses? You could add up the sizes of all the files in that folder, but folders can also contain subfolders. So you will have to repeat the procedure (method) for each subfolder. Each subfolder can also contain subfolders.

The Base Case

very recursive method must have at least one base case which halts the recursion. This is usually an if statement that causes the recursion to stop by just giving an answer without needing a recursive method call. You could also think of it as the simplest case where you can give the answer right away. The factorial method has a way to stop the recursion (not call itself). It stops when n is equal to 0, since it just returns 1. This is the base case.

public static int factorial(int n)
{
    if (n == 0)         /* THE BASE CASE */
        return 1;
    else
        return n * factorial(n-1);
}

Tracing

To see the recursive method working, you can step through the factorial function here

Lesson Video:

Key Points:

• A recursive method is a method that calls itself.
• Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.
• Each recursive call has its own set of local variables, including the formal parameters.
• Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.
• Any recursive solution can be replicated through the use of an iterative approach.
• Writing recursive program code is outside the scope of the course and IB Exam. You will only need to understand how to trace a recursive algorithm.
• Recursion can be used to traverse String, array, and ArrayList objects.