`

如何写一个递归程序

 
阅读更多

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

 

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

 

递归到底有什么意义?

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


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

 

  1. double fab(int n)  
  2. {  
  3.     if(n == 0 || n == 1){  
  4.         return 1;  
  5.     }else{  
  6.         return n*fab(n-1);  
  7.     }  
  8. }  
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),这和简单的循环没有区别,但循环没有函数调用的开销,也不会导致栈溢出。所以结论是如果仅仅用递归来达到循环的效果,那还是改用循环吧。

 

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

 

怎么写递归程序

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

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

 

  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. 基准情况

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

 

  1. if(end < start){  
  2.     return -1;  
  3. }else if(num_wanted == array[middle]){  
  4.     return middle;  
  5. }  
if(end < start){
	return -1;
}else if(num_wanted == array[middle]){
	return middle;
}

 

 

2. 不断演进

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

 

  1. if(num_wanted > array[middle]){  
  2.     index = binary_search(array, middle+1, end, num_wanted);  
  3. }else{  
  4.     index = binary_search(array, start, middle-1, num_wanted);  
  5. }  
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. 不要做重复的事情

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

 

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

 

  1. int binary_search(int* array, int start, int end, int num_wanted)  
  2. {  
  3.     int middle = (end - start)/2 + start; // 1  
  4.     if(end < start){  
  5.         return -1;  
  6.     }else if(num_wanted == array[middle]){  
  7.         return middle;  
  8.     }  
  9.   
  10.     int index;  
  11.     if(num_wanted > array[middle]){  
  12.         index = binary_search(array, middle+1, end, num_wanted); // 2  
  13.     }else{  
  14.         index = binary_search(array, start, middle-1, num_wanted); // 3  
  15.     }  
  16.     return index; // 4  
  17. }  
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条法则在这个例子里并没有出现,我们可以看一下斐波那契数列的递归实现

 

  1. long int fib(int n)  
  2. {  
  3.     if(n <= 1){  
  4.         return 1;  
  5.     }else{  
  6.         return fib(n-1) + fib(n-2); // 1  
  7.     }  
  8. }  
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次调用自身,但是每次运行只有其中一个会被真正执行。

 

尾递归

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

 

  1. int binary_search(int* array, int start, int end, int num_wanted)  
  2. {  
  3.     int middle;  
  4. search:  
  5.     middle = (end - start)/2 + start;  
  6.     if(end < start){  
  7.         return -1;  
  8.     }else if(num_wanted == array[middle]){  
  9.         return middle;  
  10.     }  
  11.   
  12.     if(num_wanted > array[middle]){  
  13.         start = middle+1;  
  14.         end = end;  
  15.         goto search;  
  16.         //index = binary_search(array, middle+1, end, num_wanted);  
  17.     }else{  
  18.         start = start;  
  19.         end = middle-1;  
  20.         goto search;  
  21.         //index = binary_search(array, start, middle-1, num_wanted);  
  22.     }  
  23. }  
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循环就成了这样。

  1. int binary_search(int* array, int start, int end, int num_wanted)  
  2. {  
  3.     int middle = (end - start)/2 + start;  
  4.     while(end >= start && num_wanted != array[middle]){  
  5.         if(num_wanted > array[middle]){  
  6.             start = middle+1;  
  7.         }else{  
  8.             end = middle-1;  
  9.         }  
  10.         middle = (end - start)/2 + start;  
  11.     }  
  12.   
  13.     if(end < start){  
  14.         return -1;  
  15.     }else{  
  16.         return middle;  
  17.     }  
  18. }  
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;
	}
}

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

分享到:
评论

相关推荐

    递归子程序法和预测分析法程序

    与递归子程序法不同的是,预测分析法在解析过程中会利用一个有限的向前查看(即k个符号的查看窗口)来决定下一步的操作。这种方法试图预测输入序列的可能展开,从而选择正确的解析路径。预测分析表是预测分析法的...

    Java SE程序 递归 Java SE程序 递归

    Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE...

    读懂C++递归程序

    上述文档中提到的递归程序是一个递归函数,它处理一个整数,并按位打印出该整数的每一位数字。程序的代码如下: ```cpp void f(int n) { if (n == 0) return; else { cout ; f(n / 10); cout ; return; } } ...

    精通递归程序设计

    ### 精通递归程序设计 #### 一、递归程序设计概述 递归是一种在计算机科学中广泛使用的编程技巧,它允许一个函数通过直接或间接的方式调用自身来解决问题。递归不仅可以简化代码,还能使一些复杂问题的解决变得...

    凑数字 凑金额 的最佳递归程序(by_kagawa)

    标题中的“凑数字 凑金额 的最佳递归程序”指的是一个使用递归算法解决特定问题的程序,其目标是在一组给定的数字中找到最佳组合,使得这些数字相加尽可能接近或者等于一个预设的目标金额。这样的问题在实际生活中...

    递归程序

    在编程领域,递归是一种强大的概念,它涉及到一个函数或过程在其定义中调用自身来解决问题。递归程序是基于这种自引用机制的,通常用于处理分治问题、树形结构遍历、图算法以及各种数学计算。在这个场景中,我们有两...

    编译原理-递归子程序 c++源码

    它的基本思想是,对文法中的每一个非终结符编写一个函数,每个函数的功能是识别由该非终结符所表示的语法成分。 1、给定文法:S→(T)|^|a T→T,S|S 由于该文法不是 LL(1) 文法,所以需要将其改写为能用递归下降...

    凑数字凑金额的最佳递归程序.xls

    凑数字凑金额的最佳递归程序

    递归程序设计(WORD)

    标题提到的"递归程序设计"是一个面向初学者的主题,旨在帮助学习者理解递归的基本概念和应用。描述中提到了两个实验题目,一个是计算两个整数的最大公约数(GCD),另一个是生成Fibonacci数列的前n项。这两个问题都...

    汇编语言的递归程序

    本文将详细探讨如何在汇编语言中编写递归程序,以求解一个整数的阶乘为例,展示递归在汇编中的具体应用。 首先,我们需要了解递归的基本概念。递归通常涉及三个主要部分:基本情况(base case)、递归情况...

    递归下降子程序

    递归下降子程序利用了C++的这种特性,将每个文法规则转换为一个函数,函数的递归调用模拟了文法的结构。例如,`parseExpression()`函数可能首先调用`parseTerm()`,然后`parseTerm()`可能进一步调用`parseFactor()`...

    语法分析器 递归子程序法

    总的来说,这个程序使用递归子程序法构建了一个PL/0语言的语法分析器,通过对输入的字符流进行分析,验证源程序的语法合法性,并生成中间代码。这种方式直观且易于理解,对于学习编译原理和实践编译器开发具有重要的...

    编译原理 递归下降语法分析程序(代码+说明文档)

    本资源包含了一个递归下降语法分析程序的实现,以及相关的说明文档,旨在帮助学习者深入理解和实践这一重要概念。 1. **递归下降解析法**:递归下降分析是通过一系列的函数来实现的,每个函数对应文法规则的一个非...

    递归程序设计_求N阶乘.doc

    递归程序设计_求N阶乘 在计算机科学中,递归程序设计是一种常用的编程技术。...今天,我们学习了如何使用递归程序设计来计算N的阶乘,并使用MASM for Windows编译器编写了一个功能强大的递归程序。

    PL0语法分析器(递归子程序法)

    3. **递归子程序法工作原理**:此方法的核心在于,每一个非终结符都对应一个函数,这个函数会尝试匹配文法规则,并通过递归调用来处理子规则。如果匹配成功,函数返回;如果不成功,则抛出错误。例如,对于PL0的...

    Java写的递归下降分析程序

    总结起来,"Java写的递归下降分析程序" 是一个基于Java实现的编译器前端组件,用于解析输入的源代码,将其转换成抽象语法树。它利用递归函数模拟上下文无关文法的推导过程,但可能处于未完成或存在错误的状态。通过...

    递归程序用栈改写为非递归

    C语言,将一个递归程序用栈改写为非递归,其中用到栈的基本操作

    递归下降子程序的编写

    我们编写了一个递归下降子程序,用于判定某个算术表达式是否正确。我们使用了 C++ 语言编写程序,并使用了递归函数来实现递归下降预测分析。我们的程序可以正确地判定某个算术表达式是否符合文法。 六、总结 通过...

    递归和非递归解决迷宫问题

    (1)以链栈作为存储结构,编写一个求解迷宫的非递归程序,并将求得的通路以三元组(i,j,d)的形式输出,其中: i,j指示迷宫中的一个坐标,d表示走到下一坐标的方向; (2)编写递归形式的算法,求得迷宫中所有可能...

    一个简单的C#WindowsForm程序,用递归求N!

    本项目中的"一个简单的C# WindowsForm程序,用递归求N!"是一个教学示例,旨在教授如何在C#环境下利用递归算法计算阶乘(N!)。 首先,让我们理解什么是阶乘。阶乘是数学中的一个概念,表示一个正整数n的所有小于...

Global site tag (gtag.js) - Google Analytics