递归

发表于 | Edited on

递归

递归原理

递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用

每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到子问题无需进一步递归就可以解决的地步。

为了确保递归函数不会导致无限循环，它应具有以下属性：

  1. 一个简单的基本案例（base case）–能够不使用递归来产生答案的终止方案。
  2. 一组规则，也称作递推关系（recurrentce relation），可将所有其他情况拆分到基本案例。

两两交换链表中的节点

递归写法要观察本级递归的解决过程，形成抽象模型，因为递归本质就是不断重复相同的事情。而不是思考完整的调用栈，一级又一级，无从下手。我们应该关注一级调用小单元的情况，也就是单f(x)。

关心三点：

  1. 返回值
  2. 调用单元做了什么
  3. 终止条件

本题中：

  1. 返回值：交换完成的子链表
  2. 调用单元：设需要完成的两个点为head和next，head连接后面交换完成的子链表，next连接head，完成交换
  3. 终止条件：head为空指针或者next未空指针，也就是当前无节点或者只有一个节点，无法进行交换

递推关系

在实现递归函数之前，两件重要的事情要弄清楚：

  • 递推关系：一个问题的结果与其子问题的结果之间的关系。
  • 基本情况：不需要进一步的递归调用就可以计算答案的情况。有时，基本案例也被称为bottom cases，因为它们往往是问题被减少到最小规模的情况，也就是如果我们认为将问题划分为子问题是一种自上而下的方式的最下层。

杨辉三角

二次项展开式

反转链表

  • 递归

  • 迭代
    遍历列表时，将当前节点的next指针改为指向前一个元素。由于节点没有引用上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while(curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

递归中的重复问题

记忆化

记忆化是一种优化技术，主要用于加快计算机程序的速度，方法是存储昂贵的函数调用的结果，并在相同的输入再次出现时返回缓存的结果

斐波那契数

耗时的原因是重复计算，可以造一个备忘录，每次算出某个字问题的答案后别急着返回，先记到备忘录里再返回；每次遇到一个子问题先去备忘录里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要在耗时计算了。

爬楼梯

暴力

把所有的可能爬的阶数进行组合，也就是1和2.而在每一步中会继续调用函数，并返回函数的和。

记忆化递归

动态规划

分解为包含最优子结构的子问题，即它对的最优解可以从其子问题的最优解来有效地构建

递归–时间复杂度

给出一个递归算法，其时间复杂度通常是递归调用的数量和计算时间复杂度的乘积

总结

合并两个有序链表

两个链表头部较小的一个域剩下的元素merge操作结果合并。

第K个语法符号

0%