关于递归程序设计方法的探讨

王笋 耿霞

摘要：递归是一种重要的程序设计方法，但在程序设计过程中一直是个难点。本文以递归为中心，从什么是递归、为何用递归、如何用递归以及使用递归需要注意的问题四个方面组织全文，从方法论的角度对递归程序设计进行系统的阐述。文中不仅介绍了递归程序设计的一般步骤和方法，还介绍了如何通过降阶、分治和回溯等策略进行递归程序设计。

关键词：递归；分治；回溯；汉诺塔问题；N皇后问题

引言

递归在程序设计基础、数据结构以及算法设计与分析等方面都占用重要地位，是一类重要的程序设计方法，但递归程序设计一直是个难点。程序设计过程通常会对为何用递归、如何用递归以及递归程序的执行过程存在疑惑。究其原因，一方面是通常只将递归作为一个概念进行简单介绍，对递归的执行过程以及递归程序设计的一般性步骤和方法描述过少；更重要的是缺少对递归程序设计方法系统性的概述。本文旨在解决这一问题，全文以递归为中心，从什么是递归、为何用递归、如何用递归以及使用递归需要注意的问题四个方面组织全文，从方法论的角度对递归程序设计进行系统的阐述。文中一方面结合汉诺塔问题和N皇后问题等经典实例介绍了递归程序设计的一般步骤和方法，还介绍了如何通过降阶、分治和回溯等策略进行递归程序设计。

1 什么是递归

简单来说，递归就是指函数或者过程在执行过程中直接或间接调用自身的现象。如表1中的函数即存在递归，称此类发生自身调用的函数为递归函数，通过设计递归函数进行问题求解的算法称为递归算法。

2 为何用递归

很多问题可以用递归的形式来描述，此时用递归进行程序设计简单、方便、易懂。

如一个正整数n的阶乘可如下定义：

在上述定义中，F（n）=n*F（n-1）在数学中称为递归公式，实际就对应程序设计中的递归调用，F（1）=1称为递归边界。根据阶乘的这种定义，只需列出递归边界和递归公式，再加上必须的函数头、变量声明等语句便可得到一个递归函数，如表1所示。需要说明的是，如此轻而易举得到的递归函数可直接求出n的阶乘，下面分析递归函数的执行过程予以证实。

假设主函数代码如表2所示，欲求3！并输出。当主函数执行到x=F（3）时，函数F第一次被调用并开始执行，此时形参n=3，显然应执行语句result=3*F（2）；之后F第二次被调用并开始执行，此时形参n=2，显然应执行语句result=2*F（1）；之后F第三次被调用并开始执行，此时形参n=1，显然应执行语句result=1和return result，至此，函数F的第三次执行结束，返回至调用语句result=2*F（1），注意返回后流程位于F的第二次执行中；继续执行可得result=2*1，接下来执行return result，至此，函数的第二次执行也结束并返回至调用语句result=3*F（2）处，注意返回后流程位于F的第一次执行中；继续执行得result=3*2*1，接下来执行语句return result，至此函数的第一次执行结束，返回至调用语句x=F（3）处，此时流程已回到主函数中；继续执行得x=3*2*1，如此3！被求出并赋予x，最后输出x的值6，整个程序结束。

由上例可见，递归通常是把一个大型复杂的问题层层转化为一个与原问题本质相同但规模更小的子问题来求解，运用递归只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量，用递归思想写出的程序往往十分简洁易懂。

3 如何用递归

如上节所述，进行递归程序设计的关键是借助递归关系的定义和递归边界构造递归函数，但有些问题的描述中递归关系和递归边界并没有显示给出，称此类问题为隐式递归问题。

对于显示递归问题，如前所述，直接根据递归关系的定义和递归边界构造出递归函数即可求解；对于隐式递归问题则要通过一定的策略来找出隐藏的递归关系和递归边界，常见策略如降阶、分治和回溯。

3.1 降阶

若问题规模较小时易找到解决方案，则可将此小规模问题及其解决方案作为递归边界；之后类似数学归纳法，假设规模为n-1时会求解，在此基础上考虑问题规模为n时的解决方案，如此即可得到一个将大规模问题归结为小规模问题的遞归关系。联合递归边界和递归关系的定义便可得到求解问题的递归函数，称此种构造递归算法的策略为降阶。

下面以汉诺塔问题为例说明如何通过降阶构造递归函数。所谓汉诺塔问题是指梵塔内有ABC三个塔座，其中塔座A上插有n个由小到大罗列的圆盘。现要求将这些圆盘从塔座A上搬动到塔座C上，要求一次只能搬动一个盘子，而且要求大盘不能压小盘，中间允许借助塔座B临时存放盘子。

假设欲构造递归函数Hanoi（n，x，y，z）输出将n个盘子从塔座x借助塔座y搬动到塔座z上的解决方案。

首先找出递归边界。显然，当问题规模足够小如只有一个盘子时，可直接将该盘从x搬动到y即可，此时可直接输出解决方案x→z。由此可得递归边界：

if（n==1）printf（“%c→%c”，x，z）。

