递归和迭代

发表于 更新于 分类于 阅读次数：

递归

概念：

程序调用自身的编程技巧称为递归,是函数自己调用自己.
一个函数在其定义中直接或间接调用自身的一种方法,它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大的减少代码量.递归的能力在于用有限的语句来定义对象的无限集合.

递归分为两个阶段：

  1. 递推:把复杂的问题的求解推到比原问题简单一些的问题的求解;
  2. 回归:当获得最简单的情况后,逐步返回,依次得到复杂的解.

实现

斐波那契数列:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 斐波那契数列为:0,1,1,2,3,5...
# fib(0)=0;
# fib(1)=1;
# fib(n)=fib(n-1)+fib(n-2);

public static int fib(int n) {
		
		if(n==0)
			return 0;
		
		else if (n==1|n==2) 
			return 1;
		
		else 
			 return fib(n-1)+fib(n-2);
		
	}

迭代

概念：

利用变量的原值推算出变量的一个新值，迭代就是A不停的调用B.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 迭代实现斐波那契数列
public static int iteration(int n) {
	if (n == 1 || n == 2) {
		return 1;
	} else {
		int f1 = 1;
		int f2 = 1;
		int f3 = 0;
		for (int i = 2; i < n; i++) {
			f3 = f1 + f2; // 利用原值推算出新值
			f1 = f2;
			f2 = f3;
		}
		return f3;
	}
}

参考文章

  1. 迭代wiki
  2. 递归wiki