Python的函数六

十、函数的嵌套调用和递归调用

1、函数的嵌套调用

嵌套调用是指主程序在调用某函数时，该函数中又调用了其他函数。如下图所示。其中主程序调用了函数f1(),而f1()函数的语句块中又含有调用另一个函数f2()的语句，当然函数f2()也可以继续调用另一函数f3()。这就形成了函数的嵌套调用。

【例题1】分析下列程序的调用关系,再写出程序运行后的输出结果。

def f1(n):

  s=1

  for i in range(1,n+1):

    s=s*i

  return s

def f2(n):

  s=0

  for i in range(1,n+1):

    s=s+f1(i)

  return s

 

x=5

sum=f2(x)

print(sum) 

【分析】该程序由两个函数定义和一段主程序组成，其中最后三行代码为主程序，主程序执行后时以x为参数调用了函数f2,f2函数中调用了另一函数f1,由前面的介绍不难看出f1函数的功能是求n的阶乘，而f2函数是求f1(1)+f1(2)+f1(3)+f1(4)+f1(5)各函数值的和，也就是求1至5的各数的阶乘之和。即sum=1!+2!+3!+4!+5!,

sum=1+1x2+1x2x3+1x2x3x4+1x2x3x4x5

sum=153

所以程序的最后输出结果是：153

我们也可以将f1函数的定义写在f2函数的定义的语句块内部，这样定义的f1函数，称作内部函数，只能由f2函数语句块内的语句调用 ，不能由其他函数或主程序来调用。下面的代码将f1函数定义成了f2函数的内部函数。下图中内部红框中的代码是f2函数定义的语句块。其中蓝色框中的代码为f1函数的定义，f1函数的定义被包含在f2语句块中。这样修改后的源程序如下面右图所示。

2、函数的递归调用

在调用一个函数时又出现了直接或间接调用该函数自身，称为递归调用。

递归不仅是一种函数的调用方法也是一种重要的分析问题的方法，借助于递归思想我们可以将许多复杂的问题简单化。我们先从简单的问题谈起。

假如我们要求100以内自然数的累加和，则我们可以这样思考，只要求出99以内各自然数的累加和再加上100就可以了。这好像并没有解决问题，但实际问题已经解决。

下面我们用这一思想来写函数。设求自然数n内各自然数的累加为f(n).

则 f(n)=1         当n=1时

   f(n)=n+f(n-1)  当n不等于1时。

写成Python 函数的形式，就是

def f(n):

  if n==1:

     s=1

  else：

     s=n+f(n-1)

  return s

我们在Python的程序文件中输入这个函数定义，并添加三行主程序代码调用这个函数，下面是程序和运行结果。

上面左图窗口中最后三行为主程序代码，分别调用函数f求100以内自然数累加和，求10以内自然数的累加和，求5以内自然数的累加和。

那么函数是怎样执行的呢，为了使问题简单，我们下面以f(5)为例分析函数的执行过程。

下图标出了调用函数f(5)求1+2+3+4+5的过程。

执行主程序中的语句f(5)时系统自动进入f函数内部执行，函数得到参数n=5,参见上面的第一个红框中的函数，函数中执行到小红方框语句时无法完成函数，于是该函数又调用了另一个函数f(虽然函数名称相同，但相当于是另一个新函数)，将参数n=4传递给函数f，求f(4),这时程序执行到第二个大红框，此时n=4,程序执行到小红框时仍无法求出结果，还必须再一次调用函数f,这次调用函数使用的参数是n=3,于是再次启动f函数，执行到第三个大红框中的代码，第三个红框中的小红框中的代码被执行时又一次调用了函数f,这次使用的参数是n=2,此时执行到第四个大红框中的代码，当执行到第四个大红框中的小红框中的代码时，又一次调用函数f,这次使用的参数是n=1,此时已执行到第五个黑色框中的程序代码，这次因为n=1,所以函数直接得到结果1，并返回这个函数值，于是第四个大红框中的小红框得到了结果1，将1代入，求出了s=2+1,至此第四个红框得到了函数值s并返回函数值3，于是第三个红框中的s得到了结果，s=3+3,返回函数值为 6给前一小红框，于是第二个红框中的s值得到函数值6，于是完成s=4+6的计算,接着返回该值10，前面的小红框中得到这个值，于是s=5+10就完成计算,这个值求出后，再返回主程序，就求出了最后的结果。

理解上面问题的关键是将各函数f看作是彼此不同的函数， 为了求f(5),必须调用函数求f(4),为了求f(4)必须调用函数求f(3),为了求f(3)必须调用函数求f(2),为了求f(2)必须调用函数f求f(1),f(1)可以求出，于是f(2)也就有了结果，f(2)有了结果，于是f(3)也就求出了，有了f(3)也就能求出f(4),有了f(4)，也就能求出f(5)了。

