搜索
写经验 领红包
 > 健康

java中的递归方法将整数倒置(java的递归写法)

导语:Java中的递归方法

递归算法

1.递归算法

递归在计算机科学中也称为递归算法。一些问题在分解的时候会有这样的现象:解决该问题的过程是由重复的相似子过程组成,类似这样的问题我们都可以通过递归算法进行解决。在计算机语言中,递归算法的实现靠函数的自我调用来完成,我们所见到的大多数高级编程语言都支持这样的做法。

递归算法通常有两种方式实现——普通递归和尾递归。递归方法简单的来说就是方法的内部再次调用自身,递归方法会嵌套的参与运算。这样每一个递归方法都要分配一个函数堆栈进行操作,这就是普通递归。普通递归对内存的消耗是非常大的。

另一种递归方式被称为尾递归,尾递归对普通递归进行了优化。如果使用尾递归,需要将递归方式进行特殊的设计,它需要将递归方法在return语句后进行单独调用(即尾调用)。当采用尾递归的时候,一些编程语言会进行优化,将所有嵌套的递归方法放在同一个函数堆栈中进行,效率非常快。作为一名Java程序员,如果你无法将递归方法设计成尾递归的模式也没有任何问题,因为Java并没有对尾递归进行优化 ,Java对内存的优化是依赖于回收机制。但是如果你是一名C程序员,就需要对尾递归的写法进行掌握了。

递归算法的优缺点是非常明显,算法实现简单、可读性强是递归算法的优点所在。缺点也同样明显,递归算法会占用大量内存空间,如果递归深度过大,容易发生内存相关问题。所以在递归算法中,有这样一句话:不用递归累死,滥用递归慢死。如何合理的使用递归算法,是递归使用的关键问题。

2.怎么使用递归

在设计递归算法的时候,一定要注意两点:1、设计出等价的递归公式。这一点需要我们拥有一些数学基础以及抽象概括能力,能够在复杂的运行过程中,抽象出等价的函数关系。

2、递归退出的条件。这一点尤为重要,如果递归方法没有结束条件,就如同死循环一样,让内存和CPU直接。常见的递归练习方法有斐波那契数列和汉诺塔移动算法。

2.1 斐波那契数列(Fibonacci sequence)

斐波那契数列是经典的递归算法应用,它是一组有规律数列:,当我们要获取数列中第n位的数字时,可以总结如下公式:

当n=1或者2时,有f(n)=1,当>=3时,有f(n)=f(n-1)+f(n-2)

下面我们要设计一个方法,输出数列的前n位的信息,n通过整型参数控制。如果我们需要一个完整的数列,就需要创建一个数列容器,将数列中的每一位数字依次计算出来,并保存到容器中,最后按照顺序从容器中输出数列(如下列Java示例):

使用数组保存斐波那契数列

采用上面的做法好处非常明显,它能够记录每一位数列的值。当我们需要获取整个数列的时候,这样的方式是可取的。在一些时候,我们只想获取其中一位的数值,我们就不需要记录数列,这个时候使用递归的方式就非常方便(如下Java示例所示):

采用上述代码,可以直接获取到数列中第n位的数值。我们可以发现,使用递归的方式让代码更简洁、阅读起来更友好。下面我们创建两个测试方法,对上述两种方式进行测试:

运行结果:

2.2 汉诺塔(Hanoi)

汉诺塔是一种有趣的益智游戏,很多人在儿时都玩过这种类似的玩具(如下图所示):

汉诺塔

汉诺塔的移动规则是将所有圆盘从A柱移动到C柱上,并保持上小、下大的有序顺序摆放。在移动的过程中,也需要保持这个规则。例如上图的三层汉诺塔,我们在移动的时候有如下步骤(如下图所示):

三层汉诺塔移动步骤

如果有多个盘子,我们设盘子总数为n,我们可以分为两部分解决,一部分是上面的n-1个盘子,它们作为一个整体,另一部分是最下面的盘子n。它们移动可以分为三步:

1.将第一部分的n-1个盘子的作为一个整体,从A移动到B柱上,C柱过度。

2.接着将第n个盘子从A柱移动到C柱上。

3.再将n-1个盘子的整体从B柱移动到C柱上,A柱过度(移动规律如下图所示)。

N个盘子移动时的规律总结

用代码实现的时候,我们就可以利用递归的方式进行移动。下面代码中,我们为了观察移动过程中,各柱子上盘子的变化情况,我们用队列来模拟柱子(实现代码如下所示):

运行结果:

3.递归对循环的替代

在程序开发过程中,很多循环方法都可以使用递归来完成,例如数字的累加和阶层的计算(如下面代码所示)。

运行结果:

在上述示例代码中,我们用递归和非递归两种方式解决了累加、阶乘的循环问题。除此之外,在一些数据结构算法中,递归的使用也非常多,比如二叉树的遍历、排序等。在下面的示例中,我们使用递归的方法进行冒泡排序。

示例运行效果:

传统的冒泡排序需要借助双层循环进行排序交换。如果使用递归的方式,可以减少一层循环。在实际的排序中,我们是不推荐使用递归进行排序的,上述示例仅作为递归算法的一种思考。

免责声明:本站部份内容由优秀作者和原创用户编辑投稿,本站仅提供存储服务,不拥有所有权,不承担法律责任。若涉嫌侵权/违法的,请反馈,一经查实立刻删除内容。本文内容由快快网络小葵创作整理编辑!