递归的数学基础是数学归纳法，我们高中都学过数学归纳法，首先先复习一下数学归纳法的知识，然后再一步一步过渡到如何理解和编写递归函数。

数学归纳法的证明过程

先来回顾一下高中学过的由两个命题组成的一系列三段论的数学归纳法解题的步骤：

验证当 $n=1$ 时，显然成立。

假设当 $n=k$ 时，依然成立。

证明当 $n=k+1$ 时，证明等式依然是成立的。

根据上面的证明过程，具体举个例子分析下。

来一个例子具体说明一下。

假设数列 $a_n=2n-1$ ，用数学归纳法证明 $S_n=n^2$

按照上面给出的数学归纳法的三个步骤，一步一步求解就行了。

很显然，当 $n=1$ 时， $a_1=1$ ， $S_1=1$ ，显然成立。

假设当 $n=k$ 时成立，即： $S_k=k^2$ 。

证明当 $n=k+1$ 时成立即可。由 $S_{k+1}=S_k+a_{k+1}$ 可知得 $S_{k+1}=k^2+2(k+1)-1=k^2+2k+1=(k+1)^2$ 。所以原式得证。

最开始，这个证明我是不理解也不能接受的；但是这么做确实得分，所以然后我就慢慢接受了；由于总是用这么一套流程，做题久了我也不去质疑它的正确性了，就开始理解它了。其实和学很多东西都是一样，都是不理解，但是用的多了也就慢慢理解了。

当初为什么不理解呢？

首先第一步是没有任何问题的。但是第二步假设如何如何，而且这个假设就是答案，这有点未卜先知，在现实中几乎不存在这样的事，所以很难接受和理解，而第三步是在第二步假设正确的基础上推导结论是正确的。

我们常见的思考方式是通过不断推理论证或者实践，最后得出结论，这是经典演绎的证明方法的顺序过程。而数学归纳法是在已知结论的前提下证明结论是正确的过程，和我们平时的思考方式是相反的。导致很难接受和理解数学归纳法。然而这并不影响数学归纳法的威力。

如果你实在理解不了，那就接受吧。尤其是第二步的假设，不要问为什么就这样假设，而是在这样假设是正确的基础上论述假设是对的。如果我们能别过来这个劲，数学归纳法的核心就是在假设 $f(n-1)$ 成立的基础上，找出 $f(n)$ 和 $f(n-1)$ 之间的关系，证明 $f(n)$ 成立的过程。

上面的例子中的 $S_{k+1}=S_k+a_{k+1}$ 就是连接 $f(n)$ 和 $f(n-1)$ 之间的关系，是其核心。

对于新手的话，整个数学归纳法的难点就在于，别去理会第二步的假设或者结论为什么是正确的，而应该假设它是正确的。

数学归纳法和递归之间的关系

说了这么多数学归纳法，它和递归有什么联系呢？划重点：

数学归纳法是递归函数的数学基础；

数学归纳法的证明过程就是编写递归函数的过程；

为什么这么说呢？来看下递归函数的定义：

递归函数是直接或间接的调用自己的一个函数。

有没有思考过，递归函数为什么要调用自己呢？每次调用自己时，函数的哪些内容发生了变化呢？

很显然，每次发生递归调用时，传递的参数规模随着递归深度的增加越来越小，直到数据规模小到不需要递归本体处理时。

从上面分析的过程中可以看到递归函数包括两个部分，一部分是继续发生递归调用，称为递归条件(recursion case)；另外一部分是递归函数不再继续调用自己，避免发生无限循环调用，称为基线条件(base case)。

用一段伪代码标识一下：

def recursion(bigSize):
    # 1. 基线条件，递归函数退出条件
    if bigSize可以直接处理:
        处理
        return 
    
    # 2. 缩小函数参数的规模，继续递归下去
    smallAns = recursion(smallSize)
    # 经过递归函数后，smallAns已经变成期望的答案了。
    
    # 3. 在已知smallAns为期望的答案的前提下，构建整体的答案。
    bigAns = merge(smallAns, other)
    return bigAns

仔细看上面的代码，还是将整个代码分成三个部分，而且这三个部分是和数学归纳法证明的三个步骤是对应的。

