递归算法

1、定义：函数（方法）直接或间接调用自身。

• <font color=red>必须要有一个明确的结束递归的条件</font>

2、递归的基本思想: 小规模→大规模；大规模→小规模

■ 求解过程：

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

■ 拆解过程:

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

◼ <font color=red>凡是可以利用上述思想【小规模→大规模；大规模→小规模】解决问题的，都可以尝试使用递归</font>

很多链表、二叉树相关的问题都可以使用递归来解决，因为链表、二叉树本身就是递归的结构（链表中包含链表，二叉树中包含二叉树）

3、递归调用过程：

图片.png

int sum(int n){
    if(n <= 1) return n;
    return n + sum(n -1);
}

4、递归使用套路

① 明确函数的功能

• 先不要去思考里面代码怎么写， 首先搞清楚这个函数的干嘛用的，能完成什么功能？

② 明确原问题与子问题的关系

• 寻找 f(n) 与 f(n – 1) 的关系

③ 找出边界条件

思考问题规模小到什么程度可以直接得出解？

5、经典的递归算法

(1) 斐波那契数列

(2) 上楼梯（跳台阶）

(3) 汉诺塔

■ 斐波那契数列

• 斐波那契数列：1、1、2、3、5、8、13、21、34、……

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

■ 上楼梯（跳台阶）

• 楼梯有 n 阶台阶，上楼可以一步上 1 阶，也可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法？

  • 假设 n 阶台阶有 f(n) 种走法，第 1 步有 2 种走法

    如果上 1 阶，那就还剩 n – 1 阶，共 f(n – 1) 种走法

    如果上 2 阶，那就还剩 n – 2 阶，共 f(n – 2) 种走法

    所以 f(n) = f(n – 1) + f(n – 2)

int climbStairs(int n){
    if(n <= 2) return 1;
    return climbStairs(n -1) + climbStairs(n -2);
}

■ 汉诺塔

• 其实分 2 种情况讨论即可

  • 当 n == 1时，直接将盘子从 A 移动到 C

  • 当 n > 1时，可以拆分成 3大步骤:

    ① 将 n – 1 个盘子从 A 移动到 B

    ② 将编号为 n 的盘子从 A 移动到 C

    ③ 将 n – 1 个盘子从 B 移动到 C

    步骤 ① ③ 明显是个递归调用

// 将第i号盘子 从 from 移动到 to
void move(int i, String from, String to){
    System.out.println(i + "号盘子" + from + "->" + to);
}

/**
* 将n个盘子从柱子p1 经过柱子 p2 的协助 移动到 p3
*/
void hanoi(int n, String p1, String p2, String p3){
    if(n <= 1){
        move(n, p1, p3);
        return;
    }
    hanoi(n-1, p1, p3, p2);//将n-1个盘子从柱子p1 经过柱子p3 的协助移动到了 p2
    move(n, p1, p3);
    hanoi(n-1, p2, p1, p3);//将n-1个盘子从柱子p2 经过柱子p1 的协助移动到了 p3
}

6、递归转非递归

递归100%可以转换成非递归

(1) 递归过程中的数据存储：

递归调用的过程中，会将每一次调用的参数、局部变量都保存在了对应的栈帧（Stack Frame）中

• 栈帧：调用方法所需要的内存空间(内存空间：存储数据，比如形参、局部变量)

(2) 递归转非递归

■ 自己构建一个栈

• 原理：模拟函数调用栈

■ 利用 重复迭代某个变量 替换掉栈帧中存储的变量

7、递归注意事项：

(1) 使用递归不是为了求得最优解，是为了简化解决问题的思路，代码会更加简洁

• 递归求出来的很有可能不是最优解，也有可能是最优解

(2) 使用尾递归可以对递归进行优化

如果本文对你有帮助的话记得给一乐点个赞哦，感谢！