AI开发 - 算法基础 递归 的概念和入门（一） 递归算法的常见应用 PYTHON

一、递归的概念

在编程中，我们常常会遇到一个概念：递归。

递归是一个函数调用自身来解决问题的过程。你可以把它看作是“自我重复”的方法，用来分解复杂问题。

1. 举个例子：

想象你在一个楼梯上，每个台阶都有一个编号。如果你站在某个台阶上，要想知道距离地面多少个台阶，你可以做两件事：

1. 看看自己前面（一个台阶）的台阶距离地面有多远。
2. 然后，加上一个台阶的高度。

这个过程会一直重复下去，直到你到达楼梯的最底部，显然最底部的台阶距离地面是0。

这就是递归的一个典型应用：每个步骤都依赖于自己前一个步骤的结果。

递归的逻辑图 

2. 数学上的递归：

比如，计算阶乘（n!）就是一个递归的例子。阶乘的定义是：

• 0! = 1
• n! = n * (n-1)!

也就是说，n的阶乘等于n乘以(n-1)的阶乘，直到n=0时返回1。

3. 递归的关键点：

1. 基准条件：递归必须要有一个停止的条件，通常是一个简单的、能直接解决的问题（比如上面提到的0! = 1）。
2. 递归条件：问题要被分解为一个更小的子问题，直到基准条件触发。

4. 递归的实际代码：

def factorial(n):
    if n == 0:  # 基准条件
        return 1
    else:
        return n * factorial(n - 1)  # 递归条件

在这个例子中，factorial 函数会调用自己，直到 n 减小到 0。每一次递归都会计算一个较小的子问题，直到最简单的情况被解决。

递归的一个重要特点是它可以让程序代码更加简洁，尤其在处理一些分解式问题时非常有效，比如树的遍历、斐波那契数列等。

5. 递归的核心概念：

1. 分解问题：递归通过将一个大问题分解为多个小问题来解决。每个小问题都可以通过相同的方式继续分解，直到它变得足够简单，可以直接解决。
2. 回归（返回）：递归过程需要一个返回的过程，当问题被分解到足够简单时，递归会逐步“回退”，并汇总答案。

6. 递归的结构：

• 基准条件：递归必须有一个停止条件。没有停止条件的话，递归会无限进行下去，导致栈溢出错误。
• 递归步骤：每次递归调用时，问题要缩小或简化（一般通过参数变化来实现）。

7. 经典的递归：斐波那契数列

斐波那契数列是一个由意大利数学家斐波那契（Fibonacci）提出的数列，定义为：从第三项开始，每一项等于前两项之和。其递推公式为：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) （n ≥ 2）

例如，斐波那契数列的前几个数是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

该数列在自然界中有许多应用，如植物的叶片排列、花瓣数目等。此外，斐波那契数列还在计算机科学中有重要应用，如动态规划、递归算法等。通过递归或迭代方式可以计算斐波那契数列的第n项，且其具有很高的数学和计算机理论价值。

递归实现斐波那契数列：

def fibonacci(n):
    # 基准条件
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # 递归条件
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# 测试递归函数
print(fibonacci(5))  # 输出 5

在这个示例中：

1. 基准条件：当 n 为 0 或 1 时，直接返回结果（0 或 1）。
2. 递归步骤：对于其他的 n，通过 fibonacci(n-1) 和 fibonacci(n-2) 来计算。

比如，调用 fibonacci(5) 时，执行的步骤是：

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(2) = fibonacci(1) + fibonacci(0)

最终结果是 5。 

有些人不理解为什么最终结果是5  不应该是0 或者1 吗？

这个问题问得很好！

实际上 递归函数自被使用后，它就有可能不止返回一次。比如 上面的这个例子，如果我们在返回1 的前面，加上“ print('return')” ，也就是打印一个标记，那我们在运行后就会发现：

你可以看到5次返回，每次都是返回1， 所以最终返回的值是5个1的聚合，就是5. 

这种递归方式虽然简洁，但效率较低，因为许多子问题被重复计算了多次。

如果我们在每个返回前都打印一个字符串return： “ print('return')”，我们会发现总共有15个返回。

上面的这些问题，我们可以通过 动态规划 或 记忆化 方法来优化它。

