#Python 函数的递归调用

函数可以调用自己，这种操作称作递归，通常用来解决 可以被分解为更小相同问题 的问题，从而简化代码逻辑。

一个典型的例子就是计算斐波那契数列：

斐波那契数列的计算公式为其中，

当 n 小于或等于 0 时，fibonacci 函数返回 0
当 n 等于 1 时，fibonacci 函数返回 1
否则，fibonacci 函数调用自身进行递归

示例代码：

def fibonacci(n:int) -> int:
    if n <= 0:
        return 0    # 终止条件
    elif n == 1:
        return 1    # 终止条件

    return fibonacci(n - 1) + fibonacci(n - 2)  # 递归调用

n:int = int(input("请输入项数 n: "))
print(f"斐波那契数列的第 {n} 项为 {fibonacci(n)}")
>>> Establishing WebAssembly Runtime. 
>>> Standby. 
Powered by Shift.

#注意事项

注意，递归必须存在 终止条件（Base Case），不能无限循环地自我调用。

例如上面代码中当 n 小于等于 1 时返回最终的值，而不再继续向下调用。

因为函数在调用时需要消耗内存创建新的局部作用域，直到函数返回时释放。

无限的自我调用将导致无限的内存消耗，这是对计算机程序来说是致命的错误。

和很多流行的编程语言不同，Python 不支持尾递归优化。

Python 中函数调用深度上限默认为 1000，超过这个上限时会产生 RecursionError: 异常。

#示例

求阶乘：

阶乘的计算公式为

# 求阶乘
def factorial(n):
    if n == 0:
        return 1  # 终止条件
    else:
        return n * factorial(n - 1)  # 递归调用

n:int = int(input("请输入项数 n: "))
print(f"{n} 的阶乘为 {factorial(n)}")
>>> Establishing WebAssembly Runtime. 
>>> Standby. 
Powered by Shift.

求和：

求和符号的计算公式为

# 通项公式，这里是 MadHava 级数
def madhave(i):
    return (-1)**i / (2*i+1)

# 求和
def sum(fn, n):
    if n == 0:
        return fn(0)  # 终止条件
    else:
        return fn(n) + sum(fn, n - 1)  # 递归调用 sum

n:int = int(input("请输入项数 n: "))
result:float = sum(madhave, n)
print(f"MadHava 级数的的前 {n} 项和为 {result}，它的四倍 {4*result} 是圆周率的近似值")
>>> Establishing WebAssembly Runtime. 
>>> Standby. 
Powered by Shift.

汉诺塔问题:

你有 A B C 三根柱子和若干个大小不一的圆盘

圆盘一开始按从大到小的顺序堆叠在最 A 柱上

每次只能移动一个盘子

大盘子不能放在小盘子上面。

目标：将所有盘子从柱子 A 移动到柱子 C，借助柱子 B 求 n 个盘子需要移动多少次？

def hanoi(n, source, helper, target, count=0):
    '''
    移动汉诺塔

    :param n: 盘子的数量
    :param source: 起始的柱子
    :param helper: 辅助的柱子
    :param target: 目标的柱子
    :param count: 移动次数计数
    '''
    if n == 1:
        print(f"将 {n} 号盘子从 {source} 移动到 {target}")
        return count + 1
    else:
        # 第一步：将 n-1 个盘子从 source 移动到 helper
        count = hanoi(n-1, source, target, helper, count)

        # 第二部，将第 n 个盘子从 source 移动到 target
        count += 1
        print(f"将 {n} 号盘子从 {source} 移动到 {target}")

        # 第三步：将 n-1 个盘子从 helper 移动到 target
        return hanoi(n-1, source, target, helper, count)


n:int = int(input("请输入项数 n: "))
count:int = hanoi(n, 'A', 'B', 'C')
print(f"{n} 个盘子的汉诺塔需要移动 {count} 次")
>>> Establishing WebAssembly Runtime. 
>>> Standby. 
Powered by Shift.