动力节点旗下在线教育品牌  |  咨询热线:400-8080-105 学Java全栈,上蛙课网
首页 > 文章

浅谈递归算法优缺点

08-06 16:58 296浏览
举报 T字号
  • 大字
  • 中字
  • 小字

递归算法(recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。当然,递归算法也不是万能的,它也是存在一些不足之处的,本文我们就来聊聊递归算法优缺点

一、递归算法的优点:

1.大问题化为小问题,可以极大的减少代码量;

这一点和递归算法的原理是相互契合的,递归算法的核心思想就是化繁为简。对于一个复杂的问题,把原问题分解为若干个相对简单类同的子问题,继续下去直到子问题简单到能够直接求解,也就是说到了递归的出口,这样原问题就有递归得解。

2.用有限的语句来定义对象的无限集合;

这一点看起来似乎不是很好理解,但结合实际的例子,可以大大加深我们的理解。举个最经典的例子,求斐波那契数列。

public int f(int n){  

    if(n == 1 || n == 2){     // 基线条件(递归出口)

        return 1;  

    }  

    return f(n-1) + f(n-2);    //递归条件

}

3.代码更简洁清晰,可读性更好;

在实际的编码过程中,使用递归算法的代码给人的整体感觉更加清晰,让人能够一目了然代码的核心,同时也能够使看代码的人有更好的可读性,更容易理解。由于递归算法的逻辑性思维能力更强,解决问题的方式体现在代码中就使得代码看起来格外明了。

递归算法的缺点:

1.递归调用函数,浪费空间;

尽管递归算法有着许多优点,但不得不承认递归算法的化繁为简并不是一直有那么高的效益的,实际上这种化繁为简也增加了空间的使用。递归由于是函数调用自身,而函数调用是有时间和空间的消耗的:每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址以及临时变量,而往栈中压入数据和弹出数据都需要时间。这就极大地降低了递归的效率。

2.递归太深容易造成堆栈的溢出;

调用栈可能会溢出,其实每一次函数调用会在内存栈中分配空间,而每个进程的栈的容量是有限的,当调用的层次太多时,就会超出栈的容量,从而导致栈溢出。

最后和小伙伴们分享一句话,Leigh Caldwell在Stack Overflow上说:“如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。其实凡优势就会相应的劣势,就比如递归缺点如何选择用那要看什么对你来说更重要。所以,尽管计算理论可以证明递归的作用可以完全取代循环,但某些时候我们还是应该正视递归算法的缺点,做到扬长避短,才能使递归算法应用的更加合理,而不是一昧地使用递归算法。

0人推荐
共同学习,写下你的评论
0条评论
剪刀手爱代码
程序员剪刀手爱代码

6篇文章贡献21459字

作者相关文章更多>

推荐相关文章更多>

Java数据结构

HelloWorld10-31 08:24

浅谈MySQL中SQL优化的常用方法

军哥08-12 23:29

五分钟读懂UML类图

江湖人称小李白12-10 10:41

MyBatis开发框架的四大核心

IT逐梦者08-17 21:43

一次搞定continue,break和return

HelloWorld11-06 11:19

发评论

举报

0/150

取消