什么是递归

一句话理解

递归是函数直接或间接调用自己。

为什么要学

把大问题拆成同样形式的小问题，树、搜索、分治都会用。

讲解

递归必须有更小的规模，并且有终止条件。否则会无限调用直到爆栈。

可以先用数学归纳法想：最小情况怎么做，以及“假设更小的对了，当前怎么用它”。

例子

int f(int n) {
    if (n == 0) return 1;
    return n * f(n - 1);
}

这是阶乘。f(3)=3f(2)=32f(1)=321f(0)=6。

常见错误

• 没有终止条件。
• 规模没有变小，比如 f(n) 调用 f(n)。