Recursion v.s. Dynamic Programming

Recursive Thinking

  • Identifying for the base case: What is the easiest case ? What case(s) can I solve trivially ?
  • Redefining the difficult cases

DP Thinking

  • How can I build a path to solve a difficult case based on the easy case ?

Shared Characteristics Between Recursion and DP

Reasoning is about walking from the starting point, usually some known facts/existing materials, through a path and reach the predefined target.

The solution, which is the goal of problem solving, is the definition or description of such a path. The routine that is necessary to solve the problem is sequential in a forwarding manner because of the temporal nature of computing, however, the measure that takes to find the exact steps of such solutions may require backward reasoning. This is because the threads that leads to the target is often limited in comparison to the possible threads that can be pulled from the start point.

The logic behind recursion and dynamic programming when applied to solve a problem are both based on the inference chain, either through forwarding reasoning or backward reasoning.

When applied in the form of backward reasoning, the logic chain is built through the form of "if the goal is to reach E, then D has to be reached, etc, etc, etc".

When applied as a forward reasoning, the form changed into "From A, we can reach B, the from B we can reach C, etc, etc, etc".

The path can be found by either forwarding or backward reasoning, which are referred to recursive thinking and deduction thinking.

Recursion and DP actually refers more to the how the path is implemented than how it is discovered. Recursion is a style of software implementation as a direct translation from the backward reasoning mental procedure to the source code. DP, in comparison, is a style of algorithm implementation that reflects a way of natural forwarding reasoning.

Algorithms are the representations of logic to solve problems in the form of discrete mathematics in the context of computer science. Algorithm implementation can be strict or loose.

Why Recursion is Useful in Programming ?

Recursive programming avoids the need to write nested loops which is both difficult to understand and debug. It also improves code simplicity, Besides, recursion (make a function call in the body of itself) can implement logic that is nearly impossible to be done in loop structure by human beings.

In recursive programming, the control flow is forwarded through the change of argument values of recursive function calls. This beats loop control structure in cases when it requires that the loop counter changes in a manner other than natural incremental. Additionally, the mechanism of loop counter determines that it is not the best tool in traversalling ADTs.