递归,栈的重要应用之一

了解递归的一些细节
服务器君一共花费了367.589 ms进行了7次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

栈有一个很重要的应用:在程序设计语言中实现了递归。那么什么是递归呢?

  • 当你往镜子前面一站,镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果A、B两面镜子相互面对面放着,你往中间一站,嘿,两面镜子里都有你的千百个 “化身”。为什么会有这么奇妙的现象呢?原来,A镜子里有B镜子的像,B镜子里也 有A镜子的像,这样反反复复,就会产生一连串的“像中像” 这是一种递归现象。

我们先来看一个经典的递归例子:斐波那契数列(Fibonacci)。为了说明这个数列,这位斐老还举了一个很形象的例子。

斐波那契数列

如果兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子 来。假设所有兔都不死,那么一年以后可以繁殖多少对兔子呢?

  • 我们拿新出生的一对小兔子分析一下:第一个月小兔子没有繁殖能力,所以还是一对;两个月后,生下一对小兔子数共有两对;三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对……依次类推。
经过月数 1 2 3 4 5 6 7 8 9 10 11 12
兔子对数 1 1 2 3 5 8 13 21 34 55 89 144

表中数字1, 1,2,3, 5, 8,13……构成了一个序列。这个数列有个十分明显的 特点,那是:前面相邻两项之和,构成了后一项。

算法的可以描述为:

def Fib(n):  

    if (n < 1):  
        return 0  

    elif (n <= 2):  
        return 1  

    else:  
        return Fib(n-1)+Fib(n-2)

假设我们不了解递归,我们要实现这样的数列用常规的的办法如何实现?

比如我们需要打印出前20位的斐波那契数列数。

  • 先定义一个数组a,能存20个数。然后赋值a[0]=0,a[1]=1,然后根据它们的和凑第三个数。往后的数都是通过前两个数凑出来,a[i] = a[i-1] + a[i-2]; 这是常规的思路。
#include "stdio.h"

int main()
{
	int i;
	int a[20];
	printf("迭代显示斐波那契数列:\n");
	a[0]=0;
	a[1]=1;
	printf("%d ",a[0]);
	printf("%d ",a[1]);
	for(i = 2;i < 20;i++)
	{
		a[i] = a[i-1] + a[i-2];
		printf("%d ",a[i]);
	}
	printf("\n");
    return 0;
}

程序运行结果为:

迭代显示斐波那契数列:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
  • 嗯,代码很简单,几乎不用做什么解释。但其实我们的代码,如果用递归来实现,还可以更简单。
#include "stdio.h"

int Fbi(int i)  /* 斐波那契的递归函数 */
{
	if( i < 2 )
		return i == 0 ? 0 : 1;
    return Fbi(i - 1) + Fbi(i - 2);  /* 这里Fbi就是函数自己,等于在调用自己 */
}

int main()
{
	int i;

	printf("递归显示斐波那契数列:\n");
	for(i = 0;i < 20;i++)
		printf("%d ", Fbi(i));
    return 0;
}

怎么样,相比较迭代的代码,是不是干净很多。嘿嘿,不过要弄懂它得费点脑子。

函数怎么可以自己调用自己?听起来有些难以理解,不过你可以不要把一个递归函数中调用自己的函数看作是在调用自已,而就当它是在调另一个函数。只不过,这个函数和自己长得一样而已。我们来模拟代码中的Fbi(i)函数当i = 5的执行过程,如下图。

或者看看另外一种描述:

延伸阅读

此文章所在专题列表如下:

  1. 栈的定义与大概理解
  2. 栈的抽象数据类型ADT
  3. 顺序栈:栈的顺序存储结构
  4. 顺序栈的进栈操作
  5. 顺序栈的出栈操作
  6. 获取顺序栈的栈顶元素
  7. 链栈:栈的链式存储结构
  8. 链栈的进栈操作
  9. 链栈的初始化与遍历
  10. 链栈的出栈操作
  11. 链栈的置空操作与判断链栈是否为空
  12. 为什么要使用栈这种数据结构
  13. 递归,栈的重要应用之一
  14. 栈是如何实现递归的
  15. 接触后缀表达式(逆波兰表示法)
  16. 图解后缀表达式的计算过程
  17. 将中缀表达式转化为后缀表达式
  18. 开始学习队列这个数据结构
  19. 队列的抽象数据类型ADT
  20. 顺序队列:队列的顺序存储结构
  21. 顺序队列的入队操作
  22. 顺序队列的出队操作
  23. 顺序队列置空与判断操作
  24. 队列顺序存储结构的不足
  25. 关于循环队列的一些讲解
  26. 链队列:队列的链式存储结构
  27. 链队列的初始化操作
  28. 链队列的入队操作
  29. 链队列的出队操作
  30. 补完链队列的其它常见操作
  31. 循环队列与链队列的优劣势

本文地址:http://www.nowamagic.net/librarys/veda/detail/2298,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2298

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《编程之美:微软技术面试心得》 《编程之美》小组 (作者)

《编程之美:微软技术面试心得》是一本让人着迷的书!阅读起来。有些题目的内容会引起强烈的共鸣,尤其是那些自己非常熟悉并且又深知解答的题目;也有一些题目让我异常惊诧,原来除了我所知道的解答思路之外,还有更好的解答以及更深层次的原因。还有一些题目是从来没想到过的。阅读过程是一次愉快的享受,也是脑细胞持续活跃的过程。

更多计算机宝库...