Dynamic programming and excursion are both important programming concepts that you should learn at AlgoMonster to prepare for competitive programming.
Recursion: repeated application of the same approach to sub-problems of the same problem type. Dynamic programming is to cache the results of the subproblem. They can solve each subproblem once.
What is Recursion?
Dynamic programming (DP) and recursion are terms highly reliant on.
Recursion is a programming technology that calls itself a programming function.
Recursion is very useful if your programs have to be divided into several parts, and the output of the first part depends on the previous position.
[Example] Recursion of the Fibonacci series.
Take an example for a Fibonacci series generation:
Series of Fibonacci: 1, 1, 2, 3, 5,…
First, in the Fibonacci series, there are two numbers. Then, adding the previous two digits of the Fibonacci sequence are used to calculate the next number.
By formulating the problem as below algorithm, we can calculate this number.
fib (n) = 1; if n < 2
fib (n) = fib(n-1) + fib(n-2)
“n < 2” is a basic condition here in the first line.
A recursive function call calculates the Fibonacci number.
This is how it looks, if 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)
fib(3) = fib(2) + fib(1)
The fib(n) is divided into fib(n-1) and fib(n-2) sub-problems .
The tree forms recurrent function calling.
Recursion of the Fibonacci series in C:
For the Fibonacci series, we can write the recursive C program as follows;
| 1
2 3 4 5 6 7 8 9 |
#include<stdio.h>
int fib (int n) { if (n < 2) return 1; return fib(n-1) + fib(n-2); } void main() { printf(“The Fibonacci number for index 6 = %d”,fib(6)); } |
PRODUCT:
The Fibonacci number for index 6 = 8
It’s all a programming recursion.
Looking at the above diagram of Fibonacci, you can see that fib(4) is calculated twice. It means that two additional processing power carries out the same task repeatedly. It is where dynamic programming is required.
The question now is, how different is the dynamic programming of recursion.
What’s recursion?
It is one of the special methods to resolve questions on programming.
DP is usually used to fix problems that involve the next steps;
- Divide the problem into several small issues. Maintain the range of small problem results.
- Fuse the results of the subproblem into the outcome to save the data. It is called a memorization process.
Dynamic programming mainly aims at logically optimizing the programming code.
Several subproblems may contain this problem. It reduces the additional workload.
Example] Dynamic Programming of the Fibonacci Series.
Look at the picture above. Many values are repeatedly measured in recursion as fib (4).
It gives additional overhead processing to calculate the Fibonacci value for 4.
What if we store and use the fib(4) calculated value next time?
Fibonacci Series using Dynamic Programming approach 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)); } |
PRODUCT:
The Fibonacci number for index 6 = 8
We calculate the value of the Fibonacci series and store it in the database array.
We trade memory space here for processing time in dynamic programming.
Difference between dynamic and recursion programming.
You look at the final output of the program, recursion, and dynamic programming. They are similar.
Dynamic Programming advantages over recursion
- It reduces the line code.
- One of the main advantages of dynamic planning.
Dynamic programming disadvantages over recursion.
It has some disadvantages, which include;
- It needs a lot of memory to store the calculated results of each subproblem without ensuring whether or not the stored value is used.
- The output value is stored many times.
- Functions are recursively named in DP. The memory stack continues to grow.
- Divide the problem into several subproblems and save each problem’s results.
Now decide what your program should use.
- You can use recursion if you have limited memory for executing the code and don’t bother about processor speed.
- Use dynamic programming if you want to run your program quicker and do not have memory limitations.
Recursion and dynamic programming are key concepts for mastering any language.
These are generic concepts, and you can see them in most of the genre. In different programming languages, there can be a syntactic difference in the definition and recurring function.
How can I study and Master DP?
You should know the recursion to solve the dynamic programming problem. Take a good look at the recurrent problem resolution. One of the basic examples of recursive issues is the Fibonacci series.
It is essential to understand the theory of dividing a problem into sub-problems. Learn to store the results in the array.
Knowing how it is used in many of DP’s problems and practices can increase your understanding.
Practice is top of all the topics discussed here as an expert in the DP issue.
Solve as many issues as possible. It gives you a considerable understanding and logic for dynamic problems.