四.递归与迭代

递归，就是在运行的过程中调用自己。

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。

迭代算法是用计算机解决问题的一种基本方法，一般用于数值计算。累加、累乘都是迭代算法的基础应用

斐波那契数列

1.递归求解

下边我们通过求斐波那契数列的例子来具体讲解一下。

在咱们开始之前我们先来讲讲什么是斐波那契数列

求第n个斐波那契数(不考虑栈溢出)

1 1 2 3 5 8 13 21 34 55 …

每前2个的数的和是第三个数，我们把拥有这种性质的数列称为斐波那契数列。

//求第n个斐波那契数
//1 1 2 3 5 8 13 21 34 55 ...
int fib(int n)
{
  if (n <= 2)
    return 1;
  else
    return fib(n - 1) + fib(n - 2);
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  int ret = fib(n);
  printf("%d ", ret);
}

示例结果

这里的图解我希望大家能自己画一下，如果你理解了上面我讲的那两个例子这对你来说应该不算很难。

递归算法的不足

我们重点先讲讲上面这段代码中出现的问题

输一个很小的数我们这个程序能完美的运行，可输入一个很大的数呢？

我们来测试一下：

没有任何结果，这是为什么呢？

我们现在想测试一下此时该函数被执行了几次

int count = 0;//全局变量
int fib(int n)
{
  if (n == 3)
    count++;
  if (n <= 2)
    return 1;
  else
    return fib(n - 1) + fib(n - 2);
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  int ret = fib(n);
  printf("%d\n ", ret);
  printf("n等于3执行了%d次 ", count);
}

当n=30时，仅仅是n=3这一种情况就被执行了30多万次，可见我们这个函数的时间复杂度有多大。

为什么会出现上述情况呢？

画图说明一下

图画的太丑辣，大家能理解我的意思就行

我们发现 fib 函数在调用的过程中很多计算其实在一直重复，这就导致我们的程序中出现的大量的重复没必要的计算浪费时间。

同时：

在调试 factorial 函数的时候，如果你的参数比较大，那就会报错： stack overflow（栈溢出）这样的信息。

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

2.使用迭代算法改进我们的代码

1.将递归改写成非递归。

2.使用 static 对象替代 nonstatic 局部对象。

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

这里对关键字static不太了解的，可以看看下面链接中的博客，在操作符部分有具体讲static的用法：【C语言初阶】万字解析,带你0基础快速入门C语言(下)

改进代码如下：

//求第n个斐波那契数
int fib(int n)
{
  int result;
  int j;
  int i;
  result = j = 1;
  while (n > 2)
  {
    n -= 1;
    //实现每一次n减小时新的n-1与n-2并赋值给n
    i = j;//把n-1的值给n-2
    j = result;//把此时n的值给n-1
    result = i + j;//n的值等于此时的(n-1)+(n-2)
  }
  return result;
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  int ret = fib(n);
  printf("%d\n ", ret);
}

看看现在的结果

这里由于int型能存放的数不够肯定栈溢出了，但是先别管结果对不对，你就说快不快吧，是不是能给你个结果？这意味着咱们把代码重复冗杂的问题解决了！

提示：

1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销

这里还有几个经典的问题比如汉诺塔和青蛙跳台阶，后面都会有具体博客去讲的。

五.扫雷游戏中的递归

另外，在改进扫雷游戏中我们也使用了递归算法，但是那个比较复杂，我也在扫雷游戏那篇博客里具体讲了，感兴趣的可以去看看，链接就放在这里啦！

【C语言】万字教学，带你分步实现扫雷游戏(内含递归函数解析)，剑指扫雷，一篇足矣

总结

以上就是今天的所有内容了，今天我们具体分析的递归算法和迭代算法，同时对比了他们之间的区别与优缺点。

如果你有任何疑问欢迎在评论区指出或者私信我，我看到后会第一时间回复的哦！

新人博主创作不易，如果感觉文章内容对你有所帮助的话不妨三连一下这个新人博主再走呗。你们的支持就是我更新的动力！！！

（可莉请求你们三连支持一下博主！！！点击下方评论点赞收藏帮帮可莉吧）