遞歸三部曲
1.define subproblem：定義子問題
2.find recursion rule: 找出遞歸規(guī)則
3.define base case: 定義退出條件
題目1
n級(jí)階梯，每次走一步或兩步拜鹤，問最多有多少種走法?
public long fibonacci(int k) {
if (k == 0) return 0;
if (k == 1 || k == 2) return 1; //base case
return fibonacci(k-1)+fibonacci(k-2); //recursion rule
}
這是斐波那契數(shù)列的一種解法境钟，算法效率極低浩习，時(shí)間復(fù)雜度是O(2^n),空間復(fù)雜度是O(n);
另一種非遞歸解法：
public long fibonacci(int k) {
if (k == 0) return 0;
if (k == 1 || k == 2) return 1;
long num1 = 1, num2 = 2, num = 0;
for (int i = 3; i <= k; i++) {
num = num1 + num2;
num1 = num2;
num2 = num;
}
return num;
}
時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(1)犬性。
題目二
求a^b的結(jié)果.
subproblem: a^b= a^(b/2)* a^(b/2)
public long power(int a, int b) {
if (a == 0) return 0;
if (b == 0) return 1;//base case
//recursion rule:
long half = power(a, b / 2);
if (b % 2 == 0) {
return half * half;
} else {
return half * half * a;
}
}
6.png
時(shí)間復(fù)雜度O(lgb),空間復(fù)雜度O(lgb)
