6.1.2 Basic Recursive Problem: Exponential

The basic premise behind recursion is that you want to simplify your problem until you get to the simplest case possible. Each recursive call should make a step towards the simplest case.

Moving To a Simple Problem

Let’s take a look at an example of how you can take a problem and simplify it. Factorial is a good place to start.

Recall that the factorial of a number is the product of that number and all the positive numbers below. For example, 4 factorial (4!) is equal to 4 * 3 * 2 * 1.

Likewise, 3! is equal to 3 * 2 * 1. 2! is equal to 2 * 1, etc.

You should notice a pattern:

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

To solve 4!, you can simply multiply 4 by 3!. To find 3!, you can call the same function that you called for 4!, but using the number 3 in your call. You keep doing this until you reach your base case.

The base case is the simplest version of the problem. Once you reach the base case, you can hardcode a solution and return it to the previous functional call. The base case is where the recursive calls stop and without a base case, you may create an infinite loop.

In this case, your base case is when you calculate 1 factorial, which is simply just 1.

Example: Take a look at this example as a function. Notice that the function has a name factorial and it gets called from the main function as factorial(4).

The base case is represented on lines 6-8, when num equals 1.

When the value of num is greater than 1, it makes a recursive call to factorial(num - 1) on line 10. You will notice on the right of the example how the recursive calls keep growing until that base case is reached.

Once the base case is reached, each recursiveCall value is populated from the function return statement, then that function call can be satisfied and returned to the next function.

1 is returned to the factorial(2) call. Then 2 * 1 is returned to the factorial(3). 3 * 2 is then returned to the factorial(4) call, and finally, 4 * 6 is returned to the main function.

Finding the Base Case

One of the challenges of recursion is finding the base case. Finding the simplest case may not always jump out at you, but here are a few things to consider.

• Oftentimes the base case for mathematical problems is zero or one. You can start by looking at solving that problem.

• When looking at other things such as strings or sequences, you still want to think about zero or one, but now it is the length of a string. You will see an example of this in the next example.

• Sometimes, there may be more than one base case. You will see this is especially true when looking at solving puzzles, as there will be a success base case and a fail base case.

Recursive Call

If you do not meet your base case criteria, then you make a recursive call. For a functional recursive problem, oftentimes your recursive call is put in your return statement.

The one rule to follow with the recursive call is that each call should take you at least one step closer to the base case.

Try This Example