如何写一个递归程序

http://blog.csdn.net/nxpzmj/article/details/9617159

 

 

总是听到大大们说递归递归的，自己写程序的时候却用不到递归。其中的原因，一个是害怕写递归，另一个就是不知道什么时候用递归。这篇文章就浅析一下，希望看完之后不再害怕递归，这就是本文最大的目的。

 

递归到底有什么意义？

在说怎么写递归之前必须要说一下它的意义，其实这就是为什么大多数人在看了许多递归的例子后还是不明所以的原因。可以肯定的是，递归是个十分强大的工具，有许多算法如果不用递归可能非常难写。很多地方介绍递归会用阶乘或者斐波那契数列作例子，这完全是在误导初学者。尽管用递归实现阶乘或者斐波那契数列是可以的，但是这是没有意义的。

先掉一下书袋，递归的定义是这样的：程序调用自身的编程技巧称为递归（ recursion）。在函数调用的过程中是有一个叫函数调用栈的东西存在的。调用一个函数，首先要把原函数的局部变量等压入栈中，这是为了保护现场，保证调用函数完成后能够顺利返回继续运行下去。当调用函数返回时，又要将这些局部变量等从栈中弹出。在普通的函数调用中，一般调用深度最多不过十几层，但是来到了递归的世界情况就不一样了。先看一段随便从网上就能找到的阶乘程序

 

double fab(int n)
{
    if(n == 0 || n == 1){
        return 1;
    }else{
        return n*fab(n-1);
    }
}

double fab(int n)
{
	if(n == 0 || n == 1){
		return 1;
	}else{
		return n*fab(n-1);
	}
}

 

如果n = 100，很显然这段程序需要递归地调用自身100次。这样调用深度至少就到了100。栈的大小是有限的，当n变的更大时，有朝一日总会使得栈溢出，从而程序崩溃。除此之外，每次函数调用的开销会导致程序变慢。所以说这段程序十分不好。那什么是好的递归，先给出一个结论，接着看下去自然会明白。结论是如果递归能够将问题的规模缩小，那就是好的递归。

 

怎样才算是规模缩小了呢。举个例子，比如要在一个有序数组中查找一个数，最简单直观的算法就是从头到尾遍历一遍数组，这样一定可以找到那个数。如果数组的大小是N，那么我们最坏情况下需要比较N次，所以这个算法的复杂度记为O(N)。有一个大名鼎鼎的算法叫二分法，它的表达也很简单，由于数组是有序的，那么找的时候就从数组的中间开始找，如果要找的数比中间的数大，那么接着查找数组的后半部分(如果是升序的话)，以此类推，知道最后找到我们要找的数。稍微思考一下可以发现，如果数组的大小是N，那么最坏情况下我们需要比较logN次(计算机世界中log的底几乎总是2)，所以这个算法的复杂度为O(logN)。当N变大后，logN << N，所以二分法会比直观的算法更快。而我们之后可以看到，二分法是可以用递归很简单的实现的(当然还有更好的方法，之后也会提到)。

 

简单的分析一下二分法为什么会快。可以发现二分法在每次比较之后都帮我们排除了一半的错误答案，接下去的一次只需要搜索剩下的一半，这就是说问题的规模缩小了一半。而在直观的算法中，每次比较后最多排除了一个错误的答案，问题的规模几乎没有缩小(仅仅减少了1)。这样的递归就稍微像样点了。

重新看阶乘的递归，每次递归后问题并没有本质上的减小(仅仅减小1)，这和简单的循环没有区别，但循环没有函数调用的开销，也不会导致栈溢出。所以结论是如果仅仅用递归来达到循环的效果，那还是改用循环吧。

 

总结一下，递归的意义就在于将问题的规模缩小，并且缩小后问题并没有发生变化(二分法中，缩小后依然是从数组中寻找某一个数)，这样就可以继续调用自身来完成接下来的任务。我们不用写很长的程序，就能得到一个十分优雅快速的实现。

 

怎么写递归程序

终于进入正题了。很多初学者都对递归心存畏惧，其实递归是符合人思考方式的。写递归程序是有套路的，总的来说递归程序有几条法则的。

用二分查找作为例子，先给出函数原型

 

int binary_search(int* array, int start, int end, int num_wanted)

int binary_search(int* array, int start, int end, int num_wanted)

返回值是元素在数组中的位置，如果查找失败返回-1。

 

 

1. 基准情况

基准情况其实就是递归的终止条件。其实在实际中，这是十分容易确定的。例如在二分查找中，终止条件就是找到了我们想要的数或者搜索完了整个数组(查找失败)。

 

if(end < start){
    return -1;
}else if(num_wanted == array[middle]){
    return middle;
}

if(end < start){
	return -1;
}else if(num_wanted == array[middle]){
	return middle;
}

 

 

2. 不断演进

演进的过程就是我们思考的过程，二分查找中，就是继续查找剩下的一半数组。

 

if(num_wanted > array[middle]){
    index = binary_search(array, middle+1, end, num_wanted);
}else{
    index = binary_search(array, start, middle-1, num_wanted);
}

if(num_wanted > array[middle]){
	index = binary_search(array, middle+1, end, num_wanted);
}else{
	index = binary_search(array, start, middle-1, num_wanted);
}

当然这是比较简单的演进方式，其他的比如快速排序、树、堆的相关算法中会出现更复杂一点的演进过程(其实也复杂不到哪里去)。

 

3. 用人的思考方式设计

这条法则我认为是非常重要的，它不会出现在编码中，但却是理解递归的一条捷径。它的意思是说，在一般的编程实践中，我们通常需要用大脑模拟电脑执行每一条语句，从而确定编码的正确性，然而在递归编码中这是不需要的。递归编码的过程中，只需要知道前两条法则就够了。之后我们就会看到这条法则的如何工作的了。

 

