E41.【C语言】练习:斐波那契函数的空间复杂度的计算及函数调用分析

1.题目

求下列代码的时间复杂度

long long f(size_t n)
{
 if(n < 3)
     return 1;

 return f(n-1) + f(n-2);
}

2.解

显然是递归算法(递归讲解见),可以画个二叉树分析

Fib嵌套函数调用细则的分析

进入f(n),返回f(n-1)+f(n-2),注意:一次只能调用一个函数,因此这里f(n-1)和f(n-2)不是同时调用

设n==5,VS上测试以下求第n个斐波那契数的代码

#include <stdio.h>
#include <string.h>
long long f(size_t n)
{
    if (n < 3)
        return 1;

    return f(n - 1) + f(n - 2);
}

int main()
{
    size_t a = 5;
    long long ret=f(5);//f函数的返回值用ret来接收
    printf("%lld", ret);
}

调用堆栈分析

F11进入调试模式,选择调用堆栈

一开始未进入f函数时,堆栈中只放了main函数

进入f(5)后,将其入栈,此时n值为5

第1次执行return f(n - 1) + f(n - 2); 后,n值为4,f(4)入栈

 第2次执行return f(n - 1) + f(n - 2); 后,n值为3,f(3)入栈

............

之后的具体内容见视频

注意:如果要在内存中查看堆栈,可以利用OllyDbg或x64dbg反编译 

附:一张核心图

标号1~20代表执行的顺序

附:一张堆栈图

注意

1.递推是入栈,回归是出栈

2.图片里的递推为3,4,5,7,10,13,14,16;回归为6,8,9,11,12,15,17,18