斐波那契数

509. 斐波那契数,这一题非常适合入门练习递归,题目所提供的实例很明显的就能看出递归形式,只需要思考在什么时候退出递归即可。附上第一次提交代码:

1
2
3
4
5
6
class Solution {
public int fib(int n) {
if(n < 2) return n; // n == 1也可以
return fib(n - 1) + fib(n - 2);
}
}

递归是非常消耗资源的,因为递归过程中,前面的调用栈是不会被回收的,除了一些支持尾递归的语言除外。将递归的每一个步骤解析出来可以发现,之前重复计算了很多次,因此使用一个数组来记录下计算的数据,可以有效地减少递归次数。这是一种典型的内存换效率的做法,具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
static int[] mem = new int[100000];
static {
mem[0] = 0;
mem[1] = 1;
mem[2] = 1;
}
public int fib(int n) {
if(n < 2 || mem[n] != 0) return mem[n];
else mem[n] = fib(n - 1) +fib(n - 2);
return mem[n];
}
}

下面附上最后一次提交,使用长度为2的数组来完成这题:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
int[] temp = new int[2];
temp[1] = 1;
int i = 2;
for(; i <= n; i++) {
temp[i % 2] = temp[0] + temp[1];
}
return temp[n % 2];
}
}

在这使用了长度为2的数组实现,实际上可以替换成两个变量来交替计算即可。这道题过于简单,是一个练习和理解递归的入门第一题。