Python系列 - 递归函数

1. 递归函数

#

我们知道在函数的内部，可以调用其他函数。那如果一个函数在内部调用自身本身，这个函数就是递归函数。

• 递归函数通常包括两个主要部分：
  • 基准情形（Base Case）：这是递归停止的条件，防止函数无限制地调用自身。
  • 递归情形（Recursive Case）：函数调用自身的部分，它将问题分解为更小的子问题来求解。

编写递归函数的技巧就是：我们只需要考虑前后几个关系，例如1，2，以及n，n-1的关系，没必要展开考虑中间的关系，否则就是自讨苦吃。

• 递归的优缺点
  • 优点：
    • 简洁和易于理解：对于一些问题，递归能以更自然和简洁的方式表达。
    • 解决分治问题：递归特别适用于那些可以分解为类似子问题的问题，例如二分查找、快速排序和合并排序。
  • 缺点：
    • 性能问题：每次递归调用都有函数调用开销，可能导致较高的内存和时间开销。
    • 递归深度限制：Python 默认递归深度限制为 1000 层，如果递归深度过深，会引发 RecursionError。

1.1. 斐波那契数列

#

• 斐波那契数列是递归的经典例子。其定义为：
  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) （n ≥ 2）
• 以下是用 Python 实现斐波那契数列的递归函数：

  def fibonacci(n):
      if n <= 0:
          return 0
      elif n == 1:
          return 1
      else:
          return fibonacci(n-1) + fibonacci(n-2)
  

1.2. 阶乘

#

• 定义：
  $$ factorial(n) = n! = 1 \times 2 \times 3 \times ··· \times (n-1) \times n $$
• 以下是 Python 用递归函数实现的代码：

  def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
  

使用递归函数需要注意防止栈溢出。 在计算机中，函数调用是通过栈（stack）这种数据结构实现的， 每当进入一个函数调用，栈就会加一层栈帧， 每当函数返回，栈就会减一层栈帧。 由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。 可以试试fact(1000)，会引发错误。

2. 尾递归

#

尾递归是一种特殊的递归形式，其中递归调用是函数中最后执行的操作。在尾递归中，递归调用之后没有其他操作，因此可以直接返回递归调用的结果。这种递归形式可以被编译器或解释器优化，减少函数调用的开销，从而避免栈溢出。

def factorial_tail_recursive(n, acc=1):
    if n == 0:
        return acc
    else:
        return factorial_tail_recursive(n-1, n*acc)

• 在这个例子中，递归调用是最后一个操作，没有其他运算。递归的累积结果通过 acc 参数传递（在 1.2. 中递归调用之后还有乘法运算）。

• 我们调用这个尾递归函数时，无需传递 acc 参数的值（默认为1）。在内部调用时会赋予 acc = n * acc

• 尾递归优化

  • 尾递归优化（Tail Call Optimization, TCO）是一种编译器优化技术，它能够将尾递归转换为迭代，从而避免创建新的栈帧。这样，尾递归调用就不会增加调用栈的深度，从而节省内存和提高性能。
  • 遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，所以，上面的尾递归方式，也有栈溢出的问题。

• 也有一些编程语言支持尾递归优化，例如：

  • Scheme：作为函数式编程语言，Scheme 明确要求实现尾递归优化。
  • Haskell：Haskell 编译器 GHC 会对尾递归进行优化。
  • Scala：支持尾递归优化，但需要使用注解 @tailrec 来显式标注。

3. 递归练习

#

3.1. 汉诺塔的移动

#

汉诺塔（Tower of Hanoi）是一种经典的递归问题，它由法国数学家爱德华·卢卡斯在1883年提出。问题的描述如下：

• 有三根柱子（通常称为A柱、B柱和C柱），A柱上从下到上按大小顺序叠放着若干个圆盘（最小的圆盘在最上面），目标是将这些圆盘从A柱全部移动到C柱，并且满足以下规则：

  • 每次只能移动一个圆盘。
  • 圆盘只能放在柱子上，不能放在柱子以外的地方。
  • 不能将较大的圆盘放在较小的圆盘上。