在数学归纳法中，当 $n=1$ 时是不需要经过 $f(n)$ 处理的；在递归中，也存在当数据规模小到一定程度时不需要经过递归函数作用的base case，它们是相互对应的。

数学归纳法的第二步是假设 $f(n)$ 成立，对应递归函数中的递归本体，也就是上述代码中的smallAns = recursion(smallSize)，当这句执行完成后，smallAns就是期望的答案。至于这个期望的答案是什么样的，那就和递归函数的功能相关。

那么为什么经过递归函数后，smallAns就是期望的答案呢？如果我们进入到递归函数内部，不一会脑子就混乱了。所以我们不要进入到递归函数内部去，只需要假设递归函数可以返回期望的结果就行了。

数学归纳法的第三步是在 $f(n)$ 正确的基础上，找到 $f(n+1)$ 和 $f(n)$ 之间的关系，推到出 $f(n+1)$ 正确。而递归的第三步是在得到小规模数据结构的基础上，构建总体期望的输出，对应上面代码的merge。

理解递归的核心在于放弃和假设，放弃探究递归是如何将更小规模数据变成期望的输出，而是再次基础上，找到和整体之间的差异，构建整体期望的输出。

通过一个表总结一下递归和数学归纳法之间的对应关系。

数学归纳法	递归
验证特例，例如 $n=1$ ，显然成立	递归退出条件，也就是`base case`
假设 $n=k$ 时，结论成立	假设递归能够将小规模数据变成期望的输出
验证当 $n=k+1$ 时等式成立，核心是找出 $f(n)$ 和 $f(n+1)$ 之间的关系	找到经过递归作用后的更小规模数据和期望答案之间的关系

在编写递归函数时，base case一般是很简单的，如果不陷入到递归函数内部探索递归函数时如何运行的，而是根据自定义的递归函数功能去推理输出，那么这一步也是比较容易的，最后是找到已经得到期望结构的小规模数据和整体之间的关系，构建整体的输出，这一步不像是数学难以寻找关系，在编程的世界里都是比较容易寻找的，所以第三步也没有那么难。

既然这三步都不是很难，那么如何编写递归函数呢？

如何编写递归函数

证明数学归纳法的步骤就是编写递归函数的过程，接下来根据数学归纳法的三个步骤，说下编写递归函数的三个步骤。

对应数学归纳法中的第一条，验证特例，在编写递归中，应该明确递归函数的退出条件。如果递归函数没有正确的退出条件，结局就是爆栈。

对应数学归纳法中的第二条，假设结论是正确的。在编写递归函数时，在递归本体中以小规模数据作为参数的递归函数执行完后能够得到我们想要的答案，而具体是什么答案则是依赖递归函数的功能，所以在编写递归函数时需要明确递归函数的功能，以及入口参数、返回值都表示什么意思。

对应数学归纳法中的第三条，在假设 $f(n-1)$ 正确的基础上，找到 $f(n-1)$ 与 $f(n)$ 之间的关系，证明 $f(n)$ 成立。在编写递归函数中，假设编写的递归函数已经得到了小规模数据的答案或者结构，此时需要找到与整体期望的答案之间的差异，从而构建总体的期望输出。

针对缩小数据规模要说两句，其实每次缩小数据规模的目的就是为了向base case上靠近从而结束递归调用。那么每次向base case上靠的幅度越大，则递归调用的次数就越少。如果将规模为 $n$ 的数据拆分成 $k$ 和 $n-k$ 两个部分，如果每次向base case上靠近 $k$ 步，那么完成整个数据则需要 $\frac{n}{k}$ 次递归调用。

除此之外，在编写递归函数时只要我们明确递归函数的功能，不去追求在递归函数是如何得到小规模数据的答案或者结构时，只需要考虑两层之间的关系，所以递归代码简单易懂，代码实现起来简洁明了。只要我们做到了这一点，递归函数的编写就不难。

递归的核心-层与层之间的关系

阶乘问题

编写int factorial(int n)函数，求解 $n$ 的阶乘

按照编写递归的三个步骤，求解这个问题。

1. 定义递归函数int factorial(int n)的功能，明确参数以及返回值的含义。

这个函数的功能很简单，当参数为 $n$ 时，就计算 $n$ 的阶乘；当参数为 $n-1$ 时，就计算 $n-1$ 的阶乘，并返回计算的结果。

