`
mixer_a
  • 浏览: 338358 次
社区版块
存档分类
最新评论

关于笔算递归的通用算法——迭代

 
阅读更多

递归是是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。

在我的印象中,我第一次接触递归是在C语言书中,让求n!的解,记得程序如下:

函数的调用对应着入栈,调用的结束对应着出栈,如上面的过程,假如传入的参数为3,程序run的时候,会先将fun(3)入栈,接着会将fun(2)入栈,最后会将fun(1)入栈,计算结束之后,会按照fun(1),fun(2),fun(3)依次出栈。从上面的过程我们可以看出,在每次计算的时候,该项的结果都会依附前一项,前一项的结果依附前一项的前一项,以此类推,知道递归的终止条件。这是计算机在遇到递归的时候的做法。

假如我们现在在进行人生很重要的一次笔试,笔试题中给出了一个递归函数,给了你一个参数,你还要像计算机一样子,从外到内一层一层计算吗?如果从外到内计算的话,最后的结果很可能是你自己把自己给绕进去了。

下面提供一种比较通用的人算递归的解法:

从递归终止的条件开始,一项项的向后推,如果递归函数的参数有一个,则建立一个一维数组,如果参数有n个,则建立一个n维数组。还用上面的例子,首先建立一个数组,长度为3(因为给定的参数为3,而且在函数中,不会出现比参数更大的值),先计算fun(1),结果为1,再计算fun(2),fun(2)依附fun(1),fun(1)的结果在前面已经算出来了,存放在一维数组中,所以可以直接用,不用再算,以此类推,最后可以很容易算出fun(3)。

如果要给上面的算法归类,它应该是迭代算法。迭代算法是只根据迭代公式(递推公式),从起始项(递归终止项)开始,一步步计算,直到得到想要的结果。

下面再看一个例子,ackerman递归的求解算法,该算法出现在过一家大公司的笔试题中,当时直接就被搞晕了,结束之后,就总结一下人解递归的方法,于是就有了这篇博客。

ackerman算法程序如下:

给定的参数为m=3,n=3,即让求解ack(3,3)的值,当时一看到题,就直接从外到内一层一层的算,没算几步,就把自己给绕进去了。如果用动态规划的话,首先建立一个二位数组,大小应该3*3的,如果不够还需要增加大小。
其实在写程序的时候,应该尽量避免使用递归,将递归转换成迭代算法,可以减少很多运算,因为使用递归的时候,有些值已经在前面算出来过了,在后面还需要再算一次,迭代可以很好解决这一弊端。或许有人该问了,既然递归可以用迭代代替,为什么还有递归?个人觉得,递归是一种思想,可以利用这种思想解决问题,在实现的时候,可以转换成迭代。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics