Recursion

What is recursion?

理解1 表象上: function calls itself (调用自己!)

理解2 实质上: Boil down a big problem to smaller ones(size n depends on size n-1, or n-2 or ... n/2)

• 把size为n的问题分解成size为n-1，n-2或者n/2的问题

理解3 如何Implementation

• 1）Base Case:smallest problem to solve
• 2）Recursive rule: how to make the problem smaller (if we can resolve the same problem but with a smaller size, then what is left to do for the current problem size n)