p2-4-recursion 第四章递归

1. 初识递归

[x] 什么是递归？

递归是个很有趣也很有用的概念。所谓 “递归（recursion，recursive）”，就是 “用自己定义自己”，或者 “自己包含自己”。

[x] 有点抽象，能举个例子吗？

大家都听过的这个故事就是递归的经典例子：

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是这样的：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是这样的：从前有座山，……

[x] 如何用 BNF 来定义这则故事？

如果我们把这个故事叫做 A，那么 A 的定义可以写作这样：
A ::= 从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是这样的：A

[x] 什么是 BNF ？

上面这个定义里的 ::= 的意思是 “定义为”，这种语法叫巴科斯范式（BNF）。这个定义里最有意思的地方是，在 A 的定义中用到了 A 本身，如果我们把 A 的定义代入 ::= 右边出现的 A，就会出现无限循环下去的情况，这恰恰是原来那个故事的 point 所在。

[x] 如果把这个故事写成 Python 代码，会是什么样子？

大致是这样子的：

def a_monk_telling_story():
    print('从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是这样的：')
    return a_monk_telling_story()

这个简短的程序体现了递归的本质：一个函数的定义中调用了自己。不过，我们可不能真写这样的程序，因为它会无限的自我调用下去，形成 “无限循环”，或者更难听的词儿 “死循环” —— 循环到死。

2. 递归的基本概念

[x] 递归在编程中有什么用？

递归在编程中很有用。

人们很早就意识到，数学上有一类东西，很不好 “写出一个公式来计算”，但 “用自己来定义自己” 反而会很清晰和严谨；

递归表达式和通项表达式很不一样，有时候递归表达式代表了问题的本质，从递归表达式出发就可以一个一个计算出值来，而通项表达式更方便快速计算出特定某一项来，却完全看不出和最初的问题有什么关联。

[x] 阶乘的递归实现：

def f(n):
    if n == 1:
        return 1
    else:
        return n * f(n-1)

f(5)

[x] 问题在于，“在函数里调用自己” 究竟是怎样的一个实现过程？在函数调用 f(5) 之后到底发生了什么？

当 f(5) 被调用之后，函数开始运行……

因为 5 > 1，所以，在计算 n * f(n-1) 的时候要再次调用自己 f(4)；所以必须等待 f(4) 的值返回；因为 4 > 1，所以，在计算 n * f(n-1) 的时候要再次调用自己 f(3)；所以必须等待 f(3) 的值返回；因为 3 > 1，所以，在计算 n * f(n-1) 的时候要再次调用自己 f(2)；所以必须等待 f(2) 的值返回；因为 2 > 1，所以，在计算 n * f(n-1) 的时候要再次调用自己 f(1)；所以必须等待 f(1) 的值返回；因为 1 == 1，所以，这时候不会再次调用 f() 了，f(1) 返回值是 1；下一步，f(2) 返回值是 2 * 1 = 2；下一步，f(3) 返回值是 3 * 2 = 6；下一步，f(4) 返回值是 4 * 6 = 24；下一步，f(5) 返回值是 5 * 24 = 120。

至此，函数调用 f(5) 才执行完，最终返回值是 120。这个调用中 “递归（recursively）” 调用了四次 f() 自己。

[x] 试着在自己脑子里把这个过程走通。

3. 递归的终止

[x] 递归没有终止时会发生什么？

从上面的例子，我们可以发现，最终 f(1) 不再需要递归，可以直接返回一个确定的值，这一步是递归的转折点，特别重要，如果没有这个，递归就会无穷无尽地重复下去，永远得不到结果。例如：
def f(n):
    return n * f(n-1)
如果运行这个版本的 f(5)，会得到一个运行时异常 RecursionError: maximum recursion depth exceeded，因为 Python 对递归次数是有限制的，达到一定次数还没返回的递归会抛出这个异常。

[x] 写递归函数有哪些注意事项？

我们写递归函数的时候，要特别小心地确认递归的终止条件，就和循环中的退出条件一样，一定不能出现无限递归或者死循环的情况。

4. 递归的好处与代价

[x] 从理论上可以证明，所有递归（recursion）都可以改写为循环（iteration），反之所有循环也都可以用递归改写。那么我们写递归这样的算法好处是什么呢？

Alonzo Church 和 Alan Turing 两位现代计算机科学的奠基者的经典论文提供了证明，前提是内存管够。

最大的好处是清晰易懂。递归通常用于本质上就带有递归特性的问题（如前面所见的例子），递归算法几乎原样展现了问题的本质，容易理解也容易编写。

另外的好处是，对某些问题的算法，递归是最优化的，比如树型结构的遍历。

[x] 凡事有得必有失。递归的代价是什么呢？

主要代价有二：递归一般会使用更多的内存，因为每次调用自身都需要建立新函数调用所需要的环境，占用相应的资源，一直迭代到最深层开始返回才会释放这些资源，对此有些编程语言会在编译器和运行时进行优化，比如 “尾递归优化（tail-recursion optimization, TRO）”，能够将这种消耗免除，但 Python 并不支持（以后也不会支持），所以 Python 会限制递归的层次，超过就扔出 RecursiveError。

另一个代价是，有的时候递归算法不是最高效的，这涉及到算法分析，我们目前还不用深入，知道有这些代价就好。

对于我们来说，了解这种思考问题的方法，在碰到适合的问题时能多一个思路，就是相当不错的收获了。

小结

[x] 这一章讲了什么东西？

递归函数是在函数体定义中包含对自己调用的一种函数，通常用于实现某些天然具有递归性质的算法；

递归函数中必须正确设定递归终止的条件，避免出现无限递归的情况；

初步了解递归的优势和代价，在未来的学习中持续加深理解。

Logging

2020-03-04 19:30:48 initialize

xuzhengfu / pilot

p2-4-recursion 第四章递归 #34

1. 初识递归

2. 递归的基本概念

3. 递归的终止

4. 递归的好处与代价

小结

Logging

xuzhengfu / pilot

p2-4-recursion 第四章 递归 #34

1. 初识递归

2. 递归的基本概念

3. 递归的终止

4. 递归的好处与代价

小结

Logging

p2-4-recursion 第四章递归 #34