Overlapping Subproblems
The Fibonacci sequence is a mathematical sequence of numbers that goes like this until infinity:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…
This sequence begins with the numbers 0 and 1, and each subsequent number is the sum of the previous two numbers of the sequence. For example, the number 55 was computed because it is the sum of the previous two numbers, which are 21 and 34.
The following Python function returns the Nth number in the Fibonacci sequence. For example, if we pass the number 10 to the function, it will return 55, as 55 is the tenth number in the series. (The 0 is considered the 0th number in the series.)
| | def fib(n): |
| | if n == 0 or n == 1: |
| | return n |
| | |
| | return fib(n - 2) + fib(n - 1) |
The key line in this function is the following:
| | return fib(n - 2) + fib(n - 1) |
This line sums the previous two numbers in the Fibonacci series. It’s a beautiful recursive function.
However, alarm bells should be going off in your head right now because our function calls itself twice.
Let’s take the computation of the sixth Fibonacci number, for example. The function fib(6) makes a call to both fib(4) and fib(5), as shown in the following diagram:
As we’ve seen, a function calling itself twice can easily lead us down the road to O(2N). Indeed, here are all the recursive calls made by fib(6) shown in the .
You’ve got to admit, O(2N) can look pretty scary.
While one simple change worked to optimize the first example in this chapter, optimizing our Fibonacci sequence isn’t as simple.
And that’s because there isn’t just one single piece of data we can save in a variable. We need to calculate both fib(n - 2) and fib(n - 1) (as each Fibonacci number is the sum of those two numbers), and storing the result of one won’t alone give us the result for the other.
This is a case of what computer scientists call overlapping subproblems. Let’s unpack that term.
When a problem is solved by solving smaller versions of the same problem, the smaller problem is called a subproblem. This concept isn’t new—we’ve been dealing with it frequently throughout our discussion of recursion. In the case of the Fibonacci sequence, we compute each number by first computing the smaller numbers in the sequence. The computations of these smaller numbers are the subproblems.
What makes these subproblems overlapping, though, is the fact that fib(n - 2) and fib(n - 1) end up calling many of the same functions as each other. Specifically, fib(n - 1) ends up making some of the very same calculations already made by fib(n - 2). For example, you can see in the previous diagram that fib(5) calls fib(3) even though fib(4) has itself already done so. Many other calls are duplicated too.
Well, it seems that we’re at a dead end. Our Fibonacci example requires us to make many overlapping function calls, and our algorithm oozes along at a pace of O(2N). There’s just nothing we can do.
Or is there?
