算法--策略-递归

函数直接或间接调用自身

函数的调用过程

如果递归调用没有终止, 将会一直消耗栈空间, 最终导致栈溢出

所以必须有一个明确的结束递归条件, 也叫作边界条件, 递归基

递归不是为了得到最优解, 是为了简化解决问题的思路, 代码更加简洁

空间复杂度

调用过程

递归过程

基本思路

拆解问题

• 把大规模问题变成规模较小的同类型问题
• 规模小的问题, 继续变成更小的问题
• 规模小到一定程度可以直接得出它的解

求解

• 由小规模问题的解得出较大规模问题的解
• 较大规模问题的解不断得出规模更大问题的解
• 最后得出原来问题的解

链表, 二叉树相关问题都可以用递归来解决

套路

1. 明确函数的功能, 搞清楚这个函数是干什么用的, 完成的功能
2. 明确原问题与子问题的关系, 找到f(n) 和f(n - 1) 的关系
3. 明确递归基, 边界条件, 问题规模小到什么程度可以直接得出解

例, 斐波那契

/**
     * 使用递归实现
     * @param n
     * @return
     */
    int fib0(int n) {
        if (n <= 2) {
            return 1;
        }
        int res1 = fib0(n - 1);
        int res2 = fib0(n - 2);
        return res1 + res2;
    }

递推式T(n) = T(n - 1) + T(n - 2) + O(1), 时间复杂度O(2^n)

空间复杂度O(n)

递归调用的空间复杂度 = 递归深度 * 每次调用所需的辅助空间

递归过程2

递归调用过程中出现了很多的重复计算

优化1, 记忆化

用数组存放计算结果, 避免重复计算

    /**
     * 数组每个位置上, 放入计算的结果, 如果有值, 直接取值
     * @param n
     * @return
     */
    int fib1(int n) {
        if (n <= 2) return 1;
        int[] array = new int[n + 1];
        array[1] = array[2] = 1;
        return fib1(n, array);
    }
    
    int fib1(int n, int[] array) {
        if (array[n] == 0) {
            array[n] = fib1(n - 1, array) + fib1(n - 2, array);
        }
        return array[n];
    }

时间复杂度和空间复杂度都为O(n)

优化2

不适用递归调用, 直接使用数组

    /**
     * 自底向上计算值, 存在数组中
     * @param n
     * @return
     */
    int fib2(int n) {
        if (n <= 2) return 1;
        int[] array = new int[n + 1];
        array[1] = array[2] = 1;
        for (int i = 3; i <= n; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }
        return array[n];
    }

时间和空间复杂度还是O(n)

优化3

每次运算只需要用到数组的两个元素, 所有可以使用滚动数组来优化

    int fib3(int n) {
        if (n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n; i++) {
            array[i % 2] = array[(i - 1) % 2] + array[(i - 2) % 2];
        }
        return array[n % 2];
    }

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

优化4

使用位运算取代模运算

    int fib4(int n) {
        if (n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n; i++) {
            array[i & 1] = array[(i - 1) & 1] + array[(i - 2) & 1];
        }
        return array[n & 1];
    }

优化5

使用两个变量来记录之前的结果

    int fib5(int n) {
        if (n <= 2) return 1;
        int first = 1;
        int second = 1;
        for (int i = 3; i <= n; i++) {
            second = first + second;
            first = second - first;
        }
        return second;
    }

优化6

使用线性代数解法, 特征方程

    /**
     * 特征方程
     * @param n
     * @return
     */
    int fib6(int n) {
        double c = Math.sqrt(5);
        return (int)((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
    }

例, 上楼梯

楼梯有n 阶, 上楼可以一步上1 阶, 也可以上2 阶, 走完n 阶共有多少种走法

• 假设n 阶台阶, 有f(n) 种走法, 第一步有2 中走法
  • 如果上1 阶, 那就还剩n - 1, 共有f(n - 1) 种走法
  • 如果上2 阶, 那就还剩n - 2 阶, 共有f(n - 2) 种走法
• 所以f(n) = f(n - 1) + f(n - 2)

上台阶

    public static void main(String[] args) {
        ClimbStairs cl = new ClimbStairs();
        System.out.println(cl.climbStairs(10));
    }
    
    int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

例, 汉诺塔

把A 的n 个盘子移动到C, 盘子编号为[1, n]

每次只能移动1 个盘子, 大盘子只能放在小盘子下面

移动1个盘子 移动2个盘子 移动3个盘子 移动3个盘子1

思路:

2 种情况

• 当n == 1, 直接将盘子从A 移动到C
• 当n > 1, 分为3 个步骤
  • 1. 将n - 1 个盘子从A 移动到B
  • 2. 将编号为n 的盘子从A 移动到C
  • 3. 将n - 1 个盘子从B 移动到C
  • 步骤1, 和3 为递归调用

移动n个盘子 移动n个盘子最后一步

    public static void main(String[] args) {
        new Hanoi().hanoi(3, "A", "B", "C");
    }
    
    void hanoi(int n, String p1, String p2, String p3) {
        if (n == 1) {
            move(n, p1, p3);
            
            return;
        }
        
        hanoi(n - 1, p1, p3, p2);
        move1(n, p1, p3);
        hanoi(n - 1, p2, p1, p3);
    }
    
    void move(int no, String from, String to) {
        System.out.println("(1)将" + no + "号盘子从" + from + "移动到" + to);
    }

时间复杂度T(n) = 2 * T(n - 1) + O(1)

O(n^2)

空间复杂度 O(n)

尾调用

一个函数的最后一个动作为调用函数

如果最后一个动作是调用自身, 称为尾递归, 一些编译器对尾调用进行优化, 以达到节省栈空间的目的

尾调用优化, 也叫尾调用消除

如果当前栈帧上的局部变量等内容都不需要用了, 单签栈帧经过适当的改变后, 可以直接当做尾调用的函数的栈帧使用, 程序可以jump 到尾调用的函数代码

生成栈帧改变代码与jump 的过程称作尾调用消除, 或尾调用优化, 尾调用优化让位于尾位置的函数调用跟goto 语句性能一样高

尾调用

阶乘

    static int facttorial2(int n) {
        if (n <= 1) return n;
        return n * facttorial(n- 1);
    }
    // 尾调用优化
    static int facttorial(int n) {
        return facttorial(n, 1);
    }
    
    static int facttorial(int n, int result) {
        if (n <= 1) return result;
        return facttorial(n - 1, result * n);
    }

斐波那契尾调用优化

    static int fib(int n) {
        if (n <= 2) return 1;
        return fib(n, 1, 1);
    }
    
    static int fib(int n, int first, int second) {
        if (n <= 1) return first;
        return fib(n - 1, second,first + second);
    }