To tell the differences between master and novice programmers, dynamic programming is one the most important concepts that programming experts know. Actually, if you want to be competitive in programming, dynamic programming and recursion are important concepts you need to know. Algo.monster will show you how dynamic programming differs from recursion using programming examples.
Table of Contents
What is recursion?
Basically, dynamic programming and recursion are two closely related terms. It is safe to say that without knowing recursion, it’s impossible to learn dynamic programming (DP). So, let’s learn more about recursion before we get into dynamic programming.
Recursion is one programming method that allows a function to call itself. When you need to break your into multiple parts, and the outputs of each part depend on the output of another part, recursion is very helpful.
Each recursion function has two parts: code to execute in the recursive operation and base condition or termination condition. In this process, this function is called recursively until the base conditions are satisfied.
Fibonacci Series using recursion as an example in dynamic programming
Let’s look at an example that can generate the Fibonacci series.
Fibonacci Series is like this: one, one, two, three, five, eight, thirteen, twenty-one…
The Fibonacci series contains two ones at the beginning. Then, when you add two previous numbers you can get the next number from the Fibonacci sequence. This algorithm below will enable us to calculate the series.
fib (n)= 1; if n is less than 2
fib (n) = fib(n-1) + fib(n-2)
In the first line, you will see “n less than 2”, which is a base condition.
A recursive function normally can calculate the Fibonacci number, that is when the n is of a small value. Say, n=5, you will get: 1, 1, 2, 3, 5 …
However, this is what it looks like when you calculate the nth Fibonacci Number:
fib(n) = fib(n-1) + fib(n-2)
fib(n-1) = fib(n-2) + fib(n-3)
fib(n-2) = fib(n-3) + fib(n-4)
You break down the fib(n) into two subproblems: fib(n-2) and fib(n-1). Similarly, fib (n-1) is the sum of fib(n-2) and fib(n-2), which are the two subproblems of fib(n-1). As a result, recursive calls form a tree.
The Fibonacci series shows that fib(4) is being calculated twice. As a result, this calls for extra processing power to perform the same task repeatedly. Then, this is where dynamic programming comes in to solve the repetition.
The question now is: How is dynamic programming different from recursion? But first of all, let’s figure what DP is.
What is dynamic programming?
DP is one of the most important techniques to solve programming problems.
Dynamic programming deals with combinatorial optimization issues via recursively discomposing and tabulating intermediate results.
Steps of how DP solves problems
First, it divides the problem into smaller pieces. At the same time, it keeps the results of each piece in the array.
Second, during the process, DP checks if you have solved the same problem before. If the answer is yes, you can use the answers from the array without recalculating.
Third, combine the sub results into the overall optimal solution to the target problem.
Besides, it is necessary to store the solution of each subproblem in order to use it again later. The method that can complete this mission is what we call memoization.
In fact, optimizing programming code by integrating logic is the core idea of DP.
Also, multiple subproblems may be part of the same problem. With memoization, you avoid calculating the same sub-pieces twice or more. Thus, it minimizes the need for extra processing and improves efficiency greatly.
In the process of recursion, it’s common to see repetition in calculations in fib(n). When m is a large number, this causes much trouble in computing the final results. However, if we cache the fib(4) values for future reference, this is when dynamic programming is applicable. Well, this is when DP simplifies a problem.
Fibonacci Series using dynamic programming with memoization
| 1
2 3 4 5 6 7 8 9 10 11 12 |
include<stdio.h>
int fib (int n) { arrFib[100] = {0}; arrFib[0] = 1; arrFib[1] = 1; for (int i = 2; i<n; i++) arrFib[i] = arrFib[i-1] + arrFib[i-2]; return arrFib[n-1] } void main() { printf(“The Fibonacci number for index 6 = %d”, fib(6)); } |
Let’s check out the output: Fib (6)=8.
Instead of calling the function repeatedly, we calculate the Fibonacci series value and save it in a database array. As we’ve mentioned this technique of remembering previous results is memoization.
Dynamic programming is a way to trade processing time for memory space.
From the output of Fib(n), they seem to do the same job. However, they are logically different when it comes to how it solves the problem.
The Advantages of DP
DP is like a recursive programming method that reduces line code.
Dynamic programming has the advantage of fastening the processing speed, as we can use previous results directly. Without repetition in calculations, it improves efficiency.
The disadvantages of dynamic programming
As we say, it exchanges space for time. Thus, DP calls for a lot of memory to store each sub-solution. Still, not every result is what you will need later. When too much data caches, it leads to excessive memory usage.
Also, DP calls functions recursively, resulting in an increasing need for stack memory.
Dynamic programming or recursion?
First, you need to get the thinking behind dynamic programming. Split the problem into several subproblems, and store each answer for future use.
Then, we can use the previous answers without redoing if they occur again.
Finally, once you have determined the results for each subproblem, it is time to calculate the final output.
So, which should you choose?
With limited memory, and you don’t care much about processing speed, recursion is a better option than DP. When creating a phone app, there’s not much memory to spare, so, you can choose recursion to solve problems.
Dynamic programming is a way to speed up your program execution. So, when processing efficiency is what you need more, and you have enough memory at hand, dynamic programming is definitely the best choice.
Final thoughts
If you are new to programming languages, dynamic programming and recursion are two concepts to start with. Because these two ideas are common in generic programming languages. Yet, it is possible that there might be some syntactic differences in how different programming languages define and call a function recursively.