Unnecessary Recursive Calls

Here’s a recursive function that finds the greatest number from an array:

The essence of each recursive call is the comparison of a single number (array[0]) to the maximum number from the remainder of the array. (To calculate the maximum number from the remainder of the array, we call the very max function we’re in, which is what makes the function recursive.)

We achieve the comparison with a conditional statement. The first half of the conditional statement is as follows:

This snippet says that if the single number (array[0]) is greater than what has already been determined to be the maximum number of the rest of the array (max(array[1:])), then by definition, array[0] must be the greatest number, so we return it.

Here is the second half of the conditional statement:

This second snippet says that if array[0] is not greater than the greatest number from the rest of the array, then the greatest number from the rest of the array must be the greatest number overall, and we return it.

While this code works, it contains a hidden inefficiency. If you look carefully, you’ll note that our code contains the phrase, max(array[1:]) twice, once in each half of the conditional statement.

The problem with this is that each time we mention max(array[1:]), we trigger an entire avalanche of recursive calls.

Let’s break this down for an example array of [1, 2, 3, 4].

We know that we’re going to start by comparing the 1 with the maximum number of the remaining array, [2, 3, 4]. That, in turn, will compare the 2 against the max of the remaining [3, 4], which in turn will compare the 3 against the [4]. This, too, triggers one more recursive call on the [4] itself, which is the base case.

However, to really see how our code plays out, we’re going to start by analyzing the bottom call and working our way up the call chain.

Let’s begin.

Max Recursive Walk-Through

When we call max([4]), the function simply returns the number 4. Again, this is because our base case is when the array only contains one element, as dictated by the following line of code:

This is pretty straightforward—it’s a single function call:

Moving up the call chain, let’s see what happens when we call max([3, 4]). In the first half of the conditional statement (if array[0] > max(array[1:]):), we compare the 3 to max([4]). But calling max([4]) is itself a recursive call. The following diagram depicts max([3, 4]) calling max([4]):

Note that next to the arrow, we put the label “1st” to indicate that this recursive call was triggered by the first half of the conditional statement within max([3, 4]).

After this step has been completed, our code can now compare the 3 with the result of max([4]). Since the 3 is not greater than that result (4), we trigger the second half of the conditional. (This is the code, return max(array[1:]).) In this case, we return max([4]).

But when our code returns max([4]), it triggers the actual function call of max([4]). This is now the second time we’ve triggered the max([4]) call:

As you can see, the function, max([3, 4]) ends up calling max([4]) twice. Of course, we’d rather try to avoid doing this if we don’t have to. If we’ve already computed the result of max([4]) once, why should we call the same function again just to get the same result?

This problem gets a lot worse when we move just one level up the call chain.

Here’s what happens when we call max([2, 3, 4]).

During the first half of the conditional, we compare the 2 against max([3, 4]), which we’ve already determined looks like this:

So max([2, 3, 4]) calling max([3, 4]) then, would look like this:

But here’s the kicker. This is just for the first half of the conditional of max([2, 3, 4]). For the second half of the conditional, we end up calling max([3, 4]) again:

Yikes!

Let’s dare to move to the top of the call chain, calling max([1, 2, 3, 4]). When all is said and done, after we call max for both halves of the conditional, we get what is shown in the .

So when we call max([1, 2, 3, 4]), we actually end up triggering the max function fifteen times.

We can see this visually by adding the statement, print("RECURSION") to the beginning of our function:

When we then run our code, we’ll see the word RECURSION printed to our terminal fifteen times.

Now, we do need some of those calls, but not all of them. We do need to calculate max([4]), for example, but one such function call is enough to get the computed result. But here, we call that function eight times.