The World Best ST.

递归学习

算法 递归
字数统计: 655阅读时长: 2 min
2020/03/16 Share

递归

刷leetcode做算法题经常会遇到需要使用递归来解答的题目，总是在能做出来的边缘，差那么点火候。算法这块实在是太菜了，需要好好地补补课。故学习了一些大神总结的递归学习法，这里做一些笔记，希望之后遇到递归题目的时候能顺利的解答出来。

递归的三大要素

第一：明确你这个函数想要干什么

例如：

1
2
3
4
// 算 n 的阶乘(假设n不为0)
int f(int n){

}

这个函数的功能就是计算n的阶乘

第二：寻找递归结束条件

所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，不然的话，会一直调用自己，进入无底洞。也就是说，我们需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。

例如：

1
2
3
4
5
int f(int n){
    if (n == 1) {
        return 1;
    }
}

第三：找出函数的等价关系式

寻找原函数的一个等价关系式，例如：f(n) = n * f(n-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//用递归的方法反转链表
 2public static Node reverseList2(Node head){
    // 1.递归结束条件
    if (head == null || head.next == null) 
    {
        return head;
    }
    // 递归反转 子链表
    Node newList = reverseList2(head.next);
    // 改变 1，2节点的指向。
    // 通过 head.next获取节点2
    Node t1  = head.next;
    // 让 2 的 next 指向 2
    t1.next = head;
    // 1 的 next 指向 null.
    head.next = null;
    // 把调整之后的链表返回。
    return newList;
}

递归的优化方法

考虑是否重复计算

根据这3个要素，即可以写出递归函数，但递归如果不进行优化，则有很多子问题被重复计算。

一般我们可以把我们计算的结果保存起来，用HashMap或者用数组，通过下表获取n对应的值。典型的用空间换时间的做法。

考虑是否可以自底向上

递归我们一般都是从上往下进行递归的，比如n = 10000时，我们要从10000一直递归到1才返回结果，如果n太大的时候，栈的空间可能不够用。

上述递归方案可以修改成如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int f(int n) {
    if(n <= 2)
        return n;
    int f1 = 1;
    int f2 = 2;
    int sum = 0;

    for (int i = 3; i <= n; i++) 
    {
        sum = f1 + f2;
        f1 = f2;
        f2 = sum;
    }
    return sum;
}

原文作者：itibanst

原文链接：https://st19950627.github.io/2020/03/16/递归学习/

发表日期：March 16th 2020, 8:41:33 pm

更新日期：April 4th 2020, 5:16:14 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 递归
    1. 1.1. 递归的三大要素
      1. 1.1.1. 第一：明确你这个函数想要干什么
      2. 1.1.2. 第二：寻找递归结束条件
      3. 1.1.3. 第三：找出函数的等价关系式
    2. 1.2. 递归的优化方法
      1. 1.2.1. 考虑是否重复计算
      2. 1.2.2. 考虑是否可以自底向上
Total : 39
2023
2022
2021
2020
2019
Apollo Docker Dynamic Datasource ELK 日志系统 Gradle hexo K8S Linux List Set Map SLF4J 日志 JDK8 Restful adobe 插件 Token Session Cookie SpringBoot LIVER 定时任务 leetcode Electron JAVA 算法 回溯法 资产托管 托管 测试 Redis Api 递归 设计模式 编程规范 推荐系统 前端 React vue