2. 确定递归的退出条件

当参数 $n$ 不可再拆分的时候，此时就是递归函数的退出条件。所以当 $n=0$ 的时候，就是递归退出的条件，此时应该返回 $0!$ ，数值为1。写成代码。

int factorial(int n){
    if(n == 0)
        return 1;
}

3. 缩小数据规模，并梳理两层数据之间的关系。

整个函数就一个参数 $n$ ，数据规模就是 $n$ 。应该对 $n$ 进行拆分，为了向递归退出条件 $n=0$ 靠近。

那么具体怎么拆分呢？这里又有很多方法了。根据数学知识有， $n!=n\times(n-1)!$ ，那么问题来了，怎么用代码计算 $(n-1)!$ 呢？按照定义的递归函数功能，只需要调用factorial(n-1)就完成了 $(n-1)!$ 的计算。

这里千万不要陷进去想为什么函数factorial(n-1)就可以计算 $(n-1)!$ 。我们只需要知道调用factorial(n-1)就完成 $(n-1)!$ 的计算就可以了，我们应该关注在已知 $(n-1)!$ 的基础上，如何求解 $n!$ 。而 $(n-1)!$ 只需要依靠定义的函数功能即可实现。 $n!$ 与 $(n-1)!$ 之间相差一个 $n$ ，这个 $n$ 就是两层之间的桥梁。

所以把上述过程写成完整的代码

int factorial(int n){
    if(n == 0)
        return 1;
    //这个n就是层与层之间的桥梁。
    return n * factorial(n-1);
}

4. 思考

上面的数据划分方式，每调用一次递归函数，就向着递归退出条件靠近一步。如果是计算 $n$ 的阶乘，就需要调用 $n$ 次递归函数。

如果每次向着递归退出条件靠近2步，应该将 $n$ 怎么进行划分，代码应该是怎么样的。根据数学，还可以这样计算 $n!=n\times(n-1)\times(n-2)!$ 。

问题来了，如何使用代码计算 $(n-2)!$ 呢？如果你没有忘记递归函数的功能的话，这是不是很简单就写出来了factorial(n-2)。

再考虑一下递归的退出条件是不是要改变呢？如果每次递归规模都缩小 $2$ 的话，也就是说每次以 $2$ 步的速度向着递归退出条件靠近。在 $2$ 以内的数都不会参与到递归中，所以要将 $2$ 以内的数都作为递归退出条件。

将上述过程写成代码

int factorial(int n){
    if(n == 0 || n == 1)
        return 1;
    return n * (n - 1) * factorial(n-2);
}

上面的数据划分方式，每调用一次递归函数，就向着递归退出条件靠近2步。如果是计算 $n$ 的阶乘，就需要有 $\frac{n}{2}$ 次递归调用。

如果每次以 $3$ 步的速度向着递归退出条件靠近的话，将 $n!$ 采用如下的方式计算

$n!=n*(n-1)*(n-2)*(n-3)!$

此时递归退出条件和递归本体又是什么样子的呢？仿照上面的分析，递归的退出条件要加上 $n=2$ 这步。每次以 $3$ 步的速度向递归退出条件靠近，也就是说计算 $n!$ 需要 $\frac{n}{3}$ 次递归调用。

所以写成代码

int factorial(int n){
    if(n == 0 || n == 1)
        return 1;
    if(n == 2)
        return 2;
    return n * (n-1) * (n-2) * factorial(n-3);
}

再极端考虑一下，如果在函数内部没有递归调用，也就是每次向递归退出条件靠近 $n$ 步，将 $n!$ 使用下面的公式计算。

$n!=n\times(n-1)\times(n-2)\times...\times(n-(n-1)) = n\times(n-1)\times(n-2)\times...\times1$

此时我们的递归退出条件是什么？要根据 $n$ 的不同，将结果都枚举出来，这样就没有递归调用，全是递归退出条件了。没有递归调用，那就是迭代的写法。

int factorial(int n){
    if(n  == 0 || n == 1)
        return 1;
    if(n == 2)
        return 2;
    if(n == 3)
        return 6;
    //....
}

上面的代码用if是实现不了的，很显然是循环实现。

