函数的嵌套与递归

Python语言允许在函数定义中出现函数调用，从而形成函数的嵌套调用，如下所示。

 1  def fun1():
 2      print('fun1()函数开始')
 3      print('fun1()函数结束')
 4  def fun2():
 5      print('fun2()函数开始')
 6      fun1()
 7      print('fun2()函数结束')
 8  fun2()

运行结果如下图所示。

运行结果

在上例中，第5行在fun2()函数中调用fun1()函数，程序执行时会跳转到fun1()函数处去执行，执行完fun1()后，接着执行fun2()函数中剩余的代码，如下图所示。

函数的嵌套调用执行过程.png

函数的递归调用

在函数的嵌套调用中，一个函数除了可以调用其他函数外，还可以调用自身，这就是函数的递归调用，递归必须要有结束条件，否则会无限地递归。
接下来演示函数的递归调用，如下所示。

 1  def f(n):
 2      '''
 3      计算阶乘公式：
 4          0! = 1
 5          n! = n * (n -1)!, n > 0
 6      转化为递归函数:
 7          f(0) = 1
 8          f(n) = n * f(n - 1), n > 0
 9      '''
 10     if n == 0:
 11         return 1
 12     return n * f(n - 1)
 13 print('4! = %d'%f(4))

运行结果如下图所示。

运行结果

在上例中，第10行到第12行定义f()函数用于计算阶乘，当n == 0时，程序立即返回结果，这种简单情况称为结束条件，如果没有结束条件，就会出现无限递归。当n > 0时，就将这个原始问题分解成计算(n – 1)阶乘的子问题，持续分解，直到问题达到结束条件为止，就将结果返回给调用者，然后调用者进行计算并将结果返回给它自己的调用者，过程持续进行，直到结果返回原始调用者为止。原始问题就可以通过将f(n-1)的结果乘以n得到，这种调用过程就称为递归调用，如下图所示。

函数的递归调用.png