程序设计中递归的探讨

＼　实践与经验　＼　＼＼　—————————一——～　

算法的问题有三种情况：　

（１）问题的定义是递归的。　

在实际应用中．许多数学函数是递归定义的　例　

如：阶乘函数、斐波那契数列等　

（２）数据结构是递归的　

由于数据的结构本身具有递归特性．所以它们的　

操作可递归地描述。例如：二又树等　

（３）问题的解法是递归的。　

这类问题没有明显的递归结构．但求解的过程可　

以归纳成类似递推定义式形式的过程　例如Ｈａｎｏｉ问　

题、二分查找等　

针对这　种情况，我们分别加以举例进行分析。　

２　举例　

２．１问题是递归的　

这类问题一般是　为数学函数本身的定义就是递　归的．最典型的问题是阶乘函数，定义如下：　

ｎｆ－』＝０，　（１）：１　Ｉ　ｌ　Ｊ　【ｎ×（ｎ一１）！　ｎ＞ｌ　根据前文的叙述．设计成递归算法时．必须用ｉｆ＿＿．　

ｅｌｓｅ结构，ｉｆ满足条件．处理出口，即最低层ｎ＝０、１的情　

况．ｅｌｓｅ否则时调用函数自身。因此。可得出递归算法　为：　

ｆｌｏａｔ　ｆａｃ（ｉｎｔ　ｎ）｛　ｉｆ　ｆ　ｎ＝＝０　Ｉｌｎ＝＝ｌ１　ｒｅｔｕｒｎ　１；　ｅｌｓｅ　

ｒｅｔｕｒｎ　ｎ　ｆａｃ　ｆｎ－１）；　｝　

将求阶层的递归算法与１．１节递归算法的一般形　

式相对照．我们可以看出。形式非常工整．改动的地方　很小。为了进一步理解递归算法的执行．下面给出求　

ｆａｃ（５）的递归调用过程示意网如图ｌ所示。　

我们看这个示意图，就像一个楼梯．起初从最高　

层，一层层走到最后一层，然后再由最后一层开始．一　

层层回退最上面一层　前面几层的调用是重复行为．关　

键点是最后一层．是递归的出口．到此，程序不再往下　调用．而是开始返回上一层　仿照此例．读者可自行思　

考斐波那契数列、数组前Ｎ个元素求和等问题的处理。　

２．２数据结构是递归的　

这类问题中．数据的结构很特殊．本身就具有递归　

性，最典型的应用为二又树遍历。但此例，已分析较多，　

现从单链表结构着手　此结构在平常教学中．多采用非　递归方法．但实际上由于结构的特殊性．也可以采用递　

＠　现代计算机２０１０．１１　图１求ｆａｃｆ５１

的递归调用示意图　实践ｓ经验　／　／　一——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————一　

归算法，因此，为了活跃思维，提供多样化的解题方案，　

本文举一个单链表的例子。图２所示单链表为有序链　

表．现将一值ａ插入到链表合适位置。　

图２单链表示意图　

要找到合适位置必须对链表进行遍历．直至找到　

一个节点的值大于等于ａ后，可将ａ插人此节点前面。　据此分析．仿照１．１中递归算法的一般形式．可得出算　

法为：　

ｖｏｉｄ￣ｎｏｄｅ　Ｐ，ｎｏｄｅ　ｑ，ｉｎｔ　ａ）｛　ｉｆ（ｐ！＝ｎｕＨ＆＆ｐ一＞ｄａｔａ＜ａ）ｆ　／／递归调用　

ｑ＝ｐ；　ｆ（ｐ一＞ｎｅｘｔ，ｑ，ａ）；　｝　ｅｌｓｅ｛　，／递归的出口．找到比ａ值大的节点　

ｓ：（ｐｔｒ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｎ０ｄｅ））；　ｓ～＞ｄａｔａ＝ａ；ｑ一＞ｎｅｘｔ：ｓ；ｓ一＞ｎｅｘｔ＝ｐ；　

