基于python的leetcode算法介绍之递归

零 算法介绍

递归算法是传统算法中较为简单、基础且实用的一个部分。其核心思想就是通过函数对自身的调用，来实现多层嵌套的过程。而在函数递归的时候，为了保证程序的正常运行，我们需要在程序中设置出口，即需要一个判断条件来终止递归。最简单且常用的递归算法就有通过辗转相除法求两个数的最大公因数问题。

一 简单示例 辗转相除法

辗转相除法，也被称为欧几里得算法，是一种求两个整数的最大公因数（GCD）的经典算法。这个算法基于一个原理：两个整数的最大公因数等于较小数和两数相除余数的最大公因数。

具体步骤如下：

1. 将两个数（假设为a和b）中的大数a除以小数b，得到余数r。

2. 将b和余数r作为新的两个数，重复步骤1，直到余数为0。

3. 余数为0时的除数就是最大公因数。

以下是通过循环求解的思路：

# 被除数 将会等于 除数
# 除数 将会等于 余数
# 考虑能否被递归
# 1. 是否存在相同的算法
# 2. 它的终止条件是否唯一
# 考虑到递归的终止条件
# 递归是从最后一层反向传到第一层
def gcd(a, b):  
    while b != 0:  
        a, b = b, a % b  
    return a  

print(gcd(48, 18))
# 18

而当我们采用递归的方式实现时：

def gcd(a, b):
    return gcd(b, a % b) if a % b != 0 else b
  
print(gcd(48, 18))
# 18

Leetcode例题与思路

接下来，我们列举关于Leetcode的五道例题，并通过递归的方式进行求解：

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

解题思路：

关于这道题，其实题目中已经给清了思路，我们按照公式整理即可，详情可看题解。

题解：

class Solution:
    def fib(self, n: int) -> int:
        return self.fib(n-1) + self.fib(n-2) if n > 1 else n

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路：

这道题的解题思路其实有很多，递归仅是其中一个，由于本章是关于递归算法的介绍，所以不做其他方面的阐述。

那么我们来说一下递归的解法：

首先关于递归算法，我们最需要关注的问题是，它的终止条件是什么？ 在这道题里，链表的终止条件似乎是循环到head == None才算结束了。但是问题仅是这样吗？我们需要向下思考一层，那就是当我们在最后一个节点的情况下如何指向上一个节点？在单链表中，显然这是不被允许的！所以，这道题有很关键的一步是，我们判断终止的条件是head.next ≠ None。

当终止条件考虑过后，我们就可以考虑递归的主体了。在主程序中，由于我们的条件保证head.next ≠ None，所以我们可以使得head.next.next = head 这样就可以保证当前节点的下一个节点指向自己。而为了保证我们最后可以拿到逆序后的头节点，我们只需要返回原来链表中的最后一个元素。

题解：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:    # 判断边界并返回逆序后的头节点
            return head
        renode = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return renode

面试题 08.06. 汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

解题思路：

汉诺塔是一道非常经典的递归题目，我也非常喜欢。解这道题最好你玩过汉诺塔，这样你就会有一个基本的逻辑在。不说其他的了，我们来说一下汉诺塔的解题思路：关于这道题，我做一个很形象的比喻：把大象关进冰箱需要几步？只需要三步：打开冰箱门，放进大象，关上冰箱门。忽然这么一说你可能摸不到头脑，但我们可以这么理解：

将汉诺塔从原始柱移到目标柱需要几步？只需要三步：把前N-1层移动到临时柱，把第N层移动到目标柱，把前N-1层在移动到目标柱上。

记住这个逻辑，后面代码中，我将通过raw,temp,aim来替换掉A,B,C。

那这道题目的终止条件是什么呢？

当然是仅剩下一层的时候我该怎么移动了。很简单，从原始柱移动到目标柱就可以了。

那么由于对于N层来说，我们需要把前N-1层移动到临时柱。那么对于前N-1层，那个临时柱就变成了它的目标。提示到这里，聪明的你应该有想法了，那么更精彩的就在代码里了。

题解：

class Solution:
    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
        n = len(A)
        raw, temp, aim = A, B, C
        self.move(n, raw, temp, aim)

    def move(self, n, raw, temp, aim):
        if n == 1:
            aim.append(raw[-1])
            raw.pop()
            return 
        else:
            self.move(n-1, raw, aim, temp)
            aim.append(raw[-1]) 
            raw.pop() 
            self.move(n-1,temp, raw, aim)

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

解题思路：

如果你不知道二叉树的遍历，那么很遗憾，你需要先补习相关知识，之前说的递归的知识其实已经足够了。二叉树和递归其实是相互纠缠的一对儿，所以我们还要讲几到二叉树的题目。

中序遍历：即左子树，根结点，右子树三步走。

而在这道题中，我们先找一下终止条件：即作为树的叶子节点即可返回。

而在程序主体中，我们进需要按照左，中，右的逻辑对列表做拼接即可。

还需要注意一点，就是要小心空树哦。

题解：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        elif root.left == None and root.right == None:
            return [root.val]
        else:
            my_list = self.inorderTraversal(root.left) if root.left != None else []
            my_list = my_list + [root.val]
            my_list = my_list + self.inorderTraversal(root.right) if root.right != None else my_list
            return my_list

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

解题思路：

如何判断一个二叉树是否对称？它仅满足一个条件，即二叉树的左子树和右子树呈现镜像对称。什么意思呢？就是左子树的右节点应该风雨右子树的左节点。

去判断一棵树满足对称二叉树的条件，不如去找他不满足的地方。这是算法那种的一个很重要的思想：判断成功需要挨个证明，但判断失败仅需要一次就行。

那接下来，我们来说一下终止条件：

1. 成功：当左右镜像最后都成为None的情况下，就是最终的胜利。

2. 迭代：当左右都没到叶子节点的时候，且左右根的值相同。

3. 失败：不满足以上条件就是失败。

所以代码很简单可以写成一下形式：

题解：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def search(left, right):
            if left == None and right == None:
                return True
            elif left != None and right != None and left.val == right.val:
                return search(left.left, right.right) and search(left.right, right.left)
            else:
                return False
        return search(root.left, root.right) if root != None else True

以上就是关于递归的一些见解，我将不定期的更新该系列，来完善基于python的算法体系。