4. 不要做重复的事情

在任何编码中，这都是不应该出现的事情，但是在递归中这更加可怕，可能由于一次多余的递归使得算法增加数级复杂度。之后也会看到相关的例子。

 

现在我们可以写出我们完整的二分法的程序了

 

int binary_search(int* array, int start, int end, int num_wanted)
{
    int middle = (end - start)/2 + start; // 1
    if(end < start){
        return -1;
    }else if(num_wanted == array[middle]){
        return middle;
    }

    int index;
    if(num_wanted > array[middle]){
        index = binary_search(array, middle+1, end, num_wanted); // 2
    }else{
        index = binary_search(array, start, middle-1, num_wanted); // 3
    }
    return index; // 4
}

int binary_search(int* array, int start, int end, int num_wanted)
{
	int middle = (end - start)/2 + start; // 1
	if(end < start){
		return -1;
	}else if(num_wanted == array[middle]){
		return middle;
	}

	int index;
	if(num_wanted > array[middle]){
		index = binary_search(array, middle+1, end, num_wanted); // 2
	}else{
		index = binary_search(array, start, middle-1, num_wanted); // 3
	}
	return index; // 4
}

程序中除了1和4都已经在前两条法则的实现中了。1不必多说，4是一个比较关键的步骤，经常容易被忘记。这里就用到第3条法则，编写的时候只要认为2或者3一定会正确运行，并且立刻返回，不要考虑2和3内部是如何运行的，因为这就是你现在在编写的。这样4该如何处理就是显而易见的了，在这里只需要将找到的index返回就可以了。

 

第4条法则在这个例子里并没有出现，我们可以看一下斐波那契数列的递归实现

 

long int fib(int n)
{
    if(n <= 1){
        return 1;
    }else{
        return fib(n-1) + fib(n-2); // 1
    }
}

long int fib(int n)
{
	if(n <= 1){
		return 1;
	}else{
		return fib(n-1) + fib(n-2); // 1
	}
}

乍看之下，这段程序很精练，它也是一段正确的递归程序，有基准条件、不断推进。但是如果仔细分析一下它的复杂度可以发现，如果我们取n=N，那么每次fib调用会增加额外的2次fib调用(在1处)，即fib的运行时间T(N) = T(N-1) + T(N-2)，可以得到其复杂度是O(2^N)，几乎是可见的复杂度最大的程序了(其中详细的计算各位有兴趣可以google一下，这里就不展开了^_^)。所以如果在一个递归程序中重复多次地调用自身，又不缩小问题的规模，通常不是个好主意。

 

PS. 大家可以比较一下二分法与斐波那契数列的递归实现的区别，尽管二分法也出现了2次调用自身，但是每次运行只有其中一个会被真正执行。

 

尾递归

到此其实你已经可以写出任何一个完整的递归程序了，虽然上面的例子比较简单，但是方法总是这样的。不过我们可以对递归程序再进一步分析。二分查找的递归算法中我们注意到在递归调用之后仅仅是返回了其返回值，这样的递归称作尾递归。尽管在编写的时候不必考虑递归的调用顺序，但真正运行的时候，递归的函数调用过程可以分为递和归两部分。在递归调用之前的部分称作递，调用之后的部分称作归。而尾递归在归的过程中实际上不做任何事情，对于这种情况可以很方便的将这个递归程序转化为非递归程序。

 

int binary_search(int* array, int start, int end, int num_wanted)
{
    int middle;
search:
    middle = (end - start)/2 + start;
    if(end < start){
        return -1;
    }else if(num_wanted == array[middle]){
        return middle;
    }

    if(num_wanted > array[middle]){
        start = middle+1;
        end = end;
        goto search;
        //index = binary_search(array, middle+1, end, num_wanted);
    }else{
        start = start;
        end = middle-1;
        goto search;
        //index = binary_search(array, start, middle-1, num_wanted);
    }
}

int binary_search(int* array, int start, int end, int num_wanted)
{
	int middle;
search:
	middle = (end - start)/2 + start;
	if(end < start){
		return -1;
	}else if(num_wanted == array[middle]){
		return middle;
	}

	if(num_wanted > array[middle]){
		start = middle+1;
		end = end;
		goto search;
		//index = binary_search(array, middle+1, end, num_wanted);
	}else{
		start = start;
		end = middle-1;
		goto search;
		//index = binary_search(array, start, middle-1, num_wanted);
	}
}

上面就是去除递归后的二分查找的程序，我们只需要在程序开头处加上一个标号，在原本递归调用处修改参数的值并goto到标号就能完成这个工作。事实上，如果你写出了一个尾递归程序，在编译的时候编译器很可能就这样帮你优化了。当然这样的程序非常不符合我们的习惯，它实际上是将递归转化为了循环。循环还是应当使用while或者for实现，仔细地将上面这段程序改成while循环就成了这样。

int binary_search(int* array, int start, int end, int num_wanted)
{
    int middle = (end - start)/2 + start;
    while(end >= start && num_wanted != array[middle]){
        if(num_wanted > array[middle]){
            start = middle+1;
        }else{
            end = middle-1;
        }
        middle = (end - start)/2 + start;
    }

    if(end < start){
        return -1;
    }else{
        return middle;
    }
}

int binary_search(int* array, int start, int end, int num_wanted)
{
	int middle = (end - start)/2 + start;
	while(end >= start && num_wanted != array[middle]){
		if(num_wanted > array[middle]){
			start = middle+1;
		}else{
			end = middle-1;
		}
		middle = (end - start)/2 + start;
	}

	if(end < start){
		return -1;
	}else{
		return middle;
	}
}

这样就更加符合我们的习惯了，它比递归的版本速度略有提高，最重要的是不会导致栈溢出