九，算法-递归
定义
递归函数就是调用自身的函数，无限递归是没有意义的，因此在递归中必须有基准情形。递归术语中，函数不再递归的情形就是基准情形。每个递归函数至少需要一个基准情形才能避免无限调用。
阅读递归代码
- 辨认基准
- 用基准情形分析代码步骤
- 找出基准情形的前一步
- 基于前一步情形分析代码步骤
- 重复过程
从基准情形慢慢向上分析是理解递归的好方法。
递归的执行
计算机使用栈来调用函数，栈顶表示最近调用的函数。碰到无限递归时，计算机把同一个函数不断地压进调用栈，导致计算机的短期存储被耗尽，这就是栈溢出错误。
书写递归代码
首先，递归可以用来解决以下几类问题：
- 重复执行的问题；如打印目录；
- 计算；即根据子问题进行计算；以计算阶乘为例，可以使用循环，也可以使用递归，即子问题和原问题相同，但输入更小，如下：
unsigned long long factorialByCycle(int n) {if (n < 0) {throw std::invalid_argument("Negative numbers have no factorial.");}unsigned long long result = 1;for (int i = 2; i <= n; ++i) {result *= i;}return result;
}unsigned long long factorialByRecursion(int n) {if (n < 0) {throw std::invalid_argument("Negative numbers have no factorial.");}if (n == 0 || n == 1) {return 1;}return n * factorialByRecursion(n - 1);
}//from bottom to top situation
unsigned long long factorialByRecursion2(int n, int i=0, int result = 1) {if (n < 0) {throw std::invalid_argument("Negative numbers have no factorial.");}if (n > i) {return result;}return factorialByRecursion2(n, i+1, result*i);
}以上两种实现阶乘的方式，也代表了两种计算方法，即：自下而上得出答案（迭代或者递归）和自上而下得出答案（递归实现，且是唯一方法）。自上而下的方法如果用递归实现，则需要额外参数，如示例中的factorialByRecursion2。
自上而下递归
递归提供了一种不同的角度来思考问题，即可以在不知道如何解决问题的情况下解决该问题，其过程如下：
- 将要实现的递归函数当成已经实现完成的函数，可以直接使用；
- 分辨子问题；
- 在子问题上调用递归函数，查看其结果，并以此为基础继续。
当需要实现一些比较复杂的问题时，可以通过递归帮助思考（即自上而下）。以台阶问题为例：假设有N级台阶，一个人每次可以上1级、2级、3级台阶。那么爬到顶端，共有多少种路径。
如果以自下而上的方式研究这个问题，则情况会变得复杂，以爬上4级台阶为例，自下而上的分析过程如下：
- 只有一级台阶，则路径只有一种；
- 只有两级台阶，路径有2种路径，即
1，1 2 - 只有三级台阶，路径有4种路径，即
1,1,1 1,2 2,1 3如果四级台阶，则有7种路径。如果要爬11级台阶，则用这种方式穷举，将会比较复杂、费劲。
如果使用递归的自上而下的思考方法，那么我们先要分析子问题即可。以11级阶梯为例：
- 因为每次爬取的阶梯数是1级、2级和3级，则爬到11级台阶则可能有三种情况：从第10级台阶直接爬上来；从第9级台阶直接爬上来；从第8级台阶直接爬上来；
- 先分析从第10级台阶直接爬上来，如果从第10级台直接阶爬到第11级台阶，那么就不可能从第9级台阶直接爬到第11级台阶，同理从第9级台阶直接爬到第11级台阶，那么这条路径就不可能包括从第10级台阶爬到第11级台阶这一步；
- 再分析从第9级台阶直接爬上来，如果从第9级台阶直接爬到第11级台阶，那么就不可能从第8级台阶直接爬到第11级台阶，同理从第8级台阶直接爬到第11级台阶，那么这条路径就不可能包括从第9级台阶爬到第11级台阶这一步；
综上，爬到11级顶楼的路径是爬到第10、9、8级台阶的路径之和，除此之外没有其他可能路径，因为从第7级无法直接到达第11级台阶，因此函数定义如下：
int numberOfPaths(int n) {return numberOfPaths(n-1) + numberOfPaths(n-2) + numberOfPaths(n-3);
}接下来就是要确认基准情形。按照对子问题的分析，其基准问题即位n=3,2,1时的情景。一种方式是硬编码：
int numberOfPaths(int n) {if (n < 0) {return 0;}else if (n == 1) {return 1;}else if (n == 2) {return 2;}else if (n == 3) {return 4;}return numberOfPaths(n-1) + numberOfPaths(n-2) + numberOfPaths(n-3);
}还有一种方式是，由结果反推，首先是最基准的情形，即n=1时，返回1；当n=2时，返回2，其结果由numberOfPaths(1) + numberOfPaths(0) +numberOfPaths(-1)决定，由于numberOfPaths(1)=1，则可以推导numberOfPaths(0) +numberOfPaths(-1)= 1，假设numberOfPaths(0) = 1，则numberOfPaths(-1)=0；当n=3时，返回4，其结果由numberOfPaths(2) + numberOfPaths(1) +numberOfPaths(0)决定，由于numberOfPaths(2) = 2，numberOfPaths(1) = 1，numberOfPaths(0) = 1，由此计算numberOfPaths(-1)=0，则前后吻合，按照这种分析则可以得出另一种形式的代码：
int numberOfPath2s(int n) {if (n < 0) {return 0;}else if (n == 1 || n == 0) {return 1;}return numberOfPaths(n - 1) + numberOfPaths(n - 2) + numberOfPaths(n - 3);
}