int factorial(int n){
    int res = 1;
    for(int i = 1; i <= n; i++)
        res *= i;
    return res;
}

5. 小结

虽然这个例子很简单，却是第一个按照套路一步一步编写出来的递归代码，并且通过改变划分数据的方式，逐步减少递归函数调用的次数，当不再需要递归调用时，就将递归代码转换成迭代代码。所以可以通过更改划分数据的方式，可以找到迭代解题的规律。同时也看到不同划分数据的方式，递归函数的本体和退出条件也都是不同的。

链表翻转

这题来源于leetcode上面的206号问题，首先以递归作为切入，通过更改划分数据的方式，找到规律，然后写出迭代的解法。依旧按照前面给出的递归的步骤，一步一步编写递归函数。

1. 定义递归函数ListNode* reverseList(ListNode* head) 的功能，明确参数以及返回值的意义

定义递归函数的功能总是很简单的，基本上题目让我们干什么，我们就把递归函数的功能定义成什么。这个函数的功能定义也很简单，就是翻转以head为头节点的链表，并且返回翻转后链表的头节点。画图表达一下，原链表假设如下。

image

经过翻转，链表应该变成下面这个样子，并且返回retHead作为新链表的头结点。

image

2. 确定递归函数的退出条件

想一下，当链表长度 $n$ 为什么时不需要使用递归进行翻转呢？很显然，当链表长度为 $1$ 或者 $0$ 时，不需要翻转，也就是递归退出条件。写成代码。

ListNode* reverseList(ListNode* head){
    if(head == nullptr || head->next == nullptr)
        return head;
    //递归本体
}

3. 划分数据为多层，并梳理层与层之间的关系

想一下，这里数据规模是什么？只有链表的长度可以更改，所以数据规模应该是链表的长度 $n$ 。所以问题是，如何分割链表使得数据规模向base case上靠近？

这里可以将长度 $n$ 的链表拆分成长度分别为 $n-1$ 和 $1$ 两个链表，假设 $n-1$ 部分的头结点为newHead，将其作为递归的参数，根据我们自定义的递归函数功能，就可以完成长度为 $n-1$ 的链表部分就完成了翻转。

image

当reverseList(newHead)执行完后，以newHead为头节点的链表就已经完成了翻转，并且返回了新链表的头结点retHead。这里就是要放弃思考递归函数是如何做到的，千万不要在这里陷进去。而是直接默认它是可以完成这些功能的，因为我们定义的递归函数功能就是这样。

当reverseList(newHead)执行完后，整个链表变成如下这个样子。

image

对比和我们期望的链表的结构之间的差异，只需要更改newHead节点和head节点的next指针就可以了。

image

整体代码如下：

ListNode* reverseList(ListNode* head) {
    //当不存在节点或者只有一个节点的时候，就是递归退出条件
    if(head == nullptr || head->next == nullptr)
        return head;
    //将链表分为两个部分
    ListNode* newHead = head->next;
    head->next = nullptr;
    //n-1部分送去递归，完成翻转
    ListNode* retHead = reverseList(newHead);
    //改变指针指向，一次只能翻转一个节点。
    newHead->next = head;
    head->next = nullptr;
    return retHead;
}

4. 思考

思考上面递归的过程，每调用一次递归函数只能完成一个节点的翻转，如果链表的长度为 $n$ ，则需要执行 $n-1$ 次递归函数。如果要减少递归调用的次数，需要更改划分数据的方式，这次我们将长度为 $n$ 的链表划分为长度分别为 $n-2$ 和 $2$ 两个部分。此时每调用一次递归函数的时候，就完成 $2$ 个节点的翻转，所以当链表长度为 $n$ 的时候，需要调用 $\frac{n}{2}$ 次递归函数。

这样划分数据后，递归的退出条件就是当链表长度小于等于 $2$ 时。base case代码如下：

ListNode* reverseList(ListNode* head) {
    //链表节点小于等于1的时候，直接退出
    if(head == nullptr || head->next == nullptr)
        return head;
    //链表长度为2时，手工翻转
    if(head->next->next == nullptr){
        ListNode* retHead = head->next;
        head->next = nullptr;
        retHead->next = head;
        return retHead;
    }
    //递归本体
}

