1一乐

V1

2022/08/17阅读:16主题:默认主题

递归算法


1、定义:函数(方法)直接或间接调用自身。

  • 必须要有一个明确的结束递归的条件

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

■ 求解过程:

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

■ 拆解过程:

  • 把规模大的问题变成规模较小的同类型问题
  • 规模较小的问题又不断变成规模更小的问题
  • 规模小到一定程度可以直接得出它的解
凡是可以利用上述思想【小规模→大规模;大规模→小规模】解决问题的,都可以尝试使用递归

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



3、递归调用过程:

int sum(int n){
 if(n <= 1return 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 <= 2return 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 <= 2return 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) 使用尾递归可以对递归进行优化

分类:

后端

标签:

后端

作者介绍

1一乐
V1