理解递归

Python 中的数据结构与算法

Miriam Antona

Software engineer

定义

• 函数调用自身
• 几乎所有用循环的情况
  • 都可用递归替代
• 能解决看似很复杂的问题

示例——阶乘

$n!$

示例——阶乘

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120

示例——用递归求阶乘

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)

• 会一直执行下去！

示例——识别基例

• 添加一个条件
  • 确保算法不会无限执行
• 阶乘的基例 -> $n=1$

def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120

递归如何工作

• 计算机用栈跟踪函数
  • 调用栈

递归如何工作

• factorial(5) 开始
• 在 factorial(5) 结束前 -> 启动 factorial(4)
• 在 factorial(4) 结束前 -> 启动 factorial(3)

递归如何工作

• factorial(5) 开始
• 在 factorial(5) 结束前 -> 启动 factorial(4)
• 在 factorial(4) 结束前 -> 启动 factorial(3)
• 在 factorial(3) 结束前 -> 启动 factorial(2)

递归如何工作

• factorial(5) 开始
• 在 factorial(5) 结束前 -> 启动 factorial(4)
• 在 factorial(4) 结束前 -> 启动 factorial(3)
• 在 factorial(3) 结束前 -> 启动 factorial(2)
• 在 factorial(2) 结束前 -> 启动 factorial(1)

递归如何工作

• factorial(5) 开始
• 在 factorial(5) 结束前 -> 启动 factorial(4)
• 在 factorial(4) 结束前 -> 启动 factorial(3)
• 在 factorial(3) 结束前 -> 启动 factorial(2)
• 在 factorial(2) 结束前 -> 启动 factorial(1)

递归如何工作

• factorial(1) 结束
  • 返回 1
• factorial(2) 结束

递归如何工作

• factorial(1) 结束
  • 返回 1
• factorial(2) 结束
  • 返回 2

递归如何工作

• factorial(1) 结束
  • 返回 1
• factorial(2) 结束
  • 返回 2
• factorial(3) 结束
  • 返回 6

递归如何工作

• factorial(1) 结束
  • 返回 1
• factorial(2) 结束
  • 返回 2
• factorial(3) 结束
  • 返回 6
• factorial(4) 结束
  • 返回 24

递归如何工作

• factorial(1) 结束
  • 返回 1
• factorial(2) 结束
  • 返回 2
• factorial(3) 结束
  • 返回 6
• factorial(4) 结束
  • 返回 24
• factorial(5) 结束
  • 返回 120

递归如何工作

• factorial(1) 结束
  • 返回 1
• factorial(2) 结束
  • 返回 2
• factorial(3) 结束
  • 返回 6
• factorial(4) 结束
  • 返回 24
• factorial(5) 结束
  • 返回 120

动态规划

• 一种优化技术
• 主要用于递归
• 可降低递归算法的复杂度
• 适用于：
  • 可分解为更小子问题的任何问题
  • 子问题彼此重叠
• 保存子问题解，避免重复计算
  • 记忆化

让我们来练习！

Python 中的数据结构与算法