斐波那契数
509. 斐波那契数,这一题非常适合入门练习递归,题目所提供的实例很明显的就能看出递归形式,只需要思考在什么时候退出递归即可。附上第一次提交代码:
1 2 3 4 5 6
| class Solution { public int fib(int n) { if(n < 2) return n; 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的数组实现,实际上可以替换成两个变量来交替计算即可。这道题过于简单,是一个练习和理解递归的入门第一题。