1.啥是递归

函数自己调用自己是递归

def func(x):
    # 自己调用自己
    func(x-1)

在上面的代码中，函数func在自己的函数体中调用了自己，就是递归

2.递归怎么写

递归双枪：分段做事 + 返回值

以def recursion(n)为例：

A. 首先必须明确，递归函数需要返回什么值
B. 再者明确函数recursion(n) 要做什么事——找分段函数！：
寻找有出口的 + 可递推的关于recursion(n)取值的分段函数。注意，必须是有出口的 + 可递推的分段，如图所示：

递归的核心-分段函数

写成代码形式就是一个 if else 语句：

# 出口段
if n meet some situation:
    recursion(n) = 现成值  # 递归出口 ----> 出口一定是现成值
    # 当一个值是现成的，当然是直接拿啊，还递归干啥

# 递归段
else:
    recursion(n) = recursion(n-1)  # 没到出口，递归继续 ----> 可递推才能递归

下面实战

例1：

写一个函数，输入正整数n，求出斐波那契数列第n项的值

思路
def fib(n):

1.明确函数返回值。这里很简单，fib(n)返回斐波那契数列第n项的值
2.分段做事：

关于fib(n)取值的分段函数的结构：

if n == 1 or n == 2:
    fib(n) = 1
else:
    fib(n) = fib(n-1) + fib(n-2)

那么，基于上面的分段函数和返回值，这个求fib(n)函数的递归写法很容易就可以写出来了：

# 1.首先明确fib(n)返回值是斐波那契数列第n项
def fib(n):
    # 2.递归出口是n为1或者2
    if n == 1 or n == 2:
        return 1
    # 如果不是递归出口
    else:
        # 3.借助问题递推式，继续递归缩小问题规模，直到递归出口
        return fib(n-1) + fib(n-2)

利用中间过程持久化来优化递归

在上面斐波那契数列的递归代码中， return fib(n-1) + fib(n-2) 这行进行了2次自我调用： fib(n-1) 一次，fib(n-2) 一次。实际上，在这两次自我调用的过程中，产生了大量的重复计算，这点通过画递归树可以很好理解。如果我们把计算过的值存起来，下次再用的时候就可以直接取了，这是常见的优化思路，即中间过程持久化

这里可以通过共享的字典来记录中间值

result_dict = {
    1: 1,
    2: 1,
}
# 1.首先明确fib(n)返回值是斐波那契数列第n项
def fib(n):
    global result_dict
    # 2.递归出口是n在字典内，可以直接取值，不用通过fib(n-1) + fib(n-2)递归计算了
    if n in result_dict:
        return result_dict[n]
    # 如果不是递归出口，即n不在字典内
    else:
        # 3.借助问题递推式，递归求出fib(n)，并加入字典
        result_dict[n] = fib(n-1) + fib(n-2)
        return result_dict[n]

例2（leetcode687)：

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点

注意：两个节点之间的路径长度由它们之间的边数表示

示例 1:
输入:

输出:
2
因为5-5-5是最长路径，共有2条边，长度为2

思路

一棵树中，这样所谓的最长路径，肯定经过某棵子树的根节点
因此，马上有一个等式：每一条符合要求的路径的长度 = 某一节点的最长左支 + 某一节点的最长右支，但这个等量关系并不是递推式，因为等号左右并非同一形式，因此也不能作为我们目的分段函数的其中一段

怎么办？不方，仔细看其实可以发现，
节点node的最长左支 = 【1 + max(node.left的最长左支, node.left的最长右支)】or 【0】，仅当node.val != node.left.val时取0。这显然是一个有出口的、可递推的分段函数
同理，
节点node的最长右支 = 【1 + max(node.right的最长左支, node.right的最长右支)】or 【0】，仅当node.val != node.right.val时取0。同样是一个有出口的、可递推的分段函数

找到了有出口的、可递推的分段函数，就找到了递归的突破口

