递归函数(Recursive Function)
- 有座山，山上有座庙，庙里有个老和尚，他在讲故事，讲的是什么呢？讲的是从前有座山，山上有座庙，庙里有个老和尚，他在讲故事，讲的是什么呢？讲的是从前有座山……上面的故事形成了一种无限循环，永远也讲不完。我们可以用while循环来实现，以下是代码示例：
>>> s = "从前有座山，山上有座庙，庙里有个老和尚，他在讲故事，讲的是什么呢？讲的是" >>> while True: print(s)
上面的无限循环，虽然我们用现在的知识还无法让for循环实现，但通过技巧，也是可以用for循环实现的。在Python中，还有一种方式可以实现，那就是用递归法，它的英文名是recursive。什么是递归呢？简单地说就是在函数中调用了自己。下面我们来定义一个这样的函数：
>>> def rec(): # 定义函数
print("从前有座山，山上有座庙，庙里有个老和尚，他在讲故事，讲的是什么呢？讲的是：")
rec() # 调用自己
>>> rec()
- 上面的函数，当打印了字符串后，又调用了自己，所以它会形成无限循环。在一般的程序设计中不要使用它，否则就会“跌入无底深渊”。怎么结束这种无限循环？请看下例代码：
-
>> def rec(level): if level > 0 : print("从前有座山，山上有座庙，庙里有个老和尚，他在讲故事，讲的是什么呢？讲的是：") rec(level-1) return >>> rec(3) 从前有座山，山上有座庙，庙里有个老和尚，他在讲故事，讲的是什么呢？讲的是： 从前有座山，山上有座庙，庙里有个老和尚，他在讲故事，讲的是什么呢？讲的是： 从前有座山，山上有座庙，庙里有个老和尚，他在讲故事，讲的是什么呢？讲的是：下面我们来分析一下当调用rec(3)函数时的运行过程。
- 我们看到，当rec(3)执行时，由于3大于0，所以它会先打印并且调用rec(2)。基于同样的道理，rec(2)也是由于2大于0，它也会先打印，然后再调用rec(1)。rec(1)也是一样，一直会调用到rec(0)，由于0大于0不成立，它并不会打印，会直接运行到return返回。rec(0)运行完毕后也就意味着rec(1)运行完毕，依此类推，最后就会运行到标记为14的return语句，整个rec(3)的运行过程才结束。上面的圆形标记，从1到10是“递”的过程，从11到14是“归”的过程。通过给函数设定level参数，实现了rec(3)函数的“递”和“归”的过程。接下来分析一个经典示例，用递归法求阶乘。
阶乘(Factorial )
- 计算阶乘是递归程序设计的一个经典示例。要求出某个数的阶乘就是用那个数去乘以所有比它小的自然数(大于0)。例如，factorial(5)等价于5*4*3*2*1，而factorial(3)等价于 3*2*1。阶乘的一个有趣的特性是，某个数的阶乘等于起始数乘以比它小1的数的阶乘。例如，factorial(5)与5 * factorial(4)相同。这也就是说factorial(n) = n * factorial(n-1)。这其实是一种递归的定义，所以我们可以定义递归函数来求n的阶乘。
-
>>> def f(n): return n * f(n-1) >>> f(3)
上面定义了名为f的递归函数，当调用f(3)时，调用情况大概如下所示：
f(3) -> 3 * f(2) -> 2 * f(1) -> 1 * f(0) -> 0 * f(-1) -> -1 * f(-2)………
当运行上面的函数，程序马上会报错，错误提示为：
RecursionError: maximum recursion depth exceeded
上面表示的意思是：递归错误：超过了最大的递归深度，即超过了最多调用次数。
由于上面定义的f函数没有编写结束条件，所以理论上它会“无限”地运行下去。可是Python可不会让这种行为发生，它会对递归的调用次数进行限制，默认最多只能调用1000次。通过导入sys模块，可以用sys.getrecursionlimit命令查看最大的递归次数限制。由于1的阶乘就是1，所以n大于1递归才有意义，否则n到1了直接让它返回1即可。以下是改进的求阶乘的函数：
-
>>> def f(n): if n >1 : return n * f(n-1) else: return 1 >>> f(3) >>> 6
如果n等于3，f(3)的运行过程如下图所示
当调用f(3)时，根据条件判断语句，由于3大于1，所以它会返回 3 * f(2)，那么f(2)被调用，由于2大于1,所以它会返回2*f(1)。f(1)的结果就是1，所以2*f(1)的结果是2，那么3*f(2)的结果就是6，最后f(3)就能返回6了。
- 请给下列递归函数加上结束条件。
-
>>> def func(number): print(number) func(number-1)
下列是有错误的求自然数和的递归函数，请修改成正确的代码。
-
>>> def zsum(n): if n > 1: return n + zsum(n) else: return n
阅读下列代码，说出每行代码的意思，你能想像得出它会画大致什么图形吗？
-
from turtle import * t = Turtle(visible=False) def draw_square(t,length,level): if level > 0 : for i in range(4): t.fd(length) t.right(90) draw_square(t,length//4 ,level-1) draw_square(t,100,3)
