Java|递归算法计算
- 2020 年 3 月 31 日
- 筆記
问题描述
在本周的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(); } } |
|---|
来看看有什么问题
很明显，这个程序自己给跑死了。
这个程序就这样无休止的调用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; } } } |
|---|
现在已经了解了递归算法，接下来就正式来计算斐波拉契数列。
|
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; } |
|---|
结语
下面的效果是对两种方式的效率统计。通常来讲，能用递归的情况，都可以利用循环的方式来解决，但是应该尽量避免使用递归的方式来解决问题。虽然代码简单，但是这样的程序对占用大量内存，并不利于开发，要尽可能的提高程序效率。
END
