
In this blog, I will use Leetcode 509. Fibonacci Number as our example to illustrate the coding logic and complexity of recursion vs dynamic programming with Python.
This project was built by Shuheng Ma. To see the full code used, find GitHub. (Feel free to star/watch/fork, a lot new code coming : )
Section 1: Introduction of Recursion and Dynamic Programming
1.1 Background
Let’s start with what is Recursion
Recursion is the process in which a function calls itself until the base cases are reached. And during the process, complex situations will be traced recursively and become simpler and simpler. The whole structure of the process is tree like. Recursion does not store any value until reach to the final stage(base case).
And Dynamic Programming is mainly an optimization compared to simple recursion. The main idea is to decompose the original question into repeatable patterns and then store the results as many sub-answers. Therefore, we do not have to re-compute the pre-step answers when needed later. In terms of big O, this optimization method generally reduces time complexities from exponential to polynomial.
1.2 How to write a recursion/dynamic programming script
Dynamic Programming and Recursion are very similar
- Both recursion and dynamic programming are starting with the base case where we initialize the start.
- After we wrote the base case, we will try to find any patterns followed by the problem’s logic flow. Once we find it, we are basically done.
- The main difference is that, for recursion, we do not store any intermediate values whereas dynamic programming do utilize that.
Let’s get a bit deeper with the Fibonacci Number.
Section 2: Example: Leetcode 509. Fibonacci Number
2.1 Problem Prompt
The Fibonacci numbers, commonly denoted
F(n)
form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from0
and1
. That is,F[0] = 0 as the first number
F[1] = 1 as our second number
And the number after that is easy to compute:
F[n] = F[n-1] + F[n-2]
How could we find F[n] with a given n?
2.2 Examples
If this is the very first time heard something called Fibonacci Number, do not worry, here are some easy examples to understand the question:
Given n = 2, F[2] = F[1] + F[0] = 0 + 1 = 1
Given n = 3, F[3] = F[2] + F[1] = 1+ 2= 3
Section 3: Two Approaches
3.3 Recursion Approach
Let’s start with the recursion approach.
3.3.1 Recursion Code
From the code above, we could see that the very first thing we do is always looking for the base case.
In this case, the base case would be F[0] = 0 and F[1] = 1, in order to achieve the effect, we explicitly wrote these two conditions under if.
And after the base case, the next step is to think about the general pattern of how the F[n] will be generated afterward. Luckily, the problem prompt already gave us the pattern:
F[n] = F[n-1] + F[n-2]
Therefore, we could simply return the result F(n) = F(n-1) + F(n-2).
3.3.2 Recursion Procedure Plot
If n =4, the script would do something similar to below:

We start from the very top where F[4] = F[3] + F[2]. And then we will try to find the value of F[3] and F[2]. Eventually, when we reach the base case where F[0] = 0 and F[1] = 1, we can simply sum it up from the bottom to the top and obtain F[4] = 3.
3.4 Dynamic Programming Approach
3.4.1 Dynamic Programming Code
From the code above, we could see that the very first thing we do is again, looking for the base case.
In this case, the base case would be F[0] = 0 and F[1] = 1, in order to achieve the effect, we explicitly wrote these two conditions under if.
And after we finish the base case, we will create an empty dynamic programming array to store all the intermediate and temporary results in order for faster computing. Since n starts from 0, we will create a list with n+1 length.
The next step is to think about the general pattern of how the F[n] will be generated afterward. Luckily, the problem prompt already gave us the pattern:
F[n] = F[n-1] + F[n-2]
Therefore, we could simply return the result F(n) = F(n-1) + F(n-2). And to be more specific:
dp[i] = dp[i-2] + dp[i-1]
And this is actually the major difference separate dynamic programming with recursion. In recursion, we do not store any intermediate results vs in dynamic programming, we do store all intermediate steps.
In order to calculate F[4], we will first calculate F[2], F[3] and store their value into the DP list we created in advance.
3.4.2 Dynamic Programming Procedure Plot

We start from the very left where F[0] =0 and F[1] = 1. And then we will try to find the value of F[4], we will find the value of F[3] and F[2] first as well as store their value into the dp_list. Eventually, when we reach the right side where F[4] = 3, we can return the final result.
Section 4: Time and Space Complexity
4.1 Big O for Recursion
For recursion, the time complexity would be O(2^n) since every node will split into two subbranches.
And the space complexity would be O(N) since the depth of the tree will be proportional to the size of n.
Below is the Leetcode runtime result for both:

4.2 Big O for Dynamic Programming
For dynamic Programming, the time complexity would be O(n) since we only loop through it once. As you can see in the dynamic programming procedure chart, it is linear.
And the space complexity would be O(N) since we need to store all intermediate values into our dp_list. So the space we need is the same as n given.
Below is the Leetcode runtime result for both:

4.2 Visualization of Time Complexity

The red line represents the time complexity of recursion, and the blue line represents dynamic programming. The x-axis means the size of n. And y-axis means the time the algorithm will consume in order to compute the result.
Section 5: Summarization and Conclusion
As a quick recap, some take away are summarized below:

From above, we could observe that, although both recursion and dynamic programming could handle the task of computing Fibonacci Number, they do have major differences in terms of processing intermediate result and time consumption. Dynamic programming uses the same amount of space but it is way faster.
Although both Algorithms do require almost the same level of difficulty of effort to understand the logic ( I wish my blog helped you a bit with that), it is rewarding after you grasp the core of the algorithm since plenty of array questions can be solved by dynamic programming elegantly and efficiently.
If you feel you fully understand the example above and want more challenge ones, I plan to use dynamic programming to solve a series of blogs for more difficult and real life questions in near future. Thanks for your reading!