回文 - C - mars

http://verber.org/archives/137.html

递归的力量（二）

三月 20th, 200712:30 pm推荐指数：

昨天大体上说了一下递归的根本思想和使用递归解决问题的两个条件。今天来看看在解决具体问题的时候如何使用递归。

探测回文：

回文是一种字符串，它正着读和反着读都是一样的。比如level,eye都是回文。用迭代的方法可以很快地判断一个字符串是否为回文。用递归的方法如何来实现呢？

首先我们要考虑使用递归的两个条件：
第一：这个问题是否可以分解为形式相同但规模更小的问题？
第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？

先来看第一点，是否存在一种符合条件的分解。容易发现，如果一个字符串是回文，那么在它的内部一定存在着更小的回文。比如level里面的eve也是回文。而且，我们注意到，一个回文的第一个字符和最后一个字符一定是相同的。所以我们很自然的有这样的方法：先判断给定字符串的首尾字符是否相等，若相等，则判断去掉首尾字符后的字符串是否为回文，若不相等，则该字符串不是回文。注意，我们已经成功地把问题的规模缩小了，去掉首尾字符的字符串当然比原字符串小。

接着再来看第二点，这种分解是否存在一种简单情境呢？简单情境在使用递归的时候是必须的，否则你的递归程序可能会进入无止境的调用。对于回文问题，我们容易发现，一个只有一个字符的字符串一定是回文，所以，只有一个字符是一个简单情境，但它不是唯一的简单情境，因为空字符串也是回文。这样，我们就得到了回文问题的两个简单情境：字符数为1和字符数为0。

好了，两个条件都满足了，基于以上分析，我们可以很容易的编写出解决回文问题的递归实现方式：

PLAIN TEXT

int is_palindereme(char * str, int n){
if(n == 0 || n == 1)
return 1;
else{
return ((str[0] == str[n-1]) ? is_palindereme(str+1, n-1) : 0);
}
}

看起来很不错嘛。只有简单的几行代码，非常的简短，就解决了问题。

还有一个典型的例子是对已排序数组的二分查找算法。

现在有一个已经排序好的数组，要在这个数组中查找一个元素，以确定它是否在这个数组中，很一般的想法是顺序检查每个元素，看它是否与待查找元素相同。这个方法很容易想到，但它的效率不能让人满意，它的复杂度是O(n)的。现在我们来看看递归在这里能不能更有效。

还是考虑上面的两个条件：
第一：这个问题是否可以分解为形式相同但规模更小的问题？
第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？

考虑条件一：我们可以这样想，如果想把问题的规模缩小，我们应该做什么？可以的做法是：我们先确定数组中的某些元素与待查元素不同，然后再在剩下的元素中查找，这样就缩小了问题的规模。那么如何确定数组中的某些元素与待查元素不同呢？考虑到我们的数组是已经排序的，我们可以通过比较数组的中值元素和待查元素来确定待查元素是在数组的前半段还是后半段。这样我们就得到了一种把问题规模缩小的方法。

接着考虑条件二：简单情境是什么呢？容易发现，如果中值元素和待查元素相等，就可以确定待查元素是否在数组中了，这是一种简单情境，那么它是不是唯一的简单情境呢？考虑元素始终不与中值元素相等，那么我们最终可能得到了一个无法再分的小规模的数组，它只有一个元素，那么我们就可以通过比较这个元素和待查元素来确定最后的结果。这也是一种简单情境。

好了，基于以上的分析，我们发现这个问题可以用递归来解决，二分法的代码如下：

PLAIN TEXT

int binary_search(int * a, int n, int key){
int mid;
if(n == 1){
return (a[0] == key);
}else{
mid = n/2;
if(a[mid-1] == key)
return 1;
else if(a[mid-1]> key)
return binary_search(a, mid, key);
else
return binary_search(&a[mid], n - mid, key);
}
}

这个算法的复杂度是O(logn)的，显然要优于先前提到的朴素的顺序查找法。

好了，今天就说到这里，光看不管用，不如留个练习题您回去做做：

写一个函数dig_sum(int n)，输入一个非负整数，返回组成它的数字之和。如：dig_sum(2007) = 2+0+0+7 = 9。