上面的函数可简化为：

def f(n):

  if n==1

     return 1

  else：

     return n+f(n-1)

从上面的分析可看出递归函数虽然设计时简单，但执行起来并不简单，虽然程序中没有循环，但它在执行时却完成了循环程序才能完成的任务。

递归调用函数的过程实际是：一个函数中又调用另一个函数……，直到得到最后的边界值，才逐级返回到主程序。下面我们通过几个例子来熟悉递归函数的编写方法。

依照上面的函数我们不难写出求整数n的阶乘的递归函数定义。

【例题1】 编写一个递归函数f,该函数能返回下面数列的第n项的值，并调用这个函数求出下面数列的第5项，第8项，第10项的值。

1，1，2，3，5，8，13，21，34，55……

【分析】设f(n)代表数列的第n项，则有下面的关系：

f(n)=1   当n=1或n=2时

f(n)=f(n-1)+f(n-2)   当n大于2时。

于是写出递归函数如下：

def f(n)：

   if n==1  or n==2:

       return 1

   else:

      return f(n-1)+f(n-2)    

下面左图是源程序，右图是运行后的结果，程序的最后三行代码为主程序，用于测试函数的功能，分别输出数列的第5项，第8项和第10项的值。

程序中求f(5)时函数的调用关系如下图所示。

【例题2】编写一个递归函数，能求出两个正整数的最大公约数，并用该函数求12，16的最大公约数，求100,25的最大公约数，求48,36的最大公约数。

【分析】我们设正整数m,n的最大公约数为f(m,n)，则有下面的关系。

f(m,n)=m  如果n=0

f(m,n)=f(n,m%n) 当n不等于0时

下面写出函数如下：

def f(m,n):

   if n==0:

      return m

   else :

     return f(n,m%n)

下面左图是源程序，右图是运行结果。

上面程序中最后三条语句分别用于求12和16，100和25，48和36的最大公约数。

【例题3】编写递归函数，输入一个正整数n，输出n个元素的全排列。比如输入2，则输出如下：

[1, 2]

[2, 1]

如果输入3，则输出为

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

如果输入4，则输出为：

[1, 2, 3, 4]

[1, 2, 4, 3]

[1, 3, 2, 4]

[1, 3, 4, 2]

[1, 4, 2, 3]

[1, 4, 3, 2]

[2, 1, 3, 4]

[2, 1, 4, 3]

[2, 3, 1, 4]

[2, 3, 4, 1]

[2, 4, 1, 3]

[2, 4, 3, 1]

[3, 1, 2, 4]

[3, 1, 4, 2]

[3, 2, 1, 4]

[3, 2, 4, 1]

[3, 4, 1, 2]

[3, 4, 2, 1]

[4, 1, 2, 3]

[4, 1, 3, 2]

[4, 2, 1, 3]

[4, 2, 3, 1]

[4, 3, 1, 2]

[4, 3, 2, 1]

【分析】函数虽然代码不多，但因为递归调用套在循环中所以画图分析的篇幅过大，此处只给出简单的说明，函数共作以下五件事，1）通过循环产生一个1-n之间的数字，2）判断该数字是否已经存在于正在生成的全排列中，如果已存在，则跳过这个数字，产生下一数字，如果当前的排列中不存在，则将其放入当前的全排列组合中。3)f(i+1,n)调用函数生成下一位数字。4)当生成了n位数字（i==n)则输出该全排列，再删除全排列序列中最后一个数字，以便更换下一个数字进行试用。

我们也可以画图分析，以n=3为例，第一次以f(1,3)调用函数，函数内部通过三次循环又各调用一次f(2,3)，f(2,3)被调用时，通过各自的循环，又各调用了f(3,3)三次，通过循环实际递归调用了九次函数f(3,3)。

每次调用函数实际是生成一位排列中的数字，够了位数则输出该排列，最后还要从排列中删除该位的数字，以便将该位更换成下一个数字。我们也可用上面的函数求从n个元素数每次取m个进行不重复的排列的全部方案，比如通过f(2,5)可以求出从5个数字中每次取两个不重复的数字共有多少种排列方式。其规律是可用f(m,n)求出从n个数字中每次取n-m+1个数字进行不重复的排列的全部排列方案。参见下面的程序，下图是分别是f(3,4）和f(2,4)调用函数后的输出结果。前者是从1，2，3，4四个数字中每次取两个的全部排列情况，后者是从1，2，3，4四个数字中每次取3个的排列方案