迭代是人,递归是神。

说这话的意思主要是递归处理问题更加抽象,代码一般更加简洁,描述问题的解决思路也更加精辟,算法算计上相比迭代一般更难。从这个层面来讲,说递归是神也并不为过。但是依然不要忘记,计算机喜欢做重复的事情,迭代的效率相对递归要高效很多。

记得刚毕业的时候,还和小伙伴一起讨论过迭代和递归的区别。但是,直到现在我也很难给出到底是哪种方式更优秀。还是要结合具体的场景来分析,才能体现这两种方式的妙用。下面我们分别讲一下迭代和递归。

迭代

首先,我们来介绍一下迭代吧,因为迭代更加容易理解一些。

简单的说,迭代就是不断的重复某一段代码,直至结束。当然,这个迭代的开始和结束都要有明确的边界。要不然程序就不能准确的知道什么时候应该开始和结束迭代。

迭代是重复反馈过程的活动,其目的通常是为了逼近所需的目标或者结果,每一次重复被称为一次迭代,而每一次迭代的结果作为下一次迭代的初始值。

典型的形式如下:

for(int i=0; i<n; ++n){
...
}

 

 递归

递归其实也是迭代的一种形式,只不过,递归的每次调用都是调用自身。和迭代类似,递归也需要有明确的开始条件和结束条件。

个人认为递归思想更符合人类解决问题的过程,将问题由大化小,逐步解决。当所有子问题解决之后,整个问题也就解决了。这就像是我们工作的时候都要做WBS一样。所以递归设计的时候,如何划分这个递归步骤才是解决问题的核心所在。

另外,需要注意的是,相比于迭代,递归虽然在代码上更简洁,但是每一次递归都要压栈,所以递归的深度是有限制的不能无限制的进行递归下去,否则会有栈溢出。记得刚开始学习编程的时候就遇到过这样的问题。

当然各有各的好处,我们要做的就是要优势最大化。

记得当初在开发一个手机游戏引擎的时候,就有一个典型的递归应用。引擎的主体是一位清华的硕士写的(后来移民加拿大了)。引擎中各个部件的更新渲染就使用了递归。因为是手机游戏,游戏不会太复杂,加上面向对象的抽象和继。只需要对父类型进行递归,调用他们的虚函数,那么所有已经实例化的控件都可以被调用。当时看着这种用法的时候真的是眼前一亮。毕竟那时候才使用C++一年多,受益匪浅。

下面是一个递归的小例子,算出n的阶乘(n! = n * (n-1) * (n-2) * …* 1(n>0))

int recursive(int i)
{
int sum = 0;
if (0 == i)
return (1);
else
sum = i * recursive(i-1);
return sum;
}

记得上大学时,课本上有个汉诺塔的例子,也是典型的递归思想。

最后

虽然这篇文章给递归如此高的评价,但也主要是对于递归思想的赞誉。一个不懂递归的程序员,是不完整的。当然具体的开发中如何选择,并不能一概而论,也不能为了一味的秀技巧而生硬的使用递归还是要根据具体情况来做决策。

No comments yet.

Leave a comment

Comment form

All fields marked (*) are required

返回顶部
跳到底部