8. 递归优化：记忆化

记忆化是一种优化递归算法的方法，通过缓存已经计算过的结果，避免重复计算。我们可以通过字典或数组来缓存每次计算的结果。

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n] #缓存放在这个字典（数组）里面，当下次有同样的n，不用计算了
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        result = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
        memo[n] = result
        return result

# 测试优化后的函数
print(fibonacci_memo(5))  # 输出 5

在这个版本中，我们引入了一个 memo 字典，它会缓存已经计算过的 fibonacci(n) 值。这样，当我们再次遇到相同的 n 时，就可以直接返回缓存的结果，避免重复计算。

二、递归的应用：

递归不仅仅用于数学问题，还广泛应用于很多领域，尤其是树形结构的遍历和分治算法。

递归在计算机科学和算法中有许多典型的应用，特别是在处理结构化数据（如树、图）或分治问题时非常有效。下面是一些常见的递归应用：

1. 树的遍历

树是递归结构的典型例子，树的遍历通常使用递归来实现。树的遍历有三种常见方式：

• 前序遍历：根节点 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根节点 -> 右子树
• 后序遍历：左子树 -> 右子树 -> 根节点

示例：二叉树的前序遍历

如下图，我们先来定义一个简单的二叉树： 

接着我们用代码来实现对这个二叉树的遍历： 

class TreeNode: 
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def preorder_traversal(root):
    if root is None:
        return
    print(root.value, end=" ")  # 先访问根节点
    preorder_traversal(root.left)  # 递归访问左子树
    preorder_traversal(root.right)  # 递归访问右子树

# 构建一个简单的二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 前序遍历
preorder_traversal(root)  # 输出：1 2 4 5 3

这段代码实现了一个简单的二叉树结构，并使用前序遍历（Preorder Traversal）对二叉树进行遍历。上述代码的解释如下：

1. TreeNode 类定义：

class TreeNode:
    def __init__(self, value):
        self.value = value  # 存储节点的值
        self.left = None  # 左子节点
        self.right = None  # 右子节点

• TreeNode 类表示二叉树的一个节点。
• 每个节点存储一个值（value），以及指向左子节点（left）和右子节点（right）的引用。
• __init__ 方法用于初始化节点对象，当创建一个新节点时，value 被赋值，而 left 和 right 初始化为 None，表示没有子节点。

2. preorder_traversal 函数定义：

def preorder_traversal(root):
    if root is None:
        return  # 如果当前节点为空，返回
    print(root.value, end=" ")  # 先访问根节点
    preorder_traversal(root.left)  # 递归访问左子树
    preorder_traversal(root.right)  # 递归访问右子树

• preorder_traversal 是一个递归函数，用于实现二叉树的前序遍历。
  • 前序遍历的顺序是：先访问根节点，然后递归访问左子树，再递归访问右子树。
• 如果当前节点为空（root is None），则返回，终止递归。
• 如果当前节点不为空，先输出当前节点的值，然后递归遍历左子树和右子树。

3. 构建二叉树：

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

• 这段代码手动构建了一个简单的二叉树：

      1
     / \
    2   3
   / \
  4   5
  

  • root 是树的根节点，值为 1。
  • root.left 和 root.right 分别是值为 2 和 3 的子节点。
  • root.left.left 和 root.left.right 分别是值为 4 和 5 的叶子节点。

4. 执行前序遍历：

preorder_traversal(root)  # 输出：1 2 4 5 3

• 调用 preorder_traversal(root) 来执行前序遍历。
  • 访问根节点 1。
  • 访问左子树，先访问 2，然后访问 4 和 5。
  • 最后访问右子树 3。
• 输出结果是：1 2 4 5 3。

2. 斐波那契数列

斐波那契数列是递归的经典例子。每个数等于前两个数的和。

示例：前面我们已经介绍过了

3. 分治算法：归并排序（Merge Sort）

归并排序是一种典型的分治算法，通过递归地将数组分成两个子数组，直到每个子数组只有一个元素，然后合并这些子数组，得到排序后的数组。

