【数据结构】栈的应用——递归（裴波那切数列）

不念不忘少年蓝@ 2023-02-14 13:25 108阅读 0赞

### 文章目录 ###

*   *  引言
     *  裴波那切数列的实现（Fibonacci）
     *   *  递归定义
         *  递归和栈的关系

## 引言 ##

栈有一个很重要的应用：在程序设计语言中实现了递归，那么什么是递归了？  
当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗？如果A,B两面镜子相互面对面放着，你往中间一站，两面镜子都有你的千百个化身。为什么会有这种现象呢？原来，A镜子里有B镜子的像，B镜子里也有A镜子的像，这样反反复复，就会产生一连串的“像中像”。这是一种递归现象。

## 裴波那切数列的实现（Fibonacci） ##

假如兔子在出生两个月候，具有繁殖能力，一对兔子每个月能生出一对小兔子来，假设所有兔子不死，那么一年之后可以繁殖多少兔子了？  
我们对新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对，两个月后，生下一对小兔子共有两对，三个月后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对……依次类推，如下图。  
![在这里插入图片描述][20200603105644195.png]上表中兔子对数1,1,2,3,5,8,13……构成了一个序列。这个数列有个十分明显的特点：前面相邻两项之和，构成了后一项。用数学函数定义就是  
![在这里插入图片描述][2020060311242452.png]  
先考虑一下，如果我们要实现这样的序列用常规的迭代办法怎么实现？  
假设我们现在打印出前40位的裴波那切数列。

int main()
    {
        
    	int i;
    	int a[40];
    	a[0]=0;
    	a[1]=1;
    	printf("%d",a[0]);
    	printf("%d",a[1]);
    	for(i = 2;i < 40;i++)
    	{
        
    		a[i]=a[i-1] + a[i-2];
    		printf("%d",a[i]);	
    	}
    	return 0;
    }

代码其实很简单，几步不用做什么解释，如果使用递归来实现，还可以更简单。

#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;
    	int a[40];  
    	printf("迭代显示斐波那契数列：\n");
    	a[0]=0;
    	a[1]=1;
    	printf("%d ",a[0]);  
    	printf("%d ",a[1]);  
    	for(i = 2;i < 40;i++)  
    	{
         
    		a[i] = a[i-1] + a[i-2];  
    		printf("%d ",a[i]);  
    	} 
    	printf("\n");
    	
    	printf("递归显示斐波那契数列：\n");
    	for(i = 0;i < 40;i++)  
    		printf("%d ", Fbi(i));  
        return 0;
    }

### 递归定义 ###

把一个直接调用自己或者通过一系列的调用语句间接的调用自己的函数，称作递归函数。  
当然，写递归程序最怕的就是陷入永不结束的无穷递归之中，所以，每个递归定义必须至少有一个条件，满足时递归不在进行，即不在引用自身而是返回值退出。  
迭代和递归的区别是:迭代使用的是循环结构，递归使用的是选择结构。  
递归的程序能使程序的结构更清晰，简介，更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存，迭代则不需要反复调用函数和占用额外的内存。

### 递归和栈的关系 ###

前面我们看到了递归是如何执行它的前行和退回阶段的。递归过程是退回的顺序是它前行的逆序。在退回的过程中，可能要执行某些动作，包括恢复在前行过程中的存储起来的某些数据。  
这种存储某些数据，并在后面又以存储的逆序恢复这些数据，已提供之后使用的需求，显然很符合栈这样的数据结构，因此，编译器使用栈实现递归。

简单的说就是在前行阶段，对于每一次递归，函数的局部变量、参数值以及返回值都被压入栈中。在退回阶段，位于栈顶的局部变量，参数值和返回值被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

[20200603105644195.png]: https://img-blog.csdnimg.cn/20200603105644195.png
[2020060311242452.png]: https://img-blog.csdnimg.cn/2020060311242452.png