文章目录前言递归和数学归纳法递归三步走递归的注意点避免栈溢出避免重复运算题目斐波那契数反转链表

前言 递归（Recursion）：指的是一种通过重复将原问题分解为同类的子问题而解决的方法。在绝大数编程语言中，可以通过在函数中再次调用函数自身的方式来实现递归。 举个简单的例子来了解一下递归算法。比如阶乘的计算方法在数学上的定义为：

def fact(n):

if n == 0:

return 1

return n * fact(n - 1)

以 n=6为例，上述代码中阶乘函数的计算过程如下：

fact(6)

= 6 * fact(5)

= 6 * (5 * fact(4))

= 6 * (5 * (4 * fact(3)))

= 6 * (5 * (4 * (3 * fact(2))))

= 6 * (5 * (4 * (3 * (2 * fact(1)))))

= 6 * (5 * (4 * (3 * (2 * (1 * fact(0))))))

= 6 * (5 * (4 * (3 * (2 * (1 * 1)))))

= 6 * (5 * (4 * (3 * (2 * 1))))

= 6 * (5 * (4 * (3 * 2)))

= 6 * (5 * (4 * 6))

= 6 * (5 * 24)

= 6 * 120

= 720

根据上面的描述，我们可以把阶乘函数的递归计算过程分为两个部分：

先逐层向下调用自身，直到达到结束条件（即n==0。然后再向上逐层返回结果，直到返回原问题的解（即返回 fact(6)==720 这两个部分也可以叫做「递推过程」和「回归过程」，如下面两幅图所示： 如上面所说，我们可以把「递归」分为两个部分：「递推过程」和「回归过程」。 • 递推过程：指的是将原问题一层一层地分解为与原问题形式相同、规模更小的子问题，直到达到结束条件时停止，此时返回最底层子问题的解。 • 回归过程：指的是从最底层子问题的解开始，逆向逐一回归，最终达到递推开始时的原问题，返回原问题的解。 「递推过程」和「回归过程」是递归算法的精髓。从这个角度来理解递归，递归的基本思想就是： 把规模大的问题不断分解为子问题来解决。 同时，因为解决原问题和不同规模的小问题往往使用的是相同的方法，所以就产生了函数调用函数自身的情况，这也是递归的定义所在。

递归和数学归纳法 递归的数学模型其实就是「数学归纳法」。这里简单复习一下数学归纳法的证明步骤： 1.证明当n=b （b 为基本情况，通常为 0 或者 1）时，命题成立。 2.证明n>b 时,假设n=k时命题成立，那么可以推导出n=k+1时命题成立；这一步不是直接证明的，而是先假设n=k时命题成立，利用这个条件，可以推论出n=k+1时命题成立。 通过以上两步证明，就可以说：当n>=b 时，命题都成立。 我们可以从「数学归纳法」的角度来解释递归： 1.递归终止条件：数学归纳法第一步中的n=b，可以直接得出结果。 2.递推过程：数学归纳法第二步中的假设部分（假设n=k时命题成立），也就是假设我们当前已经知道了n=k时的计算结果。 3.回归过程：数学归纳法第二步中的推论部分,根据n=k推论出n=k+1）也就是根据下一层的结果，计算出上一层的结果。

递归三步走 递归的基本思想就是： 把规模大的问题不断分解为子问题来解决。 那么，在写递归的时候，我们可以按照这个思想来书写递归，具体步骤如下： 1. 写出递推公式：找到将原问题分解为子问题的规律，并且根据规律写出递推公式。 2. 明确终止条件：推敲出递归的终止条件，以及递归终止时的处理方法。 3. 将递推公式和终止条件翻译成代码： 1. 定义递归函数（明确函数意义、传入参数、返回结果等）。 2. 书写递归主体（提取重复的逻辑，缩小问题规模）。 3. 明确递归终止条件（给出递归终止条件，以及递归终止时的处理方法）。

递归的注意点避免栈溢出 在程序执行中，递归是利用堆栈来实现的。每一次递推都需要一个栈空间来保存调用记录，每当进入一次函数调用，栈空间就会加一层栈帧。每一次回归，栈空间就会减一层栈帧。由于系统中的栈空间大小不是无限的，所以，如果递归调用的次数过多，会导致栈空间溢出。 为了避免栈溢出，我们可以在代码中限制递归调用的最大深度来解决问题。当递归调用超过一定深度时（比如 100）之后，不再进行递归，而是直接返回报错。 当然这种做法并不能完全避免栈溢出，也无法完全解决问题，因为系统允许的最大递归深度跟当前剩余的占空间有关，事先无法计算。 如果使用递归算法实在无法解决问题，我们可以考虑将递归算法变为非递归算法（即递推算法）来解决栈溢出的问题。

避免重复运算 在使用递归算法时，还可能会出现重复运算的问题。 比如斐波那契数列的定义是

从图中可以看出：想要计算 f(5)，需要先计算 f(3) 和 f(4)，而在计算 f(4) 时还需要计算 f(3)，这样f(3) 就进行了多次计算。同理 f(0)、f(1)、f(2) 都进行了多次计算，就导致了重复计算问题。 为了避免重复计算，我们可以使用一个缓存（哈希表、集合或数组）来保存已经求解过的 f(k) 的结果，这也是动态规划算法中的做法。当递归调用用到f(k) 时，先查看一下之前是否已经计算过结果，如果已经计算过，则直接从缓存中取值返回，而不用再递推下去，这样就避免了重复计算问题。

题目斐波那契数 递推三步走策略，写出对应的递归代码。 1写出递推公式：f(n)=f(n-1)+f(n-2) 2 明确终止条件：f(0)=0,f(1)=1 3 翻译为递归代码： 1. 定义递归函数：fib(self, n) 表示输入参数为问题的规模 n，返回结果为第 n 个斐波那契数。 2. 书写递归主体：return self.fib(n - 1) + self.fib(n - 2)。 明确递归终止条件： 1. if n == 0: return 0 2. if n == 1: return 1

class Solution:

def fib(self, n: int) -> int:

if n == 0:

return 0

if n == 1:

return 1

return self.fib(n - 1) + self.fib(n - 2)

反转链表 描述：给定一个单链表的头节点 head。 要求：将该单链表进行反转。可以迭代或递归地反转链表。 示例 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 解释： 翻转前 1->2->3->4->5->NULL 反转后 5->4->3->2->1->NULL

具体做法如下：

首先定义递归函数含义为：将链表反转，并返回反转后的头节点。然后从 head.next 的位置开始调用递归函数，即将 head.next 为头节点的链表进行反转，并返回该链表的头节点。递归到链表的最后一个节点，将其作为最终的头节点，即为 new_head。在每次递归函数返回的过程中，改变 head 和 head.next 的指向关系。也就是将 head.next 的next指针先指向当前节点 head，即 head.next.next = head 。然后让当前节点 head 的 next 指针指向 None，从而实现从链表尾部开始的局部反转。当递归从末尾开始顺着递归栈的退出，从而将整个链表进行反转。最后返回反转后的链表头节点 new_head。

1.class Solution:

2. def reverseList(self, head: ListNode) -> ListNode:

3. if head == None or head.next == None:

4. return head

5. new_head = self.reverseList(head.next)

6. head.next.next = head

7. head.next = None

8. return new_head