廖雪峰Python02

函数：递归函数

递归定义：

递归是一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的。

递归函数定义：

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。

举例：阶乘

注意：

使用递归函数需要注意栈溢出。

在Python中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

说简单点就是计算量太大了，超出限制了。

栈溢出处理办法：尾递归

将 函数 改为 数值，当然这个办法只是理论上的，实际上也行不通，Python没有尾递归优化。

练习

移动可以用递归函数非常简单地实现。

请编写move(n, a, b, c)函数，它接收参数n，表示3个柱子A、B、C中第1个柱子A的盘子数量，然后打印出把所有盘子从A借助B移动到C的方法。

思路整理：

首先来看 的情况，其实超过个之后，利用递归函数的特性，本质上和没什么区别。

可以看到，这个游戏玩法的核心就是将最底层以上的部分（记为x）放到B，然后将最底层（记为y）放到C，最后将B的部分放到C。

继续看，x从A到B的过程其实和下A到C的过程一致，只是目标位置从C替换成了B，而x从B到C的过程也其实和下A到C的过程一致，只是将起始位置从A替换成了B。

代码如下：

其他玩法：

斐波那契数列：

参考资料：

什么是递归函数:

https://baike.baidu.com/item/%E9%80%92%E5%BD%92%E5%87%BD%E6%95%B0/5634537?fr=aladdin

汉诺塔算法: