6.9　递归函数

Python语言中，如果一个函数在调用时直接或间接地调用了自身，就称为函数的递归调用，该函数就称为递归函数。

由于函数在执行时都会在栈中分配好自己的形参与局部变量副本，这些副本与该函数再次执行时不会发生任何的影响，因此使得递归调用成为了可能。

6.9.1　使用递归函数

递归是指在函数执行过程中再次对自己进行调用。例如：

    def f()
    {
    y=f();
    return y;
    }

该程序的执行过程如图6-39所示。

图6-39　递归过程

在函数f()中按照由上至下的顺序进行执行，当遇到对自身的调用时，再返回函数f()的起始处，继续由上至下进行处理。

例如，计算阶乘n! = 1 * 2 * 3 * ... * n，用函数f (n)表示，可以看出：

    f (n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n

所以，f (n)可以表示为n*fact(n-1)，只有n=1时需要特殊处理。

【例6.7】使用函数的递归调用，对n的阶乘进行求解并输出结果（源代码\ch06\6.7.py）。

保存并运行程序，结果如图6-40所示。

图6-40　运行结果

本示例演示了如何对函数进行递归调用。在上面的代码中，首先定义函数f()，该函数用于对n的阶乘进行求解。其中，若n=1，则阶乘为1；否则就调用函数f()，对n的阶乘进行求解，最后输出计算结果。

求n的阶乘即计算“n* f(n-1)”的值。6的阶乘的计算过程如下：

    ===>f(6)
    ===>6*f(5)
    ===>6*5*f(4)
    ===>6*5*4 *f(3)
    ===>6*5*4 * 3 *f(2)
    ===>6*5*4 * 3 * 2*f(1)
    ===>6*5*4 * 3 * 2*1
    ===>720

6.9.2　利用递归函数解决汉诺塔问题

汉诺塔问题源于印度一个古老的传说：有三根柱子，首先在第一根柱子从下向上按照大小顺序摆放64片圆盘；然后将圆盘从下开始同样按照大小顺序摆放到另一根柱子上，并且规定小圆盘上不能摆放大圆盘，在三根柱子之间每次只能移动一个圆盘；最后移动的结果是将所有圆盘通过其中一根柱子全部移动到另一根柱子上，并且摆放顺序不变。

以移动三个圆盘为例，汉诺塔的移动过程如图6-41所示。

图6-41　汉诺塔移动过程

【例6.8】使用递归算法解决汉诺塔问题，并将解决步骤输出在屏幕上（源代码\ch06\6.8.py）。

保存并运行程序，结果如图6-42所示。

图6-42　运行结果

在上面的代码中，首先定义move()函数，该函数有4个形参，分别是n、a、b、c，其中a、b、c用于模拟三根柱子。然后通过判断n的值分别进行不同的移法，若n为1，则可以直接将圆盘从a柱子移动到c柱子；若n不为1，则对move()函数进行递归调用。完成两个步骤：第一步将（n-1）个圆盘从a柱子通过c柱子摆放到b柱子上；第二步将第（n-1）个圆盘移动到b柱子后，由b柱子通过a柱子再移动到c柱子上，如此循环，最后完成转移。

6.9.3　防止栈溢出

使用递归函数需要防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。因为栈的大小不是无限的，所以递归调用的次数过多，会导致栈溢出。

例如：

运行结果如图6-43所示。

图6-43　运行结果

从运行结果可以看出，执行出现异常，提示超过最大递归深度。

解决递归调用栈溢出的方法是通过尾递归优化。事实上，尾递归与循环的效果是一样的，所以把循环看成是一种特殊的尾递归函数也是可以的。

尾递归是指在函数返回时调用函数本身，并且return语句不能包含表达式。这样，编译器或解释器就可以对尾递归进行优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

上面的f(n)函数，由于return n * f(n - 1)引入了乘法表达式，因此就不是尾递归了。要改成尾递归方式，就需要多一些代码，主要是把每一步的乘积传入到递归函数中：

可以看到，return f1(num - 1, num * product)仅返回递归函数本身。其中，num - 1和num *product在函数调用前就会被计算，不影响函数调用。

f(6)对应的f1(6,1)的调用如下：

    ===> f1(5, 1)
    ===> f1(5, 6)
    ===> f1(4, 30)
    ===> f1(3, 120)
    ===> f1(2, 360)
    ===> f1(1, 720)
    ===> 720

尾递归调用时，若进行了优化，则栈不会增长，因此无论调用多少次都不会导致栈溢出。