分治算法是一种将大问题分解为多个小问题，分别解决后再合并结果的算法设计思想。它适用于可以分解成子问题并且子问题的解可以合并成整体解的问题。常用于排序（如归并排序、快速排序）、查找（如二分查找）、矩阵运算（如Strassen算法）等。通过减少重复计算，分治算法通常能显著提高效率，尤其在处理大规模数据时表现突出。

示例：归并排序

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])  # 递归分割左半部分
    right = merge_sort(arr[mid:])  # 递归分割右半部分
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 测试
arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # 输出：[3, 9, 10, 27, 38, 43, 82]

这段代码实现了 归并排序（Merge Sort）算法，它是一种分治法（Divide and Conquer）排序算法。归并排序的基本思想是：将数组分成两个子数组，递归地对它们进行排序，然后将两个已排序的子数组合并成一个有序数组。具体的代码解释如下：

1. merge_sort 函数：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])  # 递归分割左半部分
    right = merge_sort(arr[mid:])  # 递归分割右半部分
    return merge(left, right)

• 功能：实现归并排序的递归过程。
• 过程：
  • 基准条件：当数组长度小于等于 1 时，直接返回数组（因为一个元素的数组已经是有序的）。
  • 分割：将数组 arr 从中间分割成两个子数组：left 和 right。
  • 递归排序：分别对 left 和 right 进行递归排序，直到数组分割到足够小（每个子数组只有一个元素）。
  • 合并：通过调用 merge 函数将排序好的 left 和 right 合并为一个有序数组并返回。

2. merge 函数：

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

• 功能：合并两个已排序的子数组 left 和 right 成一个有序数组。
• 过程：
  • 使用两个指针 i 和 j 分别指向 left 和 right 数组的开头。
  • 比较 left[i] 和 right[j]，将较小的元素加入到结果数组 result 中，并相应地移动指针 i 或 j。
  • 当一个数组遍历完毕时，将另一个数组剩余的元素直接添加到 result 中。
  • 最终返回合并后的有序数组 result。

3. 测试代码：

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # 输出：[3, 9, 10, 27, 38, 43, 82]

• 输入：待排序数组 [38, 27, 43, 3, 9, 82, 10]。
• 过程：
  • 归并排序首先将数组分割为两部分：
    • 左部分：[38, 27, 43] 和 右部分：[3, 9, 82, 10]。
  • 然后递归地对每个部分进行排序：
    • 对 [38, 27, 43] 进行排序，得到 [27, 38, 43]。
    • 对 [3, 9, 82, 10] 进行排序，得到 [3, 9, 10, 82]。
  • 最后，合并两个已排序的子数组 [27, 38, 43] 和 [3, 9, 10, 82]，得到最终的排序结果 [3, 9, 10, 27, 38, 43, 82]。

归并排序的特点：

• 归并排序的核心是递归地将数组分成更小的部分，直到每部分只有一个元素。然后通过合并操作将这些小部分重新组合成有序的大部分，最终得到一个完全排序的数组。
• 时间复杂度：归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。
• 空间复杂度：由于需要额外的空间来存储合并后的结果，因此空间复杂度为 O(n)。

4. 快速排序（Quick Sort）

快速排序是一种分治算法，通过选择一个基准元素，将数组分成两部分，然后对这两部分递归排序。快速排序的使用场景非常多，这里不一一赘述，我们下面用一段代码来演示：

示例：快速排序

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]  # 选择第一个元素为基准
    less = [x for x in arr[1:] if x <= pivot]  # 小于基准的部分
    greater = [x for x in arr[1:] if x > pivot]  # 大于基准的部分
    return quick_sort(less) + [pivot] + quick_sort(greater)

# 测试
arr = [38, 27, 43, 3, 9, 82, 10]
print(quick_sort(arr))  # 输出：[3, 9, 10, 27, 38, 43, 82]

这段代码实现了 快速排序（Quick Sort）算法，它是一种分治法（Divide and Conquer）排序算法。快速排序的基本思想是通过选择一个“基准”元素，将数组分为小于基准的部分和大于基准的部分，然后递归地对这两个部分进行排序。

1. quick_sort 函数：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]  # 选择第一个元素为基准
    less = [x for x in arr[1:] if x <= pivot]  # 小于基准的部分
    greater = [x for x in arr[1:] if x > pivot]  # 大于基准的部分
    return quick_sort(less) + [pivot] + quick_sort(greater)

