练8：递归

欢迎大家订阅【蓝桥杯Python每日一练】 专栏，开启你的 Python数据结构与算法 学习之旅！

1 递归

在 Python 中，递归（Recursion） 是一种函数调用自身的编程技术。
递归通常用来解决可以分解为类似子问题的问题，通过函数不断调用自身来完成计算。

【示例】

2 汉洛塔问题

【问题分析】

【示例代码】

# n个盘子从A挪到C，利用中间的B
def Move(n,A,B,C):
    if n==0:
        return
    # 1.将n-1个盘子从A挪到B
    Move(n-1,A,C,B)
    # 2.将第n个盘子从A挪到C
    print("{}->{}".format(A,C))
    # 3.将n-1个盘子从B挪到C
    Move(n-1,B,A,C)

【代码分析】

①函数定义与参数说明

def Move(n, A, B, C):

• n：盘子的数量。
• A：起始杆，初始时盘子在此处。
• B：辅助杆，作为中间过渡。
• C：目标杆，所有盘子最终移到此处。

②核心思想
a. 递归的拆解逻辑：

• 如果只有 1 个盘子（即 n=1），直接将盘子从 A 移到 C。
• 如果有多个盘子，递归将问题分成三步：
  1. 将 n-1 个盘子从 A 移到 B，使用 C 作为辅助杆。
  2. 将第 n 个盘子从 A 移到 C。
  3. 将 n-1 个盘子从 B 移到 C，使用 A 作为辅助杆。

b. 递归终止条件：
当 n==0 时，不需要移动任何盘子，直接返回。

③代码执行流程
调用 Move(3, 'A', 'B', 'C')，即将 3 个盘子从 A 移动到 C。

第一次调用 Move(3, 'A', 'B', 'C')

• 调用 Move(2, 'A', 'C', 'B')：将前 2 个盘子从 A 移到 B，使用 C 作为辅助杆。

• 移动第 3 个盘子：打印 A->C，将第 3 个盘子从 A 移动到 C。

• 调用 Move(2, 'B', 'A', 'C')：将前 2 个盘子从 B 移到 C，使用 A 作为辅助杆。

第二次调用 Move(2, 'A', 'C', 'B')

• 调用 Move(1, 'A', 'B', 'C')：将第 1 个盘子从 A 移到 C，使用 B 作为辅助杆。

• 移动第 2 个盘子：打印 A->B，将第 2 个盘子从 A 移动到 B。

• 调用 Move(1, 'C', 'A', 'B')：将第 1 个盘子从 C 移到 B，使用 A 作为辅助杆。

基本情况 Move(1, A, B, C)：直接打印 A->C，将盘子从 A 移到 C。

④运行结果
根据上述逻辑，Move(3, 'A', 'B', 'C') 的打印顺序为：

A->C
A->B
C->B
A->C
B->A
B->C
A->C

3 数的计算

题目地址：https://www.lanqiao.cn/problems/760/learning/

样例输入

6

样例输出

6

【示例代码】

def f(n):
    if n==1:
        return 1
    ans=1
    for i in range(1,n//2+1):
        ans+=f(i)
    return ans

n=int(input())
print(f(n))

【代码分析】

①函数 f(n) 的意义

• f(n)：表示自然数 ( n ) 按照规则处理后，能够产生的数的总数。
• 递归思路：
  • 如果 ( n = 1 )，只能产生一个数，即自身，返回 1。
  • 如果 ( n > 1 )，初始时已经有 ( n ) 自身，因此 ans 初始值为 1。
  • 遍历 ( i ) 从 1 到 ( n // 2 )，对于每个 ( i )，将 ( i ) 加到左边，并递归调用 f(i) 计算以 ( i ) 为基础的情况数，然后累加到 ans。

②核心逻辑
a. 归终止条件

if n == 1:
    return 1

当 ( n = 1 ) 时，直接返回 1，表示只能产生一个数。

b. 递归过程

for i in range(1, n // 2 + 1):
    ans += f(i)

• 遍历所有 ( i ) 从 1 到 ( n // 2 )，因为题目规定：左侧加的数不能超过 ( n ) 的一半。
• 对于每个 ( i )，递归调用 f(i)，累加其返回值，表示从 ( i ) 开始的所有可能情况。

③结果返回

return ans

返回累积的总数。

④执行流程
输入 ( n = 6 )，调用 f(6)。

a. 递归展开

• f(6)：
  1. 初始值：ans = 1（自身）。
  2. 遍历 ( i = 1, 2, 3 )（因为 ( 6 // 2 = 3 )）。
     • ( i = 1 )：调用 f(1)，返回 1，累加 ans = 2。
     • ( i = 2 )：调用 f(2)，继续递归：
       • f(2)：
         • 初始值：ans = 1。
         • 遍历 ( i = 1 )：
           • ( i = 1 )：调用 f(1)，返回 1，累加 ans = 2。
         • 返回 2。
       • 回到 f(6)，累加 ans = 4。
     • ( i = 3 )：调用 f(3)，继续递归：
       • f(3)：
         • 初始值：ans = 1。
         • 遍历 ( i = 1 )：
           • ( i = 1 )：调用 f(1)，返回 1，累加 ans = 2。
         • 返回 2。
       • 回到 f(6)，累加 ans = 6。
  3. 返回 f(6) = 6。

b. 中间过程

1. f(1) = 1
2. f(2) = 2：
   • 初始 ans = 1。
   • 遍历 ( i = 1 )：f(1) = 1，累加 ans = 2。
   • 返回 2。
3. f(3) = 2：
   • 初始 ans = 1。
   • 遍历 ( i = 1 )：f(1) = 1，累加 ans = 2。
   • 返回 2。
4. f(6) = 6：
   • 初始 ans = 1。
   • 遍历 ( i = 1, 2, 3 )：累加 f(1) + f(2) + f(3) = 1 + 2 + 2 = 5。
   • 总和：ans = 6。

【运行结果】