数据结构Java版之递归与迭代算法(五)

时间:2024-07-28 11:05:14

  递归的概念很简单,就是自己调用自己

  而迭代,则是通过修改初始化数据,得到中间结果,然后不断的对中间结果进行修改,而得到最终结果。简单来说迭代就是循环

在此,我们用一个比较经典的Fibonacci数列来说明递归与迭代的区别。  先介绍一下Fibonacci数列:

  无穷数列 1,1,2,3,5,8,13,......称为Fibonacci数列

  除了第一个数和第二个数都等于 1 。后续的数都是前两个数之和。

递归版Fibonacci :

public int fibonacci(int n) {
if(n == 1 || n == 2) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}

迭代版Fibonacci:

public int fibonacci(int n) {
if(n == 1 || n == 2) return 1;
int result = 0, pre1 = 1, pre2 = 1;
for(int i = 3; i <= n; i ++) {
result = pre1 + pre2;
pre1 = pre2;
pre2 = result;
}
return result;
}