Recursion

Abstract

---

• Starting point: break down the big problem, and sum up the answers of sub-problems, and return it as final answer
• Progression: obtaining the answers of sub-problems
• Base case: the terminating point of recursion

Wishful Thinking!

When thinking about recursion, don’t “unroll” the recursion. Treat the Recursion Function as a magic black box. Don’t forget the base case!

递归解题思路主要还是聚焦在一个节点， 想想在这一个节点上要做点啥， 递归就像‘水波纹’把这‘做点啥’传递到其它节点上

Recurrence Function

---

• A mathematical function that is defined in terms of itself. Also known as function that calls itself during its execution
• Instead of using iteration (loops), a recurrence function breaks down a problem into smaller subproblems and solves each subproblem by calling itself

Wishful Thinking

---

• Trust the Process, instead of trying to track the execution of every single recursive call in your head, assume that the recursive call will magically do the right thing for the smaller version of the problem
• Just look at the smaller problems and the build on top of the solution of the base case

Simplifies Mental Model

Instead of getting lost in the chain of recursive calls, you focus on the relationship between the current problem and the smaller sub-problem.

Encourages Top-Down Thinking

You start with the big picture of how the problem breaks down, and the details of the base case help ground the recursive process

Calculating Factorial

Given factorial(4), we know that the smaller problem is to calculate 4 * factortial(3). With wishful thinking, we trust that our code already magically knows how to calculate the factorial(3), so in the current facrotial(4) function call, we just need to focus on multiplying 4 to the factorial(3). And the base case aka the terminating point is factorial(1) = 1.