【C语言】带你玩转递归,迭代算法2

简介: 【C语言】带你玩转递归,迭代算法

四.递归与迭代

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

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

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

斐波那契数列

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);
}

示例结果

4bb6b1f3fbeb4971bb90fc20fb8aefa9.png

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

递归算法的不足

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

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

我们来测试一下:

15bd8aae63604908904592d9c4a3adec.png

没有任何结果,这是为什么呢?

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

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);
}

abe7826b06a24b3883b87fbd61d3eaf3.png


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

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

画图说明一下

3f81d506ae6b4d55998ded4b1579d627.png

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

我们发现 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);
}

看看现在的结果


6fb79b6054854336b27e2eb5f6ecf995.png

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

a6f96a23b44e4665a0b382d216d3e080.png

提示:

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

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

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


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


五.扫雷游戏中的递归

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

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

总结

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

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

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


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


20fa3306e76244de9879742c165c792a.gif

目录
相关文章
|
2天前
|
存储 算法 数据管理
C语言算法复杂度
【10月更文挑战第20天】
C语言算法复杂度
|
8天前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
32 7
|
20天前
|
C语言
c语言回顾-函数递归(上)
c语言回顾-函数递归(上)
29 2
|
20天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
14 1
|
19天前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法
|
20天前
|
C语言
c语言回顾-函数递归(下)
c语言回顾-函数递归(下)
35 0
|
20天前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
29 0
|
28天前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
2月前
|
资源调度 算法
基于迭代扩展卡尔曼滤波算法的倒立摆控制系统matlab仿真
本课题研究基于迭代扩展卡尔曼滤波算法的倒立摆控制系统,并对比UKF、EKF、迭代UKF和迭代EKF的控制效果。倒立摆作为典型的非线性系统,适用于评估不同滤波方法的性能。UKF采用无迹变换逼近非线性函数,避免了EKF中的截断误差;EKF则通过泰勒级数展开近似非线性函数;迭代EKF和迭代UKF通过多次迭代提高状态估计精度。系统使用MATLAB 2022a进行仿真和分析,结果显示UKF和迭代UKF在非线性强的系统中表现更佳,但计算复杂度较高;EKF和迭代EKF则更适合维数较高或计算受限的场景。
|
3月前
|
机器学习/深度学习 存储 并行计算
C语言与机器学习:K-近邻算法实现
C语言与机器学习:K-近邻算法实现
54 0