As Danny taught us in the class, the way to understand recursion is similar to the principal of induction in mathematics. The way to trace a recursive code goes through tracing easier cases and then substituting their results into our case.
The principal of induction is used to prove various properties in mathematics. There are two steps in the proof: base case and the induction step. In base case we show that the property holds for a small natural number and in the induction step we show why the property holding for a natural number n implies that it will also hold for a natural number n+1. And that is also the key point with the recursion.
It is impossible to trace the recursive code with some depth, since human cannot think as systematically as computers. So solving a problem on an easier case and seeing the connection between a higher case and our case is enough to trace the code.
Now that I have talked about the recursion more, I can share one of the algorithm paradigms based on recursion:
Divide and conquer algorithm
Divide and conquer algorithms are mostly used with multiple recursive steps to solve a difficult problem. As its name suggests, a hard problem is divided into smaller sub-problems which can be solved and then combined to reach the answer of the harder problem. Here are the steps to a generic divide and conquer algorithm:
1- Divide problem into sub-problems
2- Solve sub-problems recursively
3- Combine solutions from 2nd step to get the final answer
I will give few divide and conquer algorithm examples in my following post!
No comments:
Post a Comment