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.

Python Programming Engineering Guidelines


Install executable package into a directory (example: /apps/my-app) instead of site-packages


Script Python
1. Keep all statements, functions, classes in one module (your script !) . No relative imports is allowed.
2. function main() is not needed.

Package Python (package name maintained)
1. Keep the overall package layout flat. The package name is the only entry point of all module imports, use absolute imports only, sub-packages are generally accepted but not encouraged.
from mypackage.mymodule import myfunction
2. Expand sys.path in the module that contains main()

Package Python (package name not maintained)
1. Keep the overall package layout flat. Use relative imports (import from the same folder) only, sub-packages are generally accepted but not encouraged.
from mymodule import xxx


  1. Coding scripts (temporary):
    Put all definitions, variables, classes into one script; Or split them into several scripts if really needed (using relative import)

  2. Coding non-trivial packages:
    Split definitions, variables, classes into separate scripts; using absolute import, expand sys.path if needed.


  • Interfaces cannot have typed parameters (dynamic typing nature), which raises troubles and confusions for the users (partial due to the lack of IDE support).
  • Interfaces with a generics nature in dynamic typing system accepts arguments with different primitive types (root types). This complicates interface calls.