🔄
第 06 章 · 递归习题 · PYTHON

递归习题

15 道递归算法专项练习题，覆盖递归求值、递归遍历、递归分治等经典场景。

展开全部答案

📝 递归习题

15 道递归算法专项练习 · 分 2 页

1
递归求年龄：5人坐一起，第5人比第4人大2岁，第4人比第3人大2岁……第1人10岁。求第5人年龄。
📝 样例输入： n = 5
▶ 运行结果： 第五个人： 18
▼
参考答案
python
def age(n):
    if n == 1:
        return 10
    return age(n - 1) + 2

print("第五个人：", age(5))  # 18
2
使用递归打印从 1 到 n 的数字。
📝 样例输入： n = 10
▶ 运行结果： 1 2 3 4 5 6 7 8 9 10
▼
参考答案
python
def print_num(n):
    if n > 0:
        print_num(n - 1)
        print(n, end=' ')

print_num(10)  # 1 2 3 4 5 6 7 8 9 10
3
递归反转字符串：将输入的字符串用递归方法反转。
📝 样例输入： "hello"
▶ 运行结果： olleh
▼
参考答案
python
def reverse_string(s):
    if len(s) <= 1:
        return s
    return reverse_string(s[1:]) + s[0]

print(reverse_string("hello"))  # olleh
4
递归求斐波那契数列第 n 项的值。
📝 样例输入： n = 10
▶ 运行结果： 55
▼
参考答案
python
def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))  # 55
5
递归判断一个整数 n 是否是 2 的幂次方。
📝 样例输入： 16, 15
▶ 运行结果： True False
▼
参考答案
python
def is_power_of_two(n):
    if n <= 0:
        return False
    elif n == 1:
        return True
    elif n % 2 != 0:
        return False
    return is_power_of_two(n // 2)

print(is_power_of_two(16))  # True
print(is_power_of_two(15))  # False
6
递归乘法：实现两个正整数的乘法，不能使用 * 运算符。
📝 样例输入： 3, 5
▶ 运行结果： 15
▼
参考答案
python
def multiply(a, b):
    if b == 0:
        return 0
    elif b == 1:
        return a
    return a + multiply(a, b - 1)

print(multiply(3, 5))  # 15
7
递归将十进制数转换为二进制字符串。
📝 样例输入： 10
▶ 运行结果： 1010
▼
参考答案
python
def dec_to_bin(n):
    if n == 0:
        return "0"
    elif n == 1:
        return "1"
    return dec_to_bin(n // 2) + str(n % 2)

print(dec_to_bin(10))  # 1010
8
递归求数组元素之和。
📝 样例输入： [1, 2, 3, 4, 5]
▶ 运行结果： 15
▼
参考答案
python
def array_sum(arr):
    if len(arr) == 0:
        return 0
    return arr[0] + array_sum(arr[1:])

print(array_sum([1, 2, 3, 4, 5]))  # 15
9
递归计算整数各位数字之和。
📝 样例输入： 12345
▶ 运行结果： 15
▼
参考答案
python
def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

print(digit_sum(12345))  # 15
10
递归判断字符串是否为回文。
📝 样例输入： "aba", "abc"
▶ 运行结果： True False
▼
参考答案
python
def is_palindrome(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

print(is_palindrome("aba"))   # True
print(is_palindrome("abc"))   # False
11
求 1! + 2! + 3! + ... + 20! 的和（递归实现阶乘）。
📝 样例输入： n = 20
▶ 运行结果： 2561327494111820313
▼
参考答案
python
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

total = sum(factorial(i) for i in range(1, 21))
print(total)  # 2561327494111820313
12
猴子吃桃（递归）：每天吃一半多一个，第10天剩1个，求最初有多少？
📝 样例输入： day = 1（第1天）
▶ 运行结果： 1534
▼
参考答案
python
def peach(day):
    if day == 10:
        return 1
    return (peach(day + 1) + 1) * 2

print(peach(1))  # 1534
13
汉诺塔：3根柱子A、B、C，将A上n个圆盘移到C，每次移一个，大盘不能在小盘上面。输出移动步骤。
📝 样例输入： n = 3, A, B, C
▶ 运行结果： 第1个盘子：A --> C 第2个盘子：A --> B 第1个盘子：C --> B 第3个盘子：A --> C 第1个盘子：B --> A 第2个盘子：B --> C 第1个盘子：A --> C
▼
参考答案
python
def hanoi(n, a, b, c):
    if n == 1:
        print(f"第1个盘子：{a} --> {c}")
        return
    hanoi(n - 1, a, c, b)
    print(f"第{n}个盘子：{a} --> {c}")
    hanoi(n - 1, b, a, c)

hanoi(3, 'A', 'B', 'C')
14
递归阶乘求和：计算 1! + 2! + ... + 10!。
📝 样例输入： n = 10
▶ 运行结果： 4037913
▼
参考答案
python
def factor(n):
    if n < 2:
        return 1
    return n * factor(n - 1)

s = sum(factor(i) for i in range(1, 11))
print(s)  # 4037913
15
递归倒序输出：利用递归将输入的字符以相反顺序打印。
📝 样例输入： hello
▶ 运行结果： 请输入字符：hello olleh
▼
参考答案
python
def print_reverse(chars, idx=0):
    if idx >= len(chars):
        return
    print_reverse(chars, idx + 1)
    print(chars[idx], end="")

s = input("请输入字符：")
print_reverse(s)