How to Optimally Handle Recursion?

An intuitive explanation of Dynamic programming

What if you need to find the minimum number of coins that make up an amount with coins of different denominations? For example, if you are given 1 cent, 5 cents, and 10 cents and asked to use the minimum number of coins to make 18 cents.

The example of finding minimum coins is an optimization problem where you need to find the minimum number of coins that make up an amount. The solution needs to recursively check if the total can be reached by choosing the coin or not for every denomination.

Whenever you have recursion, there is an overhead of repeatedly making the same function calls which can result into an exponential or logarathmic time complexity problem depending on the total number of recursive calls and the complexity of operations for each recursive call. As a result the solution takes time to execute.

Is there a way to reduce the execution time and run the function optimally?

One of the ways to solve the time complexity problem where we need to find an optimal solution is to break the recursive problem into simpler sub-problems using Dynamic programming.

Dynamic programming is a technique to find an optimal solution to a complex recursive problem by breaking it down into simpler sub-problems and solving those sub-problems only once…