递归

我们先说递归，在定义上来讲：我们把一个直接调用自己或者通过一系列的调用语句间接调用自己的函数，称为递归函数。

我们应该还记得一个非常有名的数列：斐波那契额数列。在这里一起回忆下：假如兔子在出生两个月后就具有繁殖能力，而且一对兔子每个月能生出一对小兔子，并且假设所有兔子都不会死，那么一年以后总共有多少兔子呢？十年呢？

在这里，很容易发现的一个规律是：前两项之和等于后一项

其数学表达式为：

其代码实现非常的简洁：（我就不写注释了）

谈谈自己对递归的理解：

首先，如果某个问题你考虑用递归来解决，应该如何判断其是否适合？

- 这个问题是否能拆解为许多逻辑完全一致的小问题？

- 这个问题是否具有终止条件？

如果这两个条件都满足了，这个问题应该是可以用递归解决的，但是，递归又容易出现其他的问题，比如：

堆栈溢出，重复计算等等（不多说，坑大家一起踩，嘻嘻）

堆栈溢出的一种解决方案时限定递归条件，比如说限定其递归到哪一层就结束并返回。但是这种方案时有局限性的，只适合预估最大递归深度层数较少的时候。

重复计算是指在递归的过程中，同一个递归函数被计算了多次：比如在斐波那契额数列中，F(4)的计算需要用到F(3)，F(5)的计算也需要用到F(3)，如果递归层数足够多，是非常消耗资源的。

对于重复计算，一种解决方案是：将计算过的F(n)保存在一个散列表中，在递归过程中，检查F(k)是否被计算过，如果是，则直接从散列表中返回。

四则运算表达式求值

我们要计算：6 + （4 - 1）* 2 - 8 / 2很简单，口算就可以很快算出来（其中的“/”为除以），但是，计算机时怎么算的你知道吗？这时候，栈这种数据结构又派上用场了！

在了解计算机如何计算之前，我们先来缅怀一下想出一种不需要括号的后缀表达法而又没有以他的名字命名的波兰逻辑学家：Jan Lukasiewicz（可能是由于名字太复杂了），这种表示法被后人称为：逆波兰表示

如果以上式子用后缀表达法应该表示成什么形式呢？

6 4 1 - 2 * + 8 2 / -    ，我们称这种式子为后缀表达式

我们先来看看计算机是如何通过这个后缀表达式来计算的：

1. 初始化一个空栈，用以存储表达式上的数字和符号；

2. 表达式的6 4 1都是数字，依次进栈；

3. 下一个为符号“-”，便两次取出栈顶元素，使得1为减数，4为被减数，计算后结果为3，并将3入栈；

4. 然后是数字2，进栈；

5. 接着是符号 * ，则两次取出栈顶元素，将3 和 2做乘法运算，得到 6，将6进栈；

6. 接下来是符号“ + ”，则两次取出栈顶元素，将6 和 6做加法预算，得到12，并将12进栈；

7. 下一个是数字8 和 2，依次进栈；

8. 接着是符号“/”，则两次取出栈顶元素，将2视为除数，将8视为被除数，计算结果为4，将4进栈；

9. 最后是符号“-”，两次取出栈顶元素，计算12 - 4，结果为8；

10. 结果8出栈，栈变为空；

示意图如下：（灵魂画手）

理解了计算及如果通过栈求四则运算表达式的值，我们来谈谈这个逆波兰表示

我们先约定（其实本来就这样叫），6 + （4 - 1）* 2 - 8 / 2这种给人看的叫：中缀表达式；

而6 4 1 - 2 * + 8 2 / - 这种给计算机看的叫：后缀表达式

转化规则为：

从左到右遍历中缀表达式的数字和符号，若是数字则输出，即称为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈，一致到最终输出后缀表达式为止。

是不是看完之后有种：“你尽管讲，看得懂算我输！”的感觉？没关系，我们一步步来说，就拿上一个例子：

1. 初始化一个空栈，用来存储数字和符号；

2. 第一个数字是6，直接输出；此时输出为：6

3. 后一个是符号“+”和符号“（”，直接依次进栈；

4. 接着是数字 4 ，直接输出；此时输出为：6 4

5. 下一个是减号“-”，进栈，因为“-”的优先级比“（”低；后面是数字“1”，直接输出；此时输出为： 6 4 1

6. 后一个是右括号“）”，有右括号则输出栈顶元素“-”，直到左括号“（”出栈为止（注意：括号并不输出）；此时输出为 6 4 1 -

7. 接下来是乘号“*”，进栈，因为优先级高于栈顶符号“+”；紧接着是数字2，直接输出；此时输出为：6 4 1 - 2

8. 接着是符号“-”，其优先级低于栈顶符号“*”，则将栈顶符号出栈，将“-”与栈顶元素比较；并且此时符号“-”的优先级并不比栈顶元素“+”高，则将“+”输出，将“-”入栈；此时输出为： 6 4 1 - 2 * +

9. 接着是数字8，直接输出；后面是符号“/”，直接进栈；此时输出为：6 4 1 - 2 * + 8

10. 接着是数字2，直接输出；此时输出为：6 4 1 - 2 * + 8 2

11. 将栈中元素依次输出；此时输出为：6 4 1 - 2 * + 8 2 / -

绕晕了？

灵魂画手又来了：