函数:递归函数
递归定义:
递归是一种计算过程,如果其中每一步都要用到前一步或前几步的结果,称为递归的。用递归过程定义的函数,称为递归函数,例如连加、连乘及阶乘等。凡是递归的函数,都是可计算的,即能行的。
递归函数定义:
在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。
举例:阶乘
注意:
使用递归函数需要注意栈溢出。
在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
汉诺塔算法:
领取专属 10元无门槛券
私享最新 技术干货