赣州网站建设jx25,网站开发技术是,海南省住房和建设厅网站首页,免费主题大全下载前言 在上一篇博客函数递归详解#xff08;一#xff09;中讲解了什么是递归#xff0c;递归的思想及限制条件以及两个递归的例子#xff0c;这一篇博客将讲解递归与迭代的关系。
递归与迭代 递归是一种很好的编程技巧#xff0c;但是同很多技巧一样也是可能被误用的一中讲解了什么是递归递归的思想及限制条件以及两个递归的例子这一篇博客将讲解递归与迭代的关系。
递归与迭代 递归是一种很好的编程技巧但是同很多技巧一样也是可能被误用的就像函数递归详解一中的举例1一样看到推导公式就很容易写出地递归形式的代码 int Fact(int n)
{if (n 0)return 1;elsereturn n * Fact(n - 1);
}
Fcat函数是可以产生正确的结果但是在递归调用的过程中设计一些运行的开销 。 在C语言中每一次函数调用都要需要为本次函数调用在栈区申请一块内存空间来保存 函数调用期间的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。 函数不返回函数对应的栈帧空间就一直占用 所以如果函数调用中存在递归调用的话每一次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。 所以如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢出(stack overflow)的问题。⭐所以如果不想使用递归就得想其他的办法通常就是迭代的方式(通常就是循环的方式) . 比如计算n的阶乘也是可以使用迭代的方式进行解决并且效率比递归更高。
int Fact(int n)
{int i 0;int ret 1;for(i1;in;i){ret * i;}return ret;
}
事实上我们看到的许多问题都是以递归的形式进行解释的只是因为它比非递归形式更加清晰但是这些问题的迭代实现往往比递归实现效率更高。
但是当一个问题非常复杂难以用迭代的方式实现时此时递归的简洁性便可以补偿它所带来的开销。 举例3求第n个斐波那契数列
我们也能举出更加极端的例子就像计算第n个斐波那契数是不适合用递归求解的但是斐波那契数的问题也是可以通过使用递归的形式描述的如下 看到上述公式很容易诱导我们将代码写为递归的形式如下
int Fib(int n)
{if(n2)return 1;elsereturn Fib(n - 1) Fib(n - 2);
} 测试代码
int Fib(int n)
{if(n2)return 1;elsereturn Fib(n - 1) Fib(n - 2);
}
int main()
{int n 0;scanf(%d, n);int retFib(n);printf( %d\n, ret);return 0;
} 当我们n输入50的时候需要很长的时间才能算出结果或者根本算不出结果这个计算所耗费的时间是我们很难接受的这也说明递归的写法是非常低效的那是为什么呢 我们看下面这个递归示意图 其实递归程序会不断的展开在展开的过程中我们很容易就能发现在递归中有重复计算而且递归层次越深冗余计算就会越多我们可以做一个测试
测试代码
int count 0;
int Fib(int n)
{ if (n 3)count;if(n2)return 1;elsereturn Fib(n - 1) Fib(n - 2);
}
int main()
{int n 0;scanf(%d, n);int retFib(n);printf( %d\n, ret);printf(在递归过程中总共计算了%d次\n, count);return 0;
}我们定义一个全局变量count当计算到第3个斐波那契数的时候我们让count运行程序计算第40个斐波那契数我们看一下第3个斐波那契数重复计算了多少次 。
结果如下 当我们计算第40个斐波那契数的时候过程中仅仅第3个斐波那契数就被重复计算了39088169次足以看出递归过程中的开销有多么巨大。 那么我们知道斐波那契数的前两个都是1前两个相加便是第三个数那么我们从前往后从大到小计算就可以了于是便有如下的迭代代码 int Fib(int n)
{int a 1;int b 1;int c 1;while(n3){c a b;a b;b c;}return c;
}
用迭代的方式区实现这个代码效率高出很多。
有时候递归虽好但是也会引出一些问题所以一定不要迷恋递归适可而止就好。 递归和迭代的选择 1.如果使用递归写代码非常容易写出的代码没问题那就可以使用递归解决。 2.如果使用递归写出的代码缺陷非常明显那就不能使用递归考虑使用迭代解决问题。 以上便是我为大家带来的函数递归的第二部分内容若有不足望各位大佬在评论区指出谢谢大家可以留下你们点赞、收藏和关注这是对我极大的鼓励我也会更加努力创作更优质的作品。再次感谢大家
