当前位置：首页 > article >正文

数据结构-3.9.栈在递归中的应用

article 2024/10/2 8:32:05

一.函数被调用背后的过程：最后被调用的函数最先结束也符合栈的后进先出

1.main函数为主函数即程序入口，运行时主函数先入栈，然后存入主函数里的数据；

2.func1函数加载在栈中时他后面的代码的地址#1(调用返回地址，不是下面其他代码的地址)也会被加载进去，其他函数也同理；

3.func1里的a,b和主函数里的a,b是不一样的，因为加载的区域不一样导致地址也不一样，

因此func1里传入a,b的值影响不到主函数里a,b的值；

4.栈其实就是内存里的某一片区域(某一片存储空间)；

5.上图中main函数下还有代码，是因为在加载main函数前还会有一些未知的信息需要加载，

例如：

二.栈在递归中的应用：

1.实例：

2.递归算法求阶乘：

a.图示：

#192和#187都代表调用返回地址，是函数最终的结果，也属于函数的一部分。

n为1时不再调用factorial函数，也就没有函数入栈，之后不断出栈，求出最终结果：

b.代码：

#include<stdio.h>

//计算正整数n! 
int factorial(int n)
{
    if(n==0||n==1)
    {
        return 1;
    }
    n=n*factorial(n-1);
    return n;
}

int main()
{
    int result=factorial(10);
    printf("%d \n",result);
    return 0;
}

3.递归算法求斐波那契数列：

a.图示：

b.代码：

#include<stdio.h>

int Fib(int n)
{
    if(n==0)
    {
        return 0;
    }
    if(n==1)
    {
        return 1;
    }
    n=Fib(n-1)+Fib(n-2); 
    return n;
}

int main()
{
    int result=Fib(6);
    printf("%d \n",result);
    return 0;
}