递归的概念

1.1 递归的定义及其基本概念。

递归就是某些东西重复执行自己。想象下，你手上有一份指令，其中一部分说要执行这份指令本身。就像你给了一条命令，结果命令中还有重复这条命令的内容。

生活中的例子：

面对面的镜子：

想象一下你站在两个镜子之间。你能看到自己的倒影，同时也能在倒影里看到倒影，这种反复继续下去。这就是递归的一个例子，因为每个镜子都在展示另一个镜子的倒影。

俄罗斯套娃：

这个套娃就像一个娃娃里还有另一个娃娃，以此类推。当你看到最小的那个娃娃时，没有再可以打开的了。这就像 递归中的基本情况—停止的时刻。

分披萨：

想象一下你将披萨切成两半。然后你拿出一半再切成两半，这样一直继续下去，直到片段太小无法再切。分割的过程就是递归，而 当你不能再切片时，便是基本情况。

重要! 递归不是命令的无限重复，而是将复杂任务分解成部分来解决，这种方法与解决整个任务是相似的。

它是如何工作的？

要了解递归，你需要知道两个主要概念：

• 基本情况: 这是递归终止的条件。例如，在套娃的例子中，基本情况就是打开最后一个娃娃时，里面什么也没有。
• 递归情况: 这是任务随着较小的部分重复。在披萨的例子中，你分割一块，然后是半块，以此类推。

这有什么用呢？

递归帮助我们解决复杂的问题，通过分解成更简单的部分。你不用一次性解决整个任务，而是逐个解决。

生活中的其他例子：

嵌套故事：

想象故事的主角在讲另一个故事，而那个故事中的主角又开始讲另一个故事。当其中一个故事结束时，你返回到上一个故事。基本情况是最后一个故事结束时。

递归图案：

你画了一个大三角形，然后在每个角上画了一个小三角形，这样继续下去，直到三角形太小无法再画。基本情况是当三角形太小不能再画时。

1.2 基本情况：定义和例子。

基本情况就是结束递归调用并让函数返回具体值的条件。通常，这是问题最简单和最明显的解决方案，不需要进一步的递归。

基本情况的例子：

阶乘：

数字 n 的阶乘表示为 F(n) == 1*2*3*…*n。显然， F(n) == n* F(n-1)。

基本情况: 数字 0 或 1 的阶乘为 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # 基本情况
    else:
        return n * factorial(n - 1)
        

斐波那契数列：

斐波那契数列是这样的序列：1, 1, 2, 3, 5, 8, 13, … 每个下一个数字是前两个数字的和。F(n) == F(n-1) + F(n-2)

基本情况: 前两个斐波那契数等于1，所以“第零”斐波那契数等于0。即 F(0) = 0 和 F(1) = 1.

def fibonacci(n):
    if n == 0:
        return 0  # 基本情况
    elif n == 1:
        return 1  # 基本情况
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 递归情况：定义和例子

递归情况是函数中通过调用自己并使用新的参数来解决问题的部分，这些参数使得解决方案更接近基本情况。每次递归调用都会减少或修改任务，最终达到基本情况。

递归情况的例子：

阶乘：

递归情况：数字 n 的阶乘等于 n 乘以数字 n-1 的阶乘。

def factorial(n):
    if n == 0 or n == 1:
        return 1  # 基本情况
    else:
        return n * factorial(n - 1)  # 递归情况
        

斐波那契数列：

递归情况：F(n) 等于 F(n-1) 和 F(n-2) 的和。

def fibonacci(n):
    if n == 0:
        return 0  # 基本情况
    elif n == 1:
        return 1  # 基本情况
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # 递归情况
        

1.4 递归算法的例子

1. 遍历二叉树：

示例 "in-order" 遍历。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# 使用示例:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. 查找列表中的最大元素：

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # 基本情况
    else:
        max_of_rest = find_max(lst[1:])  # 递归情况
        return max(lst[0], max_of_rest)
        
# 使用示例:
print(find_max([1, 5, 3, 9, 2]))  # 输出: 9
        
        

3. 递归二分查找：

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # 基本情况: 元素未找到
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # 基本情况: 元素找到
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # 递归情况
    else:
        return binary_search(arr, target, left, mid - 1)  # 递归情况
        
# 使用示例:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # 输出: 4