C语言-函数递归

清明节生病了没有及时更新函数学完之后来学习函数递归的内容首先什么是递归递归简单来说就是函数自己调用自己例如下面这个最简单的递归#include stdio.h int main() { printf(Hello); main(); return 0; }d这就是一个最简单的递归在main函数中调用main函数但是是一个错误的死递归代码执行后会不断打印Hello直到报栈溢出Stack overflow的错误。栈溢出Stack overflow每一次函数调用都会在栈区中申请一块空间来存放本次函数调用期间的各种局部变量。而如果写出了以上这样错误的代码导致死递归就会不断在栈区中申请空间结果就是栈溢出。递归的条件通过以上这个例子我们知道了函数递归需要条件约束否则会陷入死递归最终导致栈溢出。因此函数递归的条件存在限制条件满足限制条件时不再递归递归时越来越接近限制条件递归的思想到这里还有很多人不知道到底递归是干什么的对递归还是一知半解的感觉了解了递归的概念和递归的条件后我们就可以来看到底什么时候用递归递归是用来解决什么问题的。递归思想就是把大型复杂问题层层转化为一个与原问题相似、规模较小的子问题来求解直到不能再被拆解。接下来举一个例子让我们来理解递归的作用例计算 n 的阶乘。使用普通迭代的思想也就是通过循环来实现#include stdio.h int main() { int n 0, a 1; scanf(%d, n); for (int i 1;i n;i) { a * i; } printf(%d, a); return 0; }那么当我们使用递归的思想时事情就变得非常简单了。我们知道n! (n-1)! x n那么如果将求阶乘封装成一个函数 Fac(); 那么 Fac(n) Fac(n-1) x n.理论成立开始实践#includestdio.h int Fac(int n) { if (n 1) return 1; else return Fac(n - 1) * n; } int main() { int n 0; scanf(%d,n); int ret Fac(n); printf(%d, ret); return 0; }不难理解这段代码就是将n的阶乘转化为n-1的阶乘再转化为n-2的阶乘最终转化为1Fac(n) Fac(n-1) x n Fac(n-2) x (n-1) x n ...... //这个过程叫做递推Fac(1) 1 , Fac(2) Fac(1) x 2 , ...... //这个过程叫回归先不断递推到限制条件得到值后在回归到原本的函数中这就是函数的递归相信现在大多数人都理解了什么是递归以及递归的用法了。递归与迭代前面我们知道了每一次函数的调用都会产生额外的空间开销这块内存空间被称为运行时堆栈或函数栈帧。函数不返回空间就会被一直占用直到递推不再继续开始回归才逐层释放空间。因此如果递归层次太深就会浪费太多栈帧空间也可能引起栈溢出。那么到底什么时候用递归呢递归会产生运行时开销效率低有时会重复计算可以将问题简化迭代效率高不会有额外开销有时比较难以想到综上所述如果一个问题非常复杂时递归实现的简洁性可以弥补运行时开销的话可以考虑用递归。比如斐波那契数列问题用递归的方式来解决便会非常简单但是如果用迭代的方式很难想得到递归方法int Fac(int); int main() { int ret Fac(7); printf(%d, ret); return 0; } int Fac(int n) { if (n 2) return 1; else { return Fac(n - 1) Fac(n - 2); } }非递归方法我能想到的是a、b交替相加a始终在奇数位b始终在偶数位int Fac(int); int main() { int ret Fac(8); printf(%d, ret); return 0; } int Fac(int n) { int i 2; int flag 1; int a 1, b 1; while (i n) { if (flag) { a b; flag 0; } else { b a; flag 1; } i; } if (n % 2) return a; else return b; }那么当我们使用递归方法计算第50位斐波那契数时会发现速度非常慢原因就是重复计算了很多数。计算Fac(50)需要知道Fac(49)和Fac(48)而Fac(49)有需要知道Fac(48)和Fac(47)这样Fac(48)便被重复计算了以此类推Fac(3)将会被计算非常多次最终导致效率低下