c语言基础知识帮助理解（函数递归详解）

"从前有座山，山里有座庙，庙里有个老和尚和一个小和尚。有一天老和尚对小和尚说:“从前有座山.山里有座庙，庙里有个老和尚和一个小和尚，有一天老和尚对小和尚说：“从前有座山.山里有座庙，庙里有个老和尚和一个小和尚......" （虽能体现递归特点，但又不是递归）

1.什么是递归

当一个函数在其定义中调用自身的过程称为递归。递归是一种强大的编程技巧，可以解决许多问题，特别是那些可以被分解为相同问题的子问题的情况

递归的主要思考方式在于：把大事化小。

在C语言中，函数递归的基本原理是将一个大问题分解为一个或多个更小的问题，然后通过调用自身来解决这些更小的问题，直到达到基本情况，即不再需要递归调用的情况

2.递归的两个必要条件

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

试想如若没有限制条件，那便无限循环，真就成了上面的“从前有座山 山里有座庙” 的故事了。

3.事例和讲解

用递归来实现求n的阶乘（factorial） ：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int factorial(int n)
{
  if (n > 1)//递归终止的条件
  {
    return n * factorial(n - 1);
  }
  else
  {
    return 1;
  }
}
int main()//递归实现求n的阶乘
{
  int n = 0;
  scanf("%d", &n);
  int n_factorial = factorial(n);
  printf("%d", n_factorial);
  return 0;
}

下面是一个示例的递归树，用于说明计算4的阶乘的过程：

4! = 4 * 3!

|

3! = 3 * 2!

|

2! = 2 * 1!

|

1! = 1

下面讲解一下思路：

• 最基本便是：n！=n*（n-1）！——让我们有了返回n * factorial(n - 1)的想法
• 当n=1时，便是终止条件——返回1 ，使用factorial(n - 1)也是为了更加靠近n=1的终止条件

4.递归原理讲解

当一个函数被调用时，会在内存中分配一个称为函数栈帧（Function Stack Frame）的数据结构。函数栈帧用于存储函数的局部变量、函数的参数、函数的返回地址等信息。

下面是一个示意图，展示了函数栈帧的结构：

• Return Address：保存着函数调用结束后需要返回的地址，即函数调用的下一条指令的地址。当函数执行完毕后，CPU会根据该地址跳转到正确的位置继续执行
• Previous Stack Frame：指向调用函数的函数栈帧的地址，用于在函数返回时恢复调用函数的上下文
• Local Variables：存储函数的局部变量。每个函数栈帧都有自己的一块内存空间，用于存储局部变量的值
• Parameters：存储函数的参数。参数在函数调用时被传递给函数，并存储在函数栈帧中

在递归函数中，每次递归调用都会生成一个新的函数栈帧，这些函数栈帧会按照一定的顺序依次排列在内存中：先调用的函数先进入栈中，后销毁

5.递归弊端

5.1利用计算斐波那契数列来引入

int Fib(int n)
{
  if (n <= 2)
    return 1;
  else
    return Fib(n - 1) + Fib(n - 2);
}
int main()
{
  int n = 3;
  printf("第三个斐波那契数%d\n", Fib(n));
  int x = 50;
  printf("第五十个斐波那契数%d", Fib(x));
  return 0;
}

我们会发现，第三个斐波纳契数立马就出来了，而第五十个迟迟不出来。

这就暴露了问题：

• 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间
  
• 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃（我已经为各位试过了，不要再试了），也就是栈溢出了
  

这也说明：有时递归的效率不是很高 ，而且不得不说有时递归代码的可读性是不及循环的

5.2如何改进

那我们如何改进呢？

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

下面便用循环来改写求斐波那契数列：

int Fib(int n)
{
  int n1 = 1;
  int n2 = 1;
  int result = 0;
  while (n > 2)
  {n--;
    result = n1 + n2;
    n1 = n2;
    n2 = result;
  }
  return result;
}
int main()
{
  int n = 3;
  printf("第三个斐波那契数%d\n", Fib(n));
  int x = 30;
  printf("第三十个斐波那契数%d", Fib(x));
  return 0;
}

所以我们也不要一味地去使用递归在合适的代码里使用合适的方法才能让我们的编程水平更加出色。

总之，递归是一项强大的编程技术，但在使用时需要注意栈溢出问题。通过合理的算法设计和对函数栈帧的了解，我们可以更好地应对递归问题，使代码更加健壮和可靠

这次的分享先到这里的，感谢大家的支持，下一次会总结数组相关的知识！！！