Writing Recursion

Recursion happens when a method calls itself. This is a repetitive process that continues and progresses until a base case is reached.

There are two critical parts to a recursive method.

• A base case.
• A recursive call with a progression toward the base case.

Without a proper progression towards the base case, the code could result in infinite recursion. This is where the program continues to call the recursive method without a stopping point.

Writing Recursion

• Step 1: Determine the base case. The smallest case where the result is defined.
• Step 2: Break the problem down into smaller pieces. Where is this solution dependent on the solution of the next smaller problem? This is your recursive case.
• Step 3: Generalize the recursion. Be sure you avoid infinite recursion by progressing toward the base case.
• Step 4: Write your method.

Factorial Example

The factorial of a number, written as n!, is the product of all positive integers from 1 to n.

For example:

5! = 5 * 4 * 3 * 2 * 1

4! = 4 * 3 * 2 * 1

3! = 3 * 2 * 1

2! = 2 * 1

1! = 1

Step 1: Determine the base case

The base case is the simplest version, which is 1! since it has a defined value, which is 1.

Step 2: Break down the problem

5! = 5 * (4 * 3 * 2 * 1) or 5 * 4!

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

3! = 3 * (2 * 1) or 3 * 2!

2! = 2 * (1) or 2 * 1!

1! = 1 --- the base case

Step 3: Generalize the recursion

In general: n! = n * (n - 1)!

The generalized recursive call, progresses toward the base case of 1 by repeated subtracting 1.

Step 4: Write your method

Check for the base case:

• if the parameter passed represents the base case, return the defined value.
• if the parameter passed is not the base case, return a value with the recursive call progressing towards the base case.

Consider this example of recursion for computing a sum:

To write the factorial method, we will:

Check to see if the parameter n is 1:

• if it is, return 1
• else, `return n * factorial(n - 1)