｝　｝　

图３有序单链表插入值递归调用示意图　

将图３、图ｌ对照起来，可发现图３中往下递归调　

用时．结果的处理只在最后一层，也就是说．当调归调　

用到最后一层时的结果即是程序要求的结果．因此．函　

数调用从最后一层回传时．并没有把下层结果带到上　

层。由此．我们可以更深刻地理解递归调用，递归调用　

必须有出口．但不一定需要把下层的值传给上层使用．　

要看结果是只在最后一层处理．还是需要其他层的共　

同处理　

２．３问题的解法是递归的　

这类问题中．问题的解法思路如果用递归来描述　

的话，会非常清晰易懂，编写成递归代码也更简洁。最　典型的有Ｈａｎｏｉ问题等。但因为该例子已经被阐述的　

较多．所以在这里举另外一个也非常典型的例子——　

快速排序　快速排序的基本思想是在待排元素中选取一元素　

ｘ为准（轴值）。将待排元素分成三部分：Ｒ１，ｘ，Ｒ２。其　

中．Ｒ１中的所有元素都＜ｘ，Ｒ２中的所有元素都≥ｘ，并对　

Ｒ１．Ｒ２重复上述方法．直至划分的每组元素个数为１。　

广　厂—ｕｎ　圆圈　圆圆圆　

排序前的元素序列　

圆圈；圆　圈圈圆圈　圆圈　圆　

ｊ　Ｒ１　ｉ　ｉ　Ｒ２　

图４～趟划分后的元素序列　

由图４分析可知．再进行第二趟、第ｉ趟、……第　

Ｎ趟的划分，重复的都是第一趟的动作，因此，后续是在　

递归的调用同一个功能．把递归的过程转换为一个递　

归树后。如图５所示。　

图５快速排序划分的递归树　

由此分析，得到快速排序的递归调崩程序：　

ｖｏｉｄ　ｑｕｉｃｋｓｏｒｔ（ｉｎｔ　ａｌｌ，ｉｎｔ　ｉ，ｉｎｔ　ｊ）　ｆ　ｉｎｔ　ｋ：　ｉｆ（ｉ＜ｊ１　／／ｉ＞＝ｊ时为递归的出口　ｐａｒｔｉｔｉｏｎ（ａ，ｉ，ｊ，ｋ）；　，／划分，ｋ为中间元素所在的下标　

ｑｕｉｃｋ—ｓｏｒｔ（ａ，ｉ，ｋ一１）；／／递归，Ｒ１快速排序　

ｑｕｉｃｋ—ｓｏｒｔ（ａ，ｋ＋１　）；／／递归，Ｒ２快速排序　

｝　

在递归的过程中．每凋用一层．功能已经接近结果　

一步，到最后一层完成时，功能也完成，因此，这个题目　

的处理既不同于图１的一层层往下调用后．再将下层　

现代计算机２０１ｏ．１１

　⑥　＼　实践与经验　

＼　

结果回传上来．供上一层使用．也不同于图３中的结果　

只在最后一层被处理　

３　递归调用的堆栈　

在递归调用中．最先调用的函数．必然最后被返　

回　这个保证是通过内存中的栈来实现的　每进入一层　

递归时．系统建立一个新的工作记录．记录函数的返回　

地址及参数调用等．推到栈顶　每退一层．就从工作栈　

中退出一个工作记录。例如：图６的求４　１的栈示意图。　

图６　

采用递归结构编写算法．结构清晰易懂．也可用数　

学归纳法来证明算法的正确性．因此它提高了算法的　

编写及调试效率。但是，递归算法的运行效率较低，时　间复杂度和空间复杂度均较高　

４　结语　

本文在这里对递归的概念及使用做了探讨．从中　

我们可以体会到．递归作为一种算法设计思路．在一些　

问题上可以起到一定的作用．使得问题的处理变得简　洁。但是递归也有它自身的缺点．算法设计时应考虑全　

