6.递归(Recursion)

递归三部曲

1.define subproblem：定义子问题
2.find recursion rule: 找出递归规则
3.define base case: 定义退出条件

题目1

n级阶梯，每次走一步或两步，问最多有多少种走法?

    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
    }

这是斐波那契数列的一种解法，算法效率极低，时间复杂度是O(2^n),空间复杂度是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;
    }

时间复杂度O(n),空间复杂度O(1)。

题目二

求a^b的结果.
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;
        }
    }

时间复杂度O(lgb),空间复杂度O(lgb)