• 功能：实现快速排序。
• 过程：
  • 基准条件：当数组 arr 的长度小于等于 1 时，数组已经是有序的，直接返回 arr。
  • 选择基准元素：选择数组的第一个元素 arr[0] 作为基准元素 pivot。
  • 分割：将数组分成两部分：
    • less：包含所有小于或等于基准元素的元素。
    • greater：包含所有大于基准元素的元素。
  • 递归排序：
    • 对 less 部分递归调用 quick_sort。
    • 对 greater 部分递归调用 quick_sort。
  • 最后，将递归排序后的 less、基准元素 [pivot] 和递归排序后的 greater 合并成一个新的数组，返回排序后的结果。

2. 测试代码：

arr = [38, 27, 43, 3, 9, 82, 10]
print(quick_sort(arr))  # 输出：[3, 9, 10, 27, 38, 43, 82]

• 输入：待排序数组 [38, 27, 43, 3, 9, 82, 10]。
• 过程：
  • 第一次选择 38 作为基准，分割为：
    • less = [27, 3, 9, 10]（小于或等于 38）
    • greater = [43, 82]（大于 38）
  • 对 less 部分 [27, 3, 9, 10] 进行快速排序，选择 27 作为基准，继续分割并递归排序，最终得到 [3, 9, 10, 27]。
  • 对 greater 部分 [43, 82] 进行排序，最终得到 [43, 82]。
  • 最终，合并得到排序后的数组 [3, 9, 10, 27, 38, 43, 82]。

快速排序的特点：

• 快速排序的核心是选择一个“基准”元素，将数组分为两部分，并通过递归对这两部分进行排序，最终合并得到排序好的数组。
• 时间复杂度：
  • 平均情况下，时间复杂度为 O(n log n)。
  • 最坏情况下（当数组已经接近有序时），时间复杂度为 O(n²)。
• 空间复杂度：由于递归调用栈的存在，空间复杂度为 O(log n)，但实际实现中会创建新的子数组，因此还需要额外的空间。

5. 汉诺塔问题（Tower of Hanoi）

汉诺塔问题是一个经典的递归问题。给定三根柱子和若干个不同大小的圆盘，要求将圆盘从一根柱子移动到另一根柱子，且每次只能移动一个圆盘，并且较大的圆盘不能放在较小的圆盘上面。

示例：汉诺塔问题

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
    else:
        hanoi(n-1, source, auxiliary, target)  # 将n-1个盘子从源柱子移到辅助柱子
        print(f"Move disk {n} from {source} to {target}")
        hanoi(n-1, auxiliary, target, source)  # 将n-1个盘子从辅助柱子移到目标柱子

# 测试
hanoi(3, 'A', 'C', 'B')

这段代码实现了经典的 汉诺塔问题（Tower of Hanoi）的递归解法。

上面的汉诺塔问题可以仔细分析如下：

• 有三根柱子（源柱子 A、目标柱子 C、辅助柱子 B），和若干个盘子（每个盘子的大小不同）。
• 任务是将所有盘子从源柱子移动到目标柱子，且遵守以下规则：
  1. 每次只能移动一个盘子。
  2. 任何时候大盘子不能放在小盘子上面。
  3. 使用辅助柱子来帮助移动。

代码分析：

hanoi 函数：

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
    else:
        hanoi(n-1, source, auxiliary, target)  # 将n-1个盘子从源柱子移到辅助柱子
        print(f"Move disk {n} from {source} to {target}")
        hanoi(n-1, auxiliary, target, source)  # 将n-1个盘子从辅助柱子移到目标柱子

• 参数说明：

  • n：表示盘子的数量。
  • source：源柱子，盘子开始时所在的柱子。
  • target：目标柱子，盘子需要移动到的柱子。
  • auxiliary：辅助柱子，移动过程中暂时存放盘子的柱子。

