数据结构之栈与递归的实现及应用（斐波拉契数列递归解法和strlen递归解法）

小咪咪 2022-05-31 06:11 210阅读 0赞

**栈与递归**  
程序中的“函数调用栈”是栈数据结构的一种应用。  
函数调用栈一般是从高地址向低地址增长的,栈底为内存的高地址处，栈顶为内存的低地址处。  
函数调用栈中存储的数据为活动记录。活动记录是函数调用时一系列相关信息的记录。

![70][]![70 1][]

函数调用过程：

![70 2][]

程序中的栈空间可看做一个顺序栈的应用。  
栈保存了一个函数调用所需的维护信息：  
1.函数参数，函数返回地址；  
2.局部变量；  
3.函数调用上下文。  
什么是程序的栈溢出？

在不断的压栈过程中造成栈空间耗尽而产生栈溢出。  
栈溢出常由于函数递归过深或局部数组过大造成。

总结：

1.程序栈空间在本质上是一种顺序栈；  
2.程序栈空间的访问是通过函数调用进行的；  
3.程序栈空间仍然遵从后进先出的规则。

**递归的数学思想**  
递归是一种数学上分而自治的思想。  
递归将大型复杂问题转化为与原问题相同但规模较小的问题进行处理。  
递归需要有边界条件：

1. 当边界条件不满足时，递归继续进行；

**2.** 当边界条件满足时，递归停止。

![70 3][]

用递归解决问题首先要建立递归的模型，下面就作重介绍介个递归的应用实例。

**1.** 斐波拉契数列递归解法

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........

这个数列从第3项开始，每一项都等于前两项之和。所以可以归纳成如下的递归模型。

F(N) = 0 (N = 0)；

F(N) = 1 (N = 1)；

F(N) = F(N-1) + F(N-2) (N > 1)；

通过上面的模型可以编写如下函数：

int fibonacci(int n)
    {
        if( n > 1 )
        {
            return fibonacci(n-1) + fibonacci(n-2);
        }
        else if( n == 1 )
        {
            return 1;
        }
        else if( n == 0 )
        {
            return 0;
        }
    }

**2.**  **strlen** 递归解法

strlen常规的写法是循环依次比对字符串的每一个字符，直至遇到’\\0’停止，返回计数值。

递归的写法是只要知道字符串第二个字符以后的长度就可以知道整个字符的长度，建立起的递归模型如下：strlen（str+1）+1。通过上面的模型可以编写如下函数：

int strlen(const char* s)
    {
        if( s == NULL )
        {
            return -1;
        }
        else if( *s == '\0' )
        {
            return 0;
        }
        else
        {
            return strlen(s+1) + 1;
        }
    }

相关代码下载地址：http://download.csdn.net/download/u014754841/10246751

[70]: https://img-blog.csdn.net/20180209112709687?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxNDc1NDg0MQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: /images/20220531/24900d8b555c4fabae9cdb91b41dc977.png
[70 2]: /images/20220531/79d59d1f33b3442abd3371e573a75c19.png
[70 3]: /images/20220531/3356bb4a92794a60932f8cb5e7cdc201.png