接下来找递归关系。当n>1时，假设n-1个盘子能按规则要求从一个塔座借助另一个塔座搬动到第三个塔座上，则要将n个盘子从塔座x借助y搬动到z可分为三步：首先将塔座x上前n-1个小盘从塔座x借助塔座z搬动到塔座y上，之后将塔座x上仅剩的盘子从x搬动z上，最后将塔座y上n-1个盘子从塔座y借助塔座x搬到塔座z上。由此可得递归关系：

Hanoi（n-1，x，z，y）；

printf（“%c→%c”，x，z）；

Hanoi（n-1，y，x，z）；

根据上述递归边界和递归关系显然可得求解Hanoi塔问题的递归函数如表3所示。如执行语句Hanoi（3，A，B，C）将输出：A→C A→B C→B A→C B→A B→C A→C

3.2 分治

若操作对象可定义成由若干结构相同但规模更小的部分组成，则对原对象的操作可递归分解到其各组成部分上分别进行，如此递归分解直到不可再分时停止，此类求解策略称为分治。根据分治策略很容易得到相应的递归关系定义和递归边界，从而构造出具体的递归函数。

如非空的二叉树可看作为由根结点、根节点的左子树以及根结点的右子树三部分组成，每一部分又都是一颗树。如右图所示二叉树T可看作由根节点A、结点B、C构成的左子树和结点D、E、F构成的右子树组成。欲设计递归函数NodeCount（T）求二叉树T的结点总数，显然T的结点数是T的左子树结点数与T的右子树结点数之和再加1，这实际就是递归关系的定义；再注意到空树的结点树为0，依次作递归边界，即可得到表4所示所示的树结点计数的递归函数。

3.3 回溯

回溯也是一种问题求解策略，通常指让计算机从某种可能的情况出发自动向前进行搜索，碰到符合的情况就输出或者保存起来，在一条路径上走到“尽头”后就回到原来的岔路口选择一条以前没有走过的路重新向前进行探测，直到找到解或者走完所有路径为止。回溯具体编程实现时通常都用递归：“向前进行搜索”对应递归调用，“尽头”对应递归边界。

比如N皇后问题。题目是说，一个N*N的国际象棋棋盘上主放置N个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上，要求输出所有可能的摆放方案。其实，题目就是要找出所有可能的合法情况，可以考虑用回溯法求解。

让计算机逐行前进，每行摆放一个棋子，若合法则前进到下一行。为此可设递归函数void NQueens（int arr[N][N]，int i）；第一个参数代表棋盘，第二个参数代表目前标号为0的行到标号为i-1的行已经各有一个棋子，且符合规则要求。递归函数第一次被调用时时形参i值应为0，函数体内递归调用语句应为NQueens（arr，i+1）。至此递归关系定义已经找到，但还有一个问题，即递归何时停止或者说计算机前进过程中如何判断是否 “走到尽头”。分析可见共有两种情况：其一，当前行下完一个棋子后出现了非法情况，如同一列或同一斜线上出现了多个皇后，此时应抹掉该行所下棋子，在其右侧重新下一个棋子再重新检查；其二，当前行下完一个棋子后仍然合法，但恰巧当前行是最后一行，这实际意味着已经得到了一种合法的摆放方案，此时应输出该方案，之后抹掉该行所下棋子，在其右侧下一个棋子重新检查。由上述递归边界和递归关系定义可构造递归函数如下：

通过上例可见，回溯法的主要特点是递归结束的条件在搜索的最后一步，关键是找到递归边界条件

4 递归存在的问题

使用递归进行程序设计思路清晰、代码简洁，但递归调用过程中，每一次发生调用系统都要将返回地址、局部变量等信息入栈保存，因此，递归程序的运行效率较低，而且递归次数过多还容易造成栈溢出。此外，尤其要避免重复递归调用的现象发生。比如求Fibnacci数列的第n项可通过表6所示递归函数实现，假设n=4则递归执行过程中发生的递归调用如图3所示，可见n=4时f（1）已经被重复调用了3次。在Core 2CPU T5500、内存1G的机器上进行测试，计算f（40）約需20.374秒的时间，其主要原因在于计算f（40）时f（1）会被重复调用165580141次；而计算f（50）更是需要40多分钟！

5 结束语

本文系统讲述了递归的基本概念、使用递归进行程序设计的好处以及如何设计递归程序，结合Hanoi塔问题、N皇后问题等经典实例介绍了通过降阶、分治及回溯构造递归函数的一般化方法，并对递归使用过程中可能存在的问题进行了说明。总地来说，递归作为一种重要的程序设计方法可使得编码清晰易懂，但存在运行效率较低的问题，在实际应用当中，建议仅当传统方法不方便求解时使用递归。

参考文献：

[1]谭浩强，《C程序设计》，清华大学出版社，北京：2005.7

[2]孙承爱，赵卫东.《程序设计基础（基于C语言）》，清华大学出版社，北京：2008.2

[3]严蔚敏，吴伟民.《数据结构（C语言版）》，清华大学出版社，北京：2007.3

[4]M.A.Weiss著，翁惠玉等译.《数据结构与问题求解-Java语言描述）》，人民邮电出版社，北京：2006.7

[5]王晓东，《计算机算法设计与分析》，电子工业出版社，北京：2007.5