函数递归+函数栈帧（简）

函数递归

递归的含义

• 递归是一种解决问题的方法，在C语言中，递归就是函数自己调用自己，例如：

#include<stdio.h>
int main()
{printf("hehe\n");main();//main函数中又调用了main函数return 0;
}

递归的思想

• 把一个大型复杂问题层层转化为一个与原问题相似，但规模较小的子问题来求解；直到子问题不能在被拆分，递归就结束了，所以递归的思考方式就是把大事化小的过程

递归的限制条件

• 递归存在限制条件，当满⾜这个限制条件的时候，递归便不再继续。
• 每次递归调⽤之后越来越接近这个限制条件。

递归的举例

求n的阶乘，代码如下：

#include<stdio.h>
int Fac(int n)
{if (n == 0)return 1;elsereturn Fac(n - 1)*n;//一直递推，调用函数
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fac(n);printf("%d\n", ret);return 0;
}

运行：

图像推演：

递归与迭代

每一次函数调用，都会在内存的栈区申请空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者叫函数栈帧。
函数不返回，函数对应的栈帧空间就一直被占用，所以如果函数调用中存在递归调用的话，每一次递归函数调用都会开辟自己的栈帧空间，直到函数递归不再继续，开始回归，才逐渐释放栈帧空间。因而如果采用递归的方式完成代码，递归层次太深，就会浪费很多的栈帧空间，也可能引起栈溢出的问题

1.递归：

• 会占用更多的内存空间，有可能导致栈溢出的问题。
• 性能的下降。
• 有的复杂问题，使用递归描述非常简洁，写成代码也非常的方便。
  2.迭代（可以理解成循环）：
• 效率高
• 迭代的方式有时候不容易想到

函数栈帧的创建和销毁

（在不同的编译器下，函数调用过程中栈帧的创建是略有差异的，具体细节取决于编译器的实现）

• 在了解具体的函数栈帧之前，我和还需要知道一个东西叫做寄存器，有eax,ebx,ecx,edx,ebp,esp
• 函数栈帧，ebp和esp这两个寄存器存放的是地址，而这俩地址是用来维护函数栈帧的。
  具体的我以后还会再写一篇博客专门来说。