转载

Java|递归算法计算

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

问题描述

在本周的 java 框架学习中，在讲述 aop 的时候，利用测试递归和迭代两种方式计算斐波拉契数列的效率进行了讲解，由于 java 基础知识不牢固，所以又回顾了递归这种方法。以下是对这种方式的学习见解。

具体内容

一.斐波拉契数列的概念：

指的是这样一个数列： 1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34 、 …… 在数学上，斐波那契数列以如下被以递推的方法定义： F(1)=1 ， F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3 ， n ∈ N* ）

二.递归算法

什么是递归？通俗点来讲就是“我自己调用自己”。利用一个简单的例子来讲解：

public class Test {
public static void main(String[] args) {
a();

}
static void a(){
System.out.println(" 禁止套娃 ");
a();
}
}

来看看有什么问题

Java|递归算法计算

很明显，这个程序自己给跑死了。

Java|递归算法计算

这个程序就这样无休止的调用 a 方法。所以完整的递归，还需要一个什么时候停止的条件，称之为递归头。

接下来完善一下上面的代码，添加递归头。

public class Test {
public static void main(String[] args) {
a();

}
static int i;
static void a(){
System.out.println(" 禁止套娃 ");
i++;
if (i<5){
a();
}else {
return;
}

}
}

Java|递归算法计算

现在已经了解了递归算法，接下来就正式来计算斐波拉契数列。

public long calFibonacciByRecursive(long n) {
if (n == 1) {
return 1;
}
else if (n==2){
return 1;
}

return calFibonacciByRecursive(n-2)+calFibonacciByRecursive(n-1);
}

三.迭代算法代码（用作对比）

这是迭代循环的方法：

public long calFibonacciByLoop(long n) {
long n1 = 1;
long n2 = 1;
long n3 = 0;
for (int i = 0; i <n ; i++) {
n3 = n1 + n2;
n1 = n2;
n2 = n3;

}

return n3;
}

结语

下面的效果是对两种方式的效率统计。通常来讲，能用递归的情况，都可以利用循环的方式来解决，但是应该尽量避免使用递归的方式来解决问题。虽然代码简单，但是这样的程序对占用大量内存，并不利于开发，要尽可能的提高程序效率。

Java|递归算法计算