面　

参考文献　【１］王庆瑞．数据结构教程【Ｍ］．北京希望电子出版社，２００２　【２］严蔚敏，吴伟民．数据结构【Ｍ］．北京：清华大学出版社，１９９７　

【３］李红卫．探索《数据结构》教学改革叨．计算机教育，２００７（１４）：　

４８～５０　刘冬晖，刘智涛．案例教学法在Ｃ语言教学中的研究与实　践ｌＪＩ．计算机教学与教育信息化，２００８：４９７～５１３　

一。　‘　‘‘ｆ、　’　■　一ｒ、　０　Ｄｉｓｃｕｓｓｉｏｎ　０ｎ　ｔｈｅ　ＨｅｃｕｒＳＩＯｎ　ｌｎ　Ｈｒｏｇｒａｍ　Ｕｅｓｉｇｎ　

ＷＵ　Ｙｏｎｇ－ｆｅｎ　，ＴＡＮＧ　Ｙａｎ—ｑｉｎｇ　，　ＺＨＡＮＧ　Ｘｉｎ—ｘｉｎｇ　

（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｍａｎｄ　Ａｕｔｏｍａｔｉｏｎ，ＰＬＡ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｎｊｉｎｇ　２１０００７）　

Ａｂｓｔｒａｃｔ：Ｒｅｃｕｒｓｉｏｎ　ｉｓ　ａ　ｖｅｒｙ　ｉｍｐｏｒｔａｎｔ　ｐｒｏｇｒａｍｍｉｎｇ　ｓｔｒｕｃｔｕｒｅ，ｂｕｔ　ｉｔ　ｉｓ　ｖｅｒｙ　ｄｉｆｉｃｕｌｔ　ｔｏ　ｂｅ　ｕｎｄｅｒｓｔｏｏｄ　ｉｎ　ｔｈｅ　ｓｏｍｅ　ｃｏｕｒｓｅｓ，ｉ．ｅ．Ｃ　ｌａｎｇｕａｇｅ，Ｄａｔａ　Ｓｔｒｕｃｔｕｒｅ．Ａｓ　ｆａｒ　ａｓ　ｔｈｅ　ｇｅｎｅｒａｌ　ｍａｓｔｅｒｙ　ｅｘｔｅｎｔｓ　ｏｆ　ｓｔｕ—　ｄｅｎｔｓ　ａｒｅ　ｃｏｎｃｅｒｎｅｄ，ｔｈｅ　ｒｅｅｕｒｓｉｏｎ　ｉｓ　ｎｏｔ　ｇｒａｓｐｅｄ　ｄｅｅｐｌｙ，ｏｒ　ａｐｐｌｉｅｄ　ｆｌｅｘｉｂｌｙ．Ｔｈｅｒｅｆｏｒｅ，ｐｒｅｓｅｎｔｓ　ｄｉｓｃｕｓｓｉｏｎｓ　ｏｎ　ｔｈｅ　ｕｓｉｎｇ　ｏｆ　ｒｅｅｕｒｓｉｖｅ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｐｒｏｇｒａｍｍｉｎｇ，ｔｏ　ｄｅｅｐｅｎ　ｔｈｅ　ｋｎｏｗｌｅｄｇｅ　ａｂｏｕｔ　ｉｔｓ　ｍａｓｔｅｒｙ　ａｎｄ　ａｐｐｌｉｃａｔｉｏｎｓ　ｆｏｒ　ｓｔｕｄｅｎｔｓ．　

Ｋｅｙｗｏｒｄｓ：Ｒｅｃｕｒｓｉｏｎ；Ｐｒｏｇｒａｍ　Ｄｅｓｉｇｎ；Ｒｅｃｕｒｒｅｎｃｅ　Ｆｏｒｍｕｌａ；Ｅｘｉｔ　Ｃｏｎｄｉｔｉｏｎ　

＠　现代计算机２０１０．１１