• 汉诺塔问题的递归解法

  • 解决汉诺塔问题的关键在于将问题分解为更小的子问题。假设有n个圆盘在A柱，目标是将它们全部移动到C柱，可以按以下步骤进行：
    • 将前n-1个圆盘从A柱移动到B柱，使用C柱作为辅助柱。
    • 将第n个（即最大的）圆盘从A柱移动到C柱。
    • 将前n-1个圆盘从B柱移动到C柱，使用A柱作为辅助柱。
    • 递归的基本情况是当只有一个圆盘时，直接将其从起始柱移动到目标柱。

• 代码：

  def hanoi(n, a, b, c):
      # base case
      if n == 1:
          print(f'将 {a} 移动到 {c}')
      else:
          # 除了最下面的一层，其余全部从 a->b
          hanoi(n - 1, a, c, b)
          # 将 a 剩下的这个最大的块移动到c上
          hanoi(1, a, b, c)
          # 上面已经完成一个最大块移到了目标柱子上。
          # 再将之前的n-1块从 b 移到 c 上，a 用于辅助。
          hanoi(n - 1, b, a, c)
  
  
  if __name__ == '__main__':
      hanoi(3, "A", "B", "C")
  

• 输出：

  将 A 移动到 C
  将 A 移动到 B
  将 C 移动到 B
  将 A 移动到 C
  将 B 移动到 A
  将 B 移动到 C
  将 A 移动到 C
  

• 这里 hanoi(n, a, b, c) 的 a 代表需要移动圆盘的柱子；b 代表提供辅助的柱子；c 代表目标柱子。

4. 附录：栈的介绍

#

栈（Stack）是一种常见的数据结构，遵循后进先出（LIFO, Last In First Out）的原则。栈只允许在一端进行操作，这一端称为栈顶（Top）。栈的两种基本操作是：

• 压栈（Push）：将元素添加到栈顶。

• 弹栈（Pop）：从栈顶移除元素。

• 栈的特点

  • LIFO：最后一个被压入栈的元素最先被弹出。
  • 只能在栈顶进行操作：添加和删除元素都只能在栈顶进行。

• 栈的应用

  • 栈在计算机科学和编程中有广泛的应用，常见的应用场景包括：

    • 函数调用管理：递归调用时，系统会使用栈来保存每次函数调用的状态（如返回地址、局部变量等）。

    • 表达式求值：用于中缀表达式转后缀表达式的过程中。

    • 括号匹配：用于检查表达式中的括号是否匹配。

    • 浏览器历史记录：管理前进和后退操作。

    • 栈的实现

      • 栈可以通过数组或链表来实现。下面是Python中用列表实现栈的示例：

      class Stack:
          def __init__(self):
              self.items = []
      
          def is_empty(self):
              return len(self.items) == 0
      
          def push(self, item):
              self.items.append(item)
      
          def pop(self):
              if self.is_empty():
                  raise IndexError("pop from empty stack")
              return self.items.pop()
      
          def peek(self):
              if self.is_empty():
                  raise IndexError("peek from empty stack")
              return self.items[-1]
      
          def size(self):
              return len(self.items)
      
      # 示例使用
      stack = Stack()
      stack.push(1)
      stack.push(2)
      stack.push(3)
      print(stack.pop())  # 输出 3
      print(stack.peek()) # 输出 2
      print(stack.size()) # 输出 2
      

  • 主要操作:
    • is_empty：检查栈是否为空。
    • push：将元素压入栈顶。
    • pop：从栈顶弹出元素。
    • peek：返回栈顶元素，但不弹出。
    • size：返回栈中的元素数量。

• 栈的时间复杂度

  • 在栈中，所有的基本操作（如push、pop、peek和is_empty）都可以在O(1)时间内完成。这是因为这些操作只涉及栈顶的元素，而不需要遍历整个栈。

• 栈的实现示例：括号匹配

  • 以下是一个使用栈来检查表达式中的括号是否匹配的示例：

    def is_balanced(expression):
        stack = Stack()
        matching_brackets = {')': '(', '}': '{', ']': '['}
    
        for char in expression:
            if char in matching_brackets.values():
                stack.push(char)
            elif char in matching_brackets.keys():
                if stack.is_empty() or stack.pop() != matching_brackets[char]:
                    return False
    
        return stack.is_empty()
    
      # 示例使用
    print(is_balanced("({[]})"))  # 输出 True
    print(is_balanced("({[})"))   # 输出 False
    

5. 参考资料

#

• https://www.liaoxuefeng.com/wiki/1016959663602400/1017268131039072