• 逻辑解析：

  1. 基准条件（n == 1）：
     • 如果只有一个盘子，直接将它从 source 移到 target，并打印操作：

       print(f"Move disk 1 from {source} to {target}")
       

  2. 递归条件（n > 1）：
     • 先将 n-1 个盘子从 source 移动到 auxiliary（借助 target 作为辅助）。

       hanoi(n-1, source, auxiliary, target)
       

     • 然后将第 n 个盘子（即最大盘子）从 source 移动到 target。

       print(f"Move disk {n} from {source} to {target}")
       

     • 最后，将之前移动到 auxiliary 上的 n-1 个盘子从 auxiliary 移动到 target（借助 source 作为辅助）。

       hanoi(n-1, auxiliary, target, source)
       

递归的过程：

• 该函数使用递归的方式，先解决一个较小的子问题（将 n-1 个盘子从源柱子移动到辅助柱子），然后再解决更大的子问题（将最大的盘子移动到目标柱子），最后再解决剩下的子问题（将 n-1 个盘子从辅助柱子移动到目标柱子）。

测试代码：

hanoi(3, 'A', 'C', 'B')

• 输入：3 个盘子，源柱子 A，目标柱子 C，辅助柱子 B。
• 输出：程序将输出每一步的移动过程。具体步骤如下：

递归展开：

1. 将 3 个盘子从 A 移动到 C，借助 B。
   • 首先，将 2 个盘子从 A 移动到 B，借助 C。
     • 然后，将 1 个盘子从 A 移动到 C。
     • 接着，将盘子 2 从 A 移动到 B。
     • 最后，将 1 个盘子从 C 移动到 B。
   • 然后，将盘子 3 从 A 移动到 C。
   • 最后，将 2 个盘子从 B 移动到 C，借助 A。
     • 同样，先将盘子 1 从 B 移动到 A，再将盘子 2 从 B 移动到 C，最后将盘子 1 从 A 移动到 C。

输出：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

6. 深度优先搜索（DFS）

在图或树的遍历中，深度优先搜索（DFS）使用递归来实现。DFS从一个节点开始，递归地访问其所有邻居节点，直到没有新的节点可以访问。

常见的实际应用包括：

1. 图的遍历：DFS可用于遍历图中的所有节点，适用于无权图的搜索、连通分量的查找等。
2. 路径寻找：在迷宫问题、机器人路径规划等应用中，DFS能够帮助找到从起点到终点的路径，特别适合解决路径问题。
3. 拓扑排序：在有向无环图（DAG）中，DFS可以用来实现拓扑排序，常用于任务调度、依赖关系解决等场景。
4. 连通性分析：DFS可以检测图中是否存在环，或者判断图是否是连通的，常用于网络连通性分析。
5. 图的着色与遍历：在图的着色问题、强连通分量分解中，DFS同样有广泛的应用。

示例：深度优先搜索（DFS）

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=" ")
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 深度优先搜索
dfs(graph, 'A')  # 输出：A B D E F C

7. 回溯算法：求解迷宫

回溯算法通常使用递归来搜索所有可能的解。在求解迷宫问题时，可以使用递归来遍历所有路径，找到从起点到终点的路径。

示例：迷宫问题

def solve_maze(maze, x, y, path=[]):
    # 迷宫的边界检查
    if x < 0 or y < 0 or x >= len(maze) or y >= len(maze[0]) or maze[x][y] == 1:
        return False
    
    # 到达目标点
    if maze[x][y] == 'E':
        path.append((x, y))
        return True
    
    # 标记当前位置
    maze[x][y] = 1  # 标记为已访问
    
    # 尝试四个方向
    if solve_maze(maze, x + 1, y, path) or solve_maze(maze, x - 1, y, path) or \
       solve_maze(maze, x, y + 1, path) or solve_maze(maze, x, y - 1, path):
        path.append((x, y))
        return True
    
    return False

# 迷宫示例（0表示可走，1表示障碍，'E'表示终点）
maze = [
    [0, 0, 1, 0, 0],
    [1, 0, 1, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1],
    [0, 0, 0, 0, 'E']
]

path = []
solve_maze(maze, 0, 0, path)
print(path)  # 输出路径

好了，今天我们一起来学习了递归 的概念和入门、 递归算法的常见应用，我们可以通过练习上面的代码，然后再修改上面的代码 或者增加一些功能，来加深对递归的理解和应用。下一次我们一起来学习递归再ai算法中的应用。