52Python递归函数

52 Python递归函数 一、什么是递归 在函数内部调用自己的函数。 递归函数的特点是在函数内部调用自身， 通过反复调用自身来解决问题。 需要注意的是，在使用递归函数时，要确保有明确的递归终止条件，以避免无限递归的情况发生。 二、理解递归： 递归算法是一种直接或间接调用自身函数或者方法，直到某个条件（也称为终止条件或基线条件） 匹配的算法。 递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。 递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。定义看起来太深，通俗点说，只要一个方法（函数）里面调用了自身，这个方法就用到了递归算法。 但是这里还有一个条件，就是在使用递归时，还必须有一个明确的递归结束条件，称为递归出口，否则理论上会永远持续下去，一遍又一遍地调用自己，没有任何返回。 那么究竟什么是调用自身？ 举个例子，我们经常会听大人讲这样一个故事，“从前有座山，山里有座庙，庙里有个老和尚，老和尚对小和尚说，从前有座山，山里有座庙，庙里有个老和尚”。只要不加以限制，这个故事可以一直讲下去，就好比递归中的调用自身，只是在缺少了递归终止条件，没有出口，无限循环。 生活中的递归现象： 我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词，可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。 接下来我们举个例子来帮助理解递归过程, 当我们在电影院里想知道自己坐在哪一排，但是前面排数太多了，所以懒得数了。 于是就问自己前面的人在哪一排？这样加上 1 就是自己在的排数了，没想到的是前面的人和自己一样懒，他又问他前面的人在哪一排，巧的是整个电院的人都很懒，直到第一排的人说我是第一排，然后从第二排的人开始向后面的人传达信息，最后这一列的人包括自己就知道自己在哪一排了。 在这个过程中第一排的人就是递归出口，他需要给一个确切的数字 1，其他人才知道自己在哪，而递归的最终结果是从递归出口倒推出来的。 三、递归的特点 必须有一个明确的结束条件。 每次进入更深一层递归时，问题规模（计算量）相比上次递归都应有所减少。 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出），此时程序会抛出错误：超出最大递归深度。 递推：像上边递归实现所拆解，递归每一次都是基于上一次进行下一次的执行，这叫递推。 回溯：则是在遇到终止条件，则从最后往回返一级一级的把值返回来，这叫回溯。 四、递归案例： ①递归求和 ②递归与阶乘 求3！=3*2*1 在这个例子中，f函数接受一个整数n作为参数，并使用递归的方式计算阶乘。当n为 0 时，函数返回 1（因为 0 的阶乘定义为 1）。否则，它返回n乘以n-1的阶乘。 ③年龄问题 ④斐波那契数列 示例 ⑤赶鸭子问题（拓展） 参考代码 $$