当链表长度大于 $2$ 的时候，我们首先将链表分割成长度为 $2$ 和 $n-2$ 两部分翻转，其中假设长度为 $n-2$ 部分的头结点是newHead。并且将newHead作为递归参数。用图表示一下。

image

当reverseList(newHead)函数执行完成后，就完成了newHead部分的翻转，并且返回retHead作为头结点。这个时候，你就不要想为什么完成翻转了啊，因为假设的递归函数功能就是这个。

image

剩下的就是对比newHead反转后的链表和期望链表之间的差异，将其找出来。

image

为了能够转换成期望的链表结构，只需要分别改变head、head->next和newHead的next指针指向就可以了。写成代码：

ListNode* reverseList(ListNode* head){
    //链表节点小于等于1的时候，直接退出
    if(head == nullptr || head->next == nullptr)
        return head;
    //链表长度为2时，手工翻转
    if(head->next->next == nullptr){
        ListNode* retHead = head->next;
        head->next = nullptr;
        retHead->next = head;
        return retHead;
    }
    
    //对链表进行分割
    ListNode* newHead = head->next->next;
    head->next->next = nullptr;
    //将小规模进行翻转
    ListNode* retHead = reverseList(newHead);
    //按照图中步骤，更改指针指向，一次可以翻转两个节点
    newHead->next = head->next;
    head->next->next = head;
    head->next = nullptr;
    return retHead;
}

上面的数据分割方式，如果链表的长度为 $n$ ，则需要调用 $\frac{n}{2}$ 次递归调用。如果要减少递归函数调用的次数，可以将长度为 $n$ 的链表拆分成 $n-3$ 和 $3$ 两部分，但是这样做，递归的退出条件就需要考虑 $n=0$ 、 $n=1$ 、 $n=2$ 、 $n=3$ 这几种情况，但是翻转长度为 $n$ 的链表只需要调用 $\frac{n}{3}$ 次递归函数。虽然编写起来就有些麻烦，但是我们还是将其编写一下，试图发现迭代写法的规律。

ListNode* reverseList(ListNode* head){
    //链表节点小于等于1的时候，直接退出
    if(head == nullptr || head->next == nullptr)
        return head;
    //链表长度为2时，手工翻转
    if(head->next->next == nullptr){
        ListNode* retHead = head->next;
        head->next = nullptr;
        retHead->next = head;
        return retHead;
    }
    //3个节点
    if(head->next->next->next == nullptr){
        ListNode* retHead = head->next->next;
        retHead->next = head->next;
        head->next->next = head;
        head->next = nullptr;
        return retHead;
    }
    //对链表进行分割
    ListNode* newHead = head->next->next->next;
    head->next->next->next = nullptr;
    //将小规模进行翻转
    ListNode* retHead = reverseList(newHead);
    //按照图中步骤，更改指针指向，一次可以翻转3个节点
    //4.next->3
    newHead->next = head->next->next;
    //3.next->2
    head->next->next->next = head->next;
    //2.next = 1
    head->next->next = head;
    //1.next = nullptr
    head->next = nullptr;
    return retHead;
}

从代码注释中，似乎可以发现些规律，链表翻转的实质就是让当前节点cur的next指针指向前一个节点pre，但是如果直接修改cur的next指针，那么cur的next指针指向的节点就不能访问到了，所以在修改next指针前，需要保存cur的next指针指向的节点，假设为nextNode。

对应的代码如下：

ListNode* nextNode = cur->next;
cur->next = pre;

这样我们就完成了修改当前节点的next指向前一个节点，也就是说当前节点做完了，需要向后处理，需要同时向后移动pre和cur一位即可。写成代码：

//1. 保存下一个节点
ListNode* nextNode = cur->next;
//2. 修改指针
cur->next = pre;

//3. 向后移动
pre = cur;
cur = nextNode;

接下来分析下，pre和cur应该初始化成什么？

由于cur是当前的节点，翻转时从第一节点开始就可以，所以初始化成head。

而pre表示的是翻转后cur的next指针指向的节点。由于头节点head翻转后的next指针指向nullptr，且cur初始化时为head，所以pre初始化应该是nullptr。