于是，定义一个函数，接收一个结点，返回以这个结点为根的左右支中最长一支的长度，即返回max(node的最长左支, node的最长右支)

在返回最长一支的长度之前，肯定计算出了node的最长左支和node的最长右支，这两项加起来，就是经过node的最长路径。不断递归，也就能不断计算出整棵树中的每一个结点为根时的最长路径，取其中最大的即为所求

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.max_val = 0

    def longestUnivaluePath(self, root: TreeNode) -> int:
        self.getLongestOneSide(root)
        return self.max_val

    # 返回结点root左右支最长一支的长度，并同时在函数体中操作self.max_val
    def getLongestOneSide(self, root) -> int:
        if not root:
            return       
        
        # 左支
        left = 0
        if root.left:
            # 如果根结点和左孩子结点的值相同，通过递归更新left
            if root.left.val == root.val:
                left = 1 + self.getLongestOneSide(root.left)
            # 如果根结点和左孩子结点的值不同，不改变left，同时递归获取root.left的左右支的最长支
            else:
                self.getLongestOneSide(root.left)
        
        # 右支
        right = 0
        if root.right:
            if root.right.val == root.val:
                right = 1 + self.getLongestOneSide(root.right)
            else:
                self.getLongestOneSide(root.right)

        # 将root结点的左右支最长和与self.max_val比较，取其大
        self.max_val = max(self.max_val, left+right)
        # 返回root结点最长的一侧
        return max(left, right)

可以看到，在这题中，不断递归的函数getLongestOneSide的返回值并不直接就是需要我们求的最长路径长度，而是返回左右支中最长的一支的长度。需要我们求的最长路径长度，在函数返回之前，就进行了比较和结算。这提示我们，递归不必一定要在返回所求；目标所求也可以在函数体的某一部分进行结算，即“第一枪就击中目标，不必一定得第二枪击中”

例3

给定一个链表和正整数k，从链表头开始k个为一组，进行组内链表翻转。若最后一组不足k个结点，则该组无需翻转

思路
根据双枪
定义一个函数reverseKGroup，接收参数head，翻转从head开始的第一组，然后对剩下的链表进行递归
1.返回翻转后的链表头
2.找分段函数。显然，当一组不足k个结点时，无需翻转，直接返回现成的该组的第一个结点；否则，只要一组有k个结点，就要递归下去

于是代码如下:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# 这就是组内翻转啊。。。，k个为一组，一组要翻转k - 1次。
# 定义函数reverseKGroup，接收参数head, 翻转从head开始的第一组，完成后返回翻转后的链表头
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        check = head
        count = 0
        # 将check指向一组的末尾
        while check and count < k-1:
            count += 1
            check = check.next

        now_head = head
        # 分段函数。check是否为None是分段依据
        if check:
            # 组内翻转k-1次
            for i in range(k-1):
                # 这里开始三步登基噢
                new_head = head.next
                head.next = new_head.next
                new_head.next = now_head
                now_head = new_head
            head.next = self.reverseKGroup(head.next, k)
        # 出口
        else:
            pass
        return now_head

leetcode#### 50. Pow(x, n)
编写一个函数，返回x的n次方，n可以是负数

思路：
暴力法，x连乘n次，时间复杂度O(n)
二分法，【x的n次方 = x的n//2次方 * x的n//2次方 or x的n//2次方 * x的n//2次方 * x】。注意，这个等式的等号两边是同型的，这就是递推式。有了递推式，出口是啥？当n==0时，返回1

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # 二分

        # 递归出口
        if n == 0:
            return 1.0
        
        negtive = n < 0
        n = abs(n)
        temp = self.myPow(x, n//2)
        if n % 2 == 0:
            return temp*temp if not negtive else 1/(temp*temp)
        else:
            return temp*temp*x if not negtive else 1/(temp*temp*x)

分段做事+返回值：双枪破递归recursion 2019-11-20（未经允许禁止转载）