序言

递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

简单来讲，递归就是函数反复调用自身的过程。
你肯定听过这个故事：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”
上面的故事即是递归思想的体现。

如何理解递归？

最开始解决递归问题的时候，人们总是会去纠结这一层函数做了什么，它调用自身后的下一层函数又做了什么。。。然后就会觉得实现一个递归解法十分复杂，根本就无从下手。
相信很多初学者和我一样，也踩过这个坑。
既然递归是一个反复调用自身的过程，这就说明它每一级的功能都是一样的，因此我们只需要关注一级递归的解决过程即可。

如上图所示，因为递归是重复的做一件事的过程，所以我们只需要关注一个func（而不是所有）。

在一个func中，需要关心以下三点：

整个递归的终止条件（结束）。
一级递归需要做什么（目的）？
下级递归处理完成后的返回结果（返回值是什么？）

因此，递归的使用可以分为以下 3 个步骤：

① 确定递归的终止条件：递归应该在什么时候结束呢？
② 确定返回值：下级递归处理完成后的返回值，其应该给本级递归传递什么信息呢？
③ 本级递归的目的：在这一级递归中，应该完成什么任务呢？

应用场景：刷题

理解上面 3 步后，就可以通过递归思想来刷算法题了。

但这么说好像很空，所以我们以题目为例，看看怎么套这个模版，相信通过题目，读者可以理解这个模版，之后再解这种套路递归题都能直接秒了。

算法题：删除排序链表中的重复元素

来看这道简单的 Leetcode 题目： Leetcode 83. 删除排序链表中的重复元素
题目很简单，解法也多样，但这里我们通过递归思想解决：

① 确定递归的终止条件：递归应该在什么时候结束呢？当然是链表已无节点或者只剩一个节点时结束递归。
② 确定返回值：下级递归处理完成后的返回值应该给本级递归传递什么信息呢？这一步需要结合第 3 步（和第1 步）来看，第 3 步的目的是删除重复元素，那么这里返回的肯定是处理（删除重复元素）后的链表（第 1 步也做过这个处理）。
③ 本级递归的目的：在这一级递归中，应该完成什么任务呢？题目需要我们删除链表的重复元素，这便是本级递归该做的事情。这一步又需要结合第 2 步来看，其肯定要在经过处理（删除重复元素）后的链表的基础上接着判断。具体逻辑见代码注释。

public ListNode deleteDuplicates(ListNode head) {
    // 1. 终止条件：链表已无节点或者只剩一个节点了，没得删除了，返回该节点
    if (head == null || head.next == null) {
        return head;
    }
    // 2. 下级递归处理完成后的返回结果（返回值）
    head.next = deleteDuplicates(head.next);

    /**
     * 3. 本级递归目的：删除重复节点
     * 当前节点值和下一节点值相等则返回下一节点，否则返回当前节点
     */
    if (head.val == head.next.val) {
        return head.next;
    } else {
        return head;
    }
    // 第 3 步简写
    // return head.val == head.next.val ? head.next : head;
}

注意哦：对第二步的返回值而言，其得到的是经过处理（删除了重复元素）后的部分链表，其值其实有两个：

倒数第二次递归返回接受到的值是终止条件（倒数第一次递归）设置的值
倒数第三次递归返回接受到的值是倒数第二次删除重复节点时得到的值
依次递推。。。

总结

对递归的 3 个步骤而言，其实是环环相扣的：

第一步的终止条件（亦可理解为优化后的数据）给第二步提供了返回值
第二步的返回值给第三步提供了处理好的数据让其继续优化
第三步优化后的数据又作为返回值传递给上级递归的第二步，依次类推。

参考资料

文章信息

时间	说明
2018-12-30	初稿