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

函数（3）

news 2025/5/24 15:43:34

前言

接着补充递归有关知识，这篇文章就把函数部分讲解完毕。

7.函数递归（补充）

下面是一个通过函数来进行递归，通过递归来计算一个数的阶乘。

int Fac(int n)
{if(n<=1)return 1;elsereturn n*Fac(n-1);
}int main( )
{int n =0;scanf("%d",&n);int ret = Fac(n);printf("%d\n",ret);return 0;
}

这里通过Fac函数来传入3，经过一系列递推（红线），最后得到了1，到达了限制条件，之后进行回归（蓝线），也就逐层返回并相乘，最后就实现了阶乘的实现原理。再通过主函数里的ret来接收数据，最后打印出结果。

每一次函数调用都会为本次函数调用分配内存空间（是在内存的栈区），为本次函数调用分配的内存空间叫做被称为这次函数调用的线帧空间，函数栈帧的创建和销毁。

再举一个例子，用一个函数通过递归来求斐波那契数列：

#include <stdio.h>int Fib(int n)
{if(n<=2)return 1;elsereturn Fib(n-1)+Fib(n-2);
}int main()
{int n=0;scanf("%d",&n);int ret=Fib(n);printf("%d",ret);return 0;
}

上述就是一个斐波那契数列，前两个数为1，大于2后每一个数都等于前两个数的和。用递归的时候如果传入数太大用的时间会非常长，重复的会非常多。

我们也可以用循环来写出来，循环前两个数字相加等于第三个。用这个函数来算非常的快，1000都可以算出来（但有可能不正确）。

int Fib(int n)
{int a=1;int b=1;int c=1;while(n>=2){c=a+b;a=b;b=c;n--;}return c;
}

如果我们用递归来写出来了，而且并没有发生栈溢出（stack overflow）或者效率低下，就可以用非递归来写，通常递归写的比较容易，非递归写的很复杂。如果递归没有解决，就要用非递归来写。

7.4递归有关的问题

系统分配给程序的栈空间是有限的，如果你的参数比较大，那么就会报错：stack overflow（栈溢出）这样的信息。

系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样就有可能导致一直开辟空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。

那如何解决上述的问题：

1.将递归改写成非递归

2.使用static对象替代nonstatic局部对象，在递归函数设计中，可以使用static对象替代nonstatic局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放nonstatic对象的开销，而且static对象还可以保存递归调用的中间状态，并且可为各个调用层所访问。

因为递归一次就要占用栈区的内存一次，通过转为静态可以将一部分存在静态区内，这样可以缓解一下栈区的压力，但这种缓解确实微乎其微的。