循环什么时候结束呢？当翻转所有链表节点后，cur为nullptr，而pre为cur的前一个节点，所以当cur为空节点时，pre就是原链表最后一个节点，也是翻转后的头节点，直接返回即可。

将上述分析的过程写成迭代代码

ListNode* reverseList(ListNode* head) {
    if(head == nullptr || head->next == nullptr)
        return head;
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while(cur != nullptr){
        //保存下一个节点
        ListNode* nextNode = cur->next;
        //改变指向
        cur->next = pre;
        //同时前进一位
        pre = cur;
        cur = nextNode;
    }
    return pre;
}

这就是翻转链表的迭代代码，如果还没有清楚这个过程以及初始化三个变量的初值，建议停止手中的键盘，拿起笔，多在纸上画画这个过程，就慢慢全明白了。

当我们又会了迭代的代码的时候，重新思考一下递归的划分数据的思路，受到归并排序的启发，可以把长度为 $n$ 的链表划分为长度分别为 $n/2$ 和 $n/2$ 两个部分，这样的话，效率是不是会更高一些呢？对于递归退出条件仍然是当 $n=0$ 或者 $n=1$ 的时候。所以问题的核心有两点，一是如何定位到链表的中间节点，二是这样划分数据的话，层与层之间的关系是怎么样的？首先解决第一个问题，定位到链表中点就是使用快慢指针了。具体的策略就是快指针每次走两步，慢指针每次都一步。这是一个基本的操作，所以就不画图了，写成代码。

ListNode* fast = head;
ListNode* mid = head;
ListNode* slow = head;
while(fast && fast->next){
    fast = fast->next->next;
    mid = slow;
    slow = slow->next;
}
//将链表断开为两部分，一部分头节点是head, 另外一部分头节点为slow
mid->next = nullptr;

当执行完上述代码后，mid、slow以及fast的指针指向如下图所示。

image

由于使用函数reverseList可以对链表进行翻转，所以可以分别将head和slow分别作为递归函数的参数，当递归执行完成后，得到的链表结构如下。

image

对比与期望的结构之间的差异，只需要更改slow的next指针，让其指向mid即可。

image

将上述过程写成完整的代码。

ListNode* reverseList(ListNode* head) {
    if(!head || !head->next)
        return head;
    //定位到中点
    ListNode* fast = head;
    ListNode* slow = head;
    ListNode* mid = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        mid = slow;
        slow = slow->next;
    }
    mid->next = NULL;
    //翻转两部分
    ListNode* retHead2 = reverseList(head);
    ListNode* retHead = reverseList(slow);
    //连接在一起，一次只能翻转一个节点，就是slow节点
    slow->next = mid;
    return retHead;
}

这样划分数据的方式，在逻辑上非常清楚，但是在效率上并不高，这是为什么呢？

递归的退出条件还是当 $n=1$ 时退出，并且在翻转时，只有一句slow->next = mid是翻转的核心代码，每调用一次递归函数只能翻转一个节点，所以翻转长度为 $n$ 的链表需要调用递归的次数就是 $n-1$ 。但是由于定位在中点过程中比较浪费时间，时间复杂度为 $O(n)$ ，而前面的数据划分时间复杂度为 $O(1)$ ，所以两者的效率差异主要体现在数据划分的方式上。

经过以上的一系列操作，可以说不论使用递归还是迭代的方式，都可以完成链表的翻转。

总结

从上面这两个例题，可以总结出，不同的数据分割形式就会导致不同的base case和递归本体，并且其也会影响递归函数的调用次数。并且可以发现，其实递归函数并不是真正起作用的部分，也就是说只调用递归函数是不能完成节点指针的指向的改变，真正起作用的部分是merge部分，对应在链表翻转问题中是更改节点的next指针部分，例如slow->next=mid。这部分如果翻转的链表节点较多，则需要调用的递归次数就较少。而随之应该更改对应的base case。

一般情况下，虽然base case是比较简单的，但是还是需要认真斟酌的，有时候整个递归的问题就出在了base case上。接下来就说下因为忽略base case而导致的问题。

从数学归纳法到递归

从数学归纳法到递归

数学归纳法的证明过程

数学归纳法和递归之间的关系

如何编写递归函数

递归的核心-层与层之间的关系

阶乘问题

链表翻转

总结