程序算法艺术与实践:递归策略基本的思想

分治策略(Divide and Conquer)是一种常用的算法技术,使用分治策略设计的算法通常是递归算法.很多时候我们看明白一个复杂的递归都有点费时间，尤其对模型所描述的问题概念不清的时候，想要自己设计一个递归那么就更是有难度了。如果递归仅仅是循环，估计现在我们就看不到递归了。递归之所以现在还存在是因为递归可以产生无限循环体. ### 用归纳法来理解递归 数学都不差的我们，第一反应就是递归在数学上的模型是什么。毕竟我们对于问题进行数学建模比起代码建模拿手多了。 自己观察递归，我们会发现，递归的数学模型其实就是归纳法。即:归纳法适用于想解决一个问题转化为解决他的子问题，而他的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。当然有一个是例外的，也就是递归结束的哪一个处理方法不适用于我们的归纳处理项，当然也不能适用，否则我们就无穷递归了。这里又引出了一个归纳终结点以及直接求解的表达式。如果运用列表来形容归纳法就是： - 步进表达式：问题蜕变成子问题的表达式 - 结束条件：什么时候可以不再是用步进表达式 - 直接求解表达式：在结束条件下能够直接计算返回值的表达式 - 逻辑归纳项：适用于一切非适用于结束条件的子问题的处理，当然上面的步进表达式其实就是包含在这里面了。 ### 分治策略一般性描述 把上面的设计思想加以归纳,可以得到分治算法的一般描述.设P是待求解的问题,|P|代表问题的输入规模,一般的分治算法Divide-and-Conquer伪码描述如下: ~~~ 算法 Divide-and-Conquer(P) 1. if |P| < c or |P| = c then S(P) 2. divide P into P1,P2,P3,...,Pk 3. for i = 1 to k do 4. yi ← Divide-and-Conquer(Pi) 5.Return Merge(y1,y2,y3,....,yk) ~~~ ### 需要满足的两个条件 编程人员还是停留在“自己调用自己”的程度上。这其实这只是递归的表象（PS:严格来说连表象都概括得不全面，因为除了“自己调用自己”的递归外，还有交互调用的递归）。而递归的思想远不止这么简单。递归，并不是简单的“自己调用自己”，也不是简单的“交互调用”。它是一种分析和解决问题的方法和思想。简单来说，递归的思想就是：把问题分解成为规模更小的、具有与原问题有着相同解法的问题。比如二分查找算法，就是不断地把问题的规模变小（变成原问题的一半），而新问题与原问题有着相同的解法。有些问题使用传统的迭代算法是很难求解甚至无解的，而使用递归却可以很容易的解决。比如Hanoi塔问题。但递归的使用也是有它的劣势的，因为它要进行多层函数调用，所以会消耗很多堆栈空间和函数调用时间。 既然递归的思想是把问题分解成为规模更小且与原问题有着相同解法的问题，那么是不是这样的问题都能用递归来解决呢？答案是否定的。并不是所有问题都能用递归来解决。那么什么样的问题可以用递归来解决呢？一般来讲，能用递归来解决的问题必须满足两个条件： - 可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。 - 存在一种简单情境，可以使递归在简单情境下退出。 如果一个问题不满足以上两个条件，那么它就不能用递归来解决。为了方便理解，如斐波那契数列来说下：求斐波那契数列的第N项的值。这是一个经典的问题，说到递归一定要提到这个问题。斐波那契数列这样定义：f(0) = 0, f(1) = 1, 对n > 1, f(n) = f(n-1) + f(n-2) 这是一个明显的可以用递归解决的问题。让我们来看看它是如何满足递归的两个条件的： - 对于一个n>2, 求f(n)只需求出f(n-1)和f(n-2)，也就是说规模为n的问题，转化成了规模更小的问题； - 对于n=0和n=1，存在着简单情境：f(0) = 0, f(1) = 1。 因此，我们可以很容易的写出计算费波纳契数列的第n项的递归程序： ~~~ int fib(n){ if(n == 0) return 0; else if(n == 1) return 1; else return f(n-1) + f(n-2); } ~~~ 在编写递归调用的函数的时候，一定要把对简单情境的判断写在最前面，以保证函数调用在检查到简单情境的时候能够及时地中止递归，否则，你的函数可能会永不停息的在那里递归调用了。 ### 两个熟悉的例子 先看两个熟悉的例子:字符串回文现象的递归判断和二分查找算法 #### 字符串回文现象的递归判断 回文是一种字符串，它正着读和反着读都是一样的。比如level,eye都是回文。用迭代的方法可以很快地判断一个字符串是否为回文。用递归的方法如何来实现呢？首先我们要考虑使用递归的两个条件： - 这个问题是否可以分解为形式相同但规模更小的问题？ - 如果存在这样一种分解，那么这种分解是否存在一种简单情境？ 先来看第一点，是否存在一种符合条件的分解。容易发现，如果一个字符串是回文，那么在它的内部一定存在着更小的回文。 比如level里面的eve也是回文。 而且，我们注意到，一个回文的第一个字符和最后一个字符一定是相同的。所以我们很自然的有这样的方法：先判断给定字符串的首尾字符是否相等，若相等，则判断去掉首尾字符后的字符串是否为回文，若不相等，则该字符串不是回文。注意，我们已经成功地把问题的规模缩小了，去掉首尾字符的字符串当然比原字符串小。 接着再来看第二点， 这种分解是否存在一种简单情境呢？简单情境在使用递归的时候是必须的，否则你的递归程序可能会进入无止境的调用。对于回文问题，我们容易发现，一个只有一个字符的字符串一定是回文，所以，只有一个字符是一个简单情境，但它不是唯一的简单情境，因为空字符串也是回文。这样，我们就得到了回文问题的两个简单情境：字符数为1和字符数为0。 综上两点分析,满足分治策略需要满足的两个条件了.即编写出解决回文问题的递归实现如下代码所示.: ~~~ int is_palindereme(char *str, int n){ printf("Length: %d \n",n); printf("%c ----- %c\n", str[0], str[n-1]); if(n == 0 || n == 1) return 1; else{ return ((str[0] == str[n-1]) ? is_palindereme(str+1, n-2) : 0); } } ~~~ 运行结果[ ](http://www.nowamagic.net/librarys/veda/detail/2317) [ ](http://www.nowamagic.net/librarys/veda/detail/2317) #### 二分查找算法的递归实现 典型的递归例子是对已排序数组的二分查找算法。现在有一个已经排序好的数组，要在这个数组中查找一个元素，以确定它是否在这个数组中，很一般的想法是顺序检查每个元素，看它是否与待查找元素相同。这个方法很容易想到，但它的效率不能让人满意，它的复杂度是O(n)的。现在我们来看看递归在这里能不能更有效。 还是考虑上面的两个条件： - 第一：这个问题是否可以分解为形式相同但规模更小的问题？ - 第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？ 考虑条件一：我们可以这样想，如果想把问题的规模缩小，我们应该做什么？可以的做法是：我们先确定数组中的某些元素与待查元素不同，然后再在剩下的元素中查找，这样就缩小了问题的规模。那么如何确定数组中的某些元素与待查元素不同呢？ 考虑到我们的数组是已经排序的，我们可以通过比较数组的中值元素和待查元素来确定待查元素是在数组的前半段还是后半段。这样我们就得到了一种把问题规模缩小的方法。 接着考虑条件二：简单情境是什么呢？容易发现，如果中值元素和待查元素相等，就可以确定待查元素是否在数组中了，这是一种简单情境，那么它是不是唯一的简单情境呢？ 考虑元素始终不与中值元素相等，那么我们最终可能得到了一个无法再分的小规模的数组，它只有一个元素，那么我们就可以通过比较这个元素和待查元素来确定最后的结果。这也是一种简单情境。 这个问题可以用递归来解决，二分法的代码如下： ~~~ void selectionSort(int data[], int count){ int i, j, min, temp; for(i = 0; i < count; i ++) { /*find the minimum*/ min = i; for(j = i + 1; j < count; j ++) if(data[j] < data[min]) min = j; temp = data[i]; data[i] = data[min]; data[min] = temp; } } int binary_search(int *data, int n, int key){ int mid; if(n == 1){ return (data[0] == key); } else{ mid = n/2; printf("mid=%d\n", data[mid]); if(data[mid-1] == key) return 1; else if(data[mid-1] > key){ printf("key %d 比 data[mid-1] %d 小，取前半段 \n", key, data[mid-1]); return binary_search(&data[0], mid, key); } else{ printf("key %d 比 data[mid-1] %d 大，取后半段 \n", key, data[mid-1]); return binary_search(&data[mid], n - mid, key); } } } ~~~ 程序运行结果：  这个算法的复杂度是O(logn)的，显然要优于先前提到的朴素的顺序查找法。 ### 小结 递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。 关于[程序算法艺术与实践](http://blog.csdn.net/column/details/tac-programalgrithm.html)更多讨论与交流，敬请关注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).