一、递归与非递归
1. 递归
递归是指函数调用函数本身，运行起来就是函数嵌套函数，层层嵌套。虽然函数调用、参数堆栈都是不小的开销，但程序简单。非递归则是不断地对参数入栈、出栈，省去了函数层层展开、层层调用的开销。虽然参数出入栈次数多了，但一般都开辟固定的足够大的内存来一次性开辟、重复使用。
2. 递归与非递归的优缺点
- 非递归是从堆栈的角度来编写程序，速度快，但代码复杂。
- 递归是从问题本身的逻辑角度来编写，虽然速度相对慢，但代码容易理解。
- 对于同一个问题，如果对速度要求不高，建议用递归方式。
3. 示例：求第n个斐波那契数、strlen、求n的阶乘、n^k、打印一个整数的每一位等
- 求第n个斐波那契数：递归和非递归实现
- 求strlen:递归和非递归实现
- 求n的阶乘：递归实现
- n^k:递归实现
- 打印一个整数的每一位：递归实现
二、递归实现DigitSum(n)
输入一个非负整数，返回组成它的数字之和(例如，调用DigitSum(1729),则应该返回1+7+2+9,它的和是19)。
```c
int DigitSum(int n) {
if (n == 0) {
return 0;
} else {
int last_digit = n % 10;
return last_digit + DigitSum(n / 10);
}
}
```
以下是重构后的内容：
1.2 递归三部曲
当我们遇到一些问题想要使用递归进行解决时，我们会发现很困难，理解看懂递归很容易，可是使用递归却非常地困难。然而递归有着一般的解题思路，我将其称为递归三部曲。
1.2.1 第一部、确定函数的功能
我们已经知道了递归就是函数直接或间接地调用本身，那么我们首先需要的就是一个函数，确定函数的功能，就是要知道这个函数要完成一件什么样的事，而这件事，是由编写函数的人自己确定的。换句话说，就是我们不需要给出这个函数内部的具体定义，只要先明白函数是用来干嘛的就可以了。
比如，我们现在需要计算一个数n的阶乘。
```c++
int f(int n) {
// TODO 具体定义
}
```
这里函数的功能就是计算n的阶乘。
1.2.2 第二部、确定递归终止条件
在1.1什么是递归中我们举了两个例子，照镜子和山上有座庙故事的例子，我们发现这两个例子都是死循环，会无休止地递归下去，这样地函数是我们需要避免写出来的，因为计算机的资源是有限的，如果递归的层次过深，就会造成“爆栈”的风险，如果不能理解什么是“爆栈”，没有关系，你可以先认为递归层次过深，内存会发生溢出。而照镜子的例子是一个无限递归，他需要的内存资源是无限的，所以这样就会发生内存溢出的风险。所以我们需要给递归确定终止条件，这样才能防止内存溢出。
我们继续看计算一个数n的阶乘的例子。我们知道当n=1时，n! = 1;所以，我们就找到了递归函数的终止条件，将上面的代码完善如下：
```c++
int f(int n) {
if (1 == n)
return n;
}
```
这样，我们就找到了递归终止条件，完成了二部曲。
.2 递推关系式
这一部分通常是编写递归函数的难点，因为它需要具备递归逻辑思维才能完成。在这里，由于我的水平有限，无法找到通用的递推关系式推导方法。如果大家对此感兴趣，可以参考相关书籍并进行相应的习题练习。
然而，在计算一个数n的阶乘的例子中，递推关系式很容易就可以找到：f(n) = n * f(n-1)。我们可以进一步完善上述代码：
```cpp
// function: 计算n的阶乘(函数功能)
// params: n为需要计算阶乘的数值
int f(int n) {
if (1 == n) // 终止条件
return n;
else
return n * f(n - 1); // 递推关系式
}
```
到这里，我们已经初步了解了如何编写递归函数的一般步骤。
1.3 尾递归
我们已经知道了什么是递归函数，即函数调用自身。那么什么是尾递归呢？
尾递归是指函数调用自身的位置位于函数最后一行，这就是尾递归。
例如：
```cpp
void func(int a, int b) {
a++;
b++;
func(a, b);
}
```
这个递归函数在末尾调用了自身，所以这是一个尾递归。
现在我们再来看上面的n的阶乘的例子：
```cpp
// function: 计算n的阶乘(函数功能)
// params: n为需要计算阶乘的数值
int f(int n) {
if (1 == n) // 终止条件
return n;
else
return n * f(n - 1); // 递推关系式
}
```
这里return n*f(n-1);是不是尾递归呢？答案是否定的。尽管这条语句位于函数的末尾，但是f(n)函数进行了运算，所以它并不是尾递归。
我们需要注意到，只有当函数本身没有参与操作，并处于末尾的时候，才是尾递归！
尾递归的作用主要是为了解决"爆栈"问题。在许多编程语言中，编译器会对尾递归进行优化，将其转换为非尾递归的形式，从而避免栈溢出的问题。详细的内容可以参考1.5函数栈部分。
下面是一些经典的递归例题及其解答：
1.4 经典递归例题
1.4.1 阶乘问题
题目：求数n的阶乘，这个问题我们已经讲过了，代码如下所示：
```cpp
// function: 计算n的阶乘(函数功能)
// params: n为需要计算阶乘的数值
int f(int n) {
if (1 == n) // 终止条件
return n;
else
return n * f(n - 1); // 递推关系式
}
```
1.4.2 斐波那契数列
题目：斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34....,即第一项 f(1) = 1,第二项 f(2) = 1.....,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。
根据递归三部曲，我们依次给出解题步骤：
(1)确定函数功能
我们假设 `fabonic(n)` 的功能是求第 n 项的值，代码如下所示：
```cpp
// function: 求第n项的值
// params: n 第n项
// return: 第n项的值
int fabonic(int n) {
// TODO 具体定义
}
```
(2)确定终止条件
我们可以知道当n=1时，`fabonic(1)=1;当n=1时，`fabonic(1)=2;所以代码如下所示：
```cpp
// function: 求第n项的值
// params: n 第n项
// return: 第n项的值
int fabonic(int n) {
if (n <= 2) // 终止条件
{
return 1;
}
}
```
.4.3 汉诺塔问题
问题：相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根柱子(编号A、B、C),在A柱自下而上、由大到小按顺序放置n个盘子(如下图)。
游戏的目标：把A柱上的盘子全部移到C柱上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根柱上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一柱上。
为了能够更好地解决这道题目，我们先通过画图来理解一下这道题目。
(1)当$n=1$时，情况如下图所示：
将1盘从A柱移动到C柱总移动次数=1
(2)当$n=2$时，我们需要进行如下移动步骤：
将1号盘从A柱移动到B柱将2号盘从A柱移动到C柱将1号盘从B柱移动到C柱总移动次数=3
(3)当$n=3$时，我们需要进行如下移动步骤：
将1号盘从A柱移动到C柱将2号盘从A柱移动到B柱将1号盘从C柱移动到B柱将3号盘从A柱移动到C柱将1号盘从B柱移动到A柱将2号盘从B柱移动到C柱将1号盘从A柱移动到C柱总移动次数=7
综上所述，我们可以得到如下函数公式：
1. 汉诺塔问题解决方案：
```cpp
void hanoi(int n, char A, char B, char C)
{
if (1 == n)
{
move(A, 1, C); // 将编号为1 的圆盘从A 移到 C
}
else
{
hanoi(n - 1, A, C, B); // 递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
move(A, n, C); // 将编号为n 的圆盘从A 移到 C
hanoi(n - 1, B, A, C); // 递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
}
}
```
至此，汉诺塔问题解决。
2. 函数栈详解：
我们知道函数的递归调用，编程实现的本质其实就是借助函数栈来实现的。我们来看一个递归函数n的阶乘的例子。
函数其实是在一个函数栈中实现运行的，栈的特点是后进先出。当我们运行f(3)这个函数时，函数运行到return n * f(n-1)这条语句时，会产生函数调用，而进行函数调用之前，需要先将函数的局部变量保存起来，也就是所谓地先将现场保存起来，然后进行参数地更新和函数调用。当函数调用完成返回时，需要将栈中的信息弹出，恢复现场，继续执行。上图其实就是函数栈。
所以当我们的递归层次越深时，函数栈需要的空间便越大(因为需要栈空间来保存局部变量等信息),所以“爆栈”的风险便越大。那么有没有办法能解决上述问题呢？
尾递归是指在函数的最末端，函数结束时调用自身，而且这个调用不会引起函数栈的增长。尾递归会导致函数栈溢出，因此需要将其转化为非递归形式。
将递归算法转换为非递归算法有两种方法：直接求值(迭代/循环),不需要回溯；不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法。
以下是重构后的代码：
```cpp
class Solution {
public:
stack
void goToLeft(TreeNode *root) //将所有左子树入栈
{
while (root != NULL)
{
stk.push(root);
root = root->left;
}
}
void *InorderSuccessor(TreeNode *root) //看这里
{
goToLeft(root); //将所有左子树入栈
while (!stk.empty())
{
TreeNode *temp = stk.top();
stk.pop();
visit(temp->val); //遍历该节点
if (temp->right != NULL)
goToLeft(temp->right); //如果右子树存在，因为右子树也是一棵独立子树，所以也要对它进行一遍这个操作进行中序遍历
}
}
};
```
总结：当递归层次不是很深时(小于1000),我们其实没有必要将其进行迭代化，迭代后的代码会比较难理解。
