一、算法描述

递归算法是一种直接或者间接调用自身函数或者方法的算法。说简单了就是程序自身的调用。

二、算法实质

递归算法就是将原问题不断分解为规模缩小的子问题，然后递归调用方法来表示 问题的解。（用同一个方法去解决规模不同的问题）

三、算法思想

递归算法，顾名思义就是有两个大的阶段：递和归，即就是有去（递去）有回（归来）。

  • 递去：将递归问题分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决
  • 归来：当你将问题不断缩小规模递去的时候，必须有一个明确的结束递去的临界点（递归出口），一旦达到这个临界点即就从该点原路返回到原点，最终问题得到解决。

过程图解：

递归图解

四、递归算法使用条件

  • 明确递归的终止条件
  • 提取重复的逻辑，缩小问题的规模不断递去
  • 给出递归终止时的处理办法

五、案例

  • 阶乘

    1
    2
    3
    4
    5
    6
    public static int recursion(int number) {
            if (number == 1) {
                return 1;
            }
            return number * recursion(number - 1);
    }

  • 力扣（合并两个有序链表）

    题目 链接: https://leetcode.cn/problems/merge-two-sorted-lists/description/

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    题目

    算法思路

    采用递归算法，若l1 || l2 开始即为空链表，不需要操作返回非空链表，否则判断那个链表的头节点对应的值更小，然后递归，决定下一个添加到结果里的节点，如果后续递归中两个链表有一个为空递归结束。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           if (l1 == null) {
               return l2;
           } else if (l2 == null) {
               return l1;
           // 排除非空集合
           } else if (l1.val <= l2.val) {
               // 寻找最小头节点 每次递归节点 寻找插入的位置 每次更新链表 直到有一个值为空 就跳出递归
               l1.next = mergeTwoLists(l1.next, l2);
               return l1;
           } else {
               l2.next = mergeTwoLists(l2.next, l1);
               return l2;
           }
     }

    复杂度分析

    • 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，O(n+m)。
    • 空间复杂度：O(n+m)，其中 n和 m分别为两个链表的长度。递归调mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m次，因此空间复杂度为 O(n+m)。

六、个人对于递归的理解(己见)

每次递归都会缩小范围，例如阶乘递归每次程序调用本身时参数就减一，从大规模逐渐减少到最后小规模的结束条件，输入5，每次递归减一 最终返回就是5 4 3 2 1 = 120（最后结束时候返回的结果），缩小到最小范围时候开始计算返回结果，也就是递归终止条件。