函数可以调用自己，这种操作称作 递归，通常用来解决 可以被分解为更小相同问题 的问题，从而简化代码逻辑。
一个典型的例子就是计算斐波那契数列：
斐波那契数列的计算公式为 \(F(n) = F(n-1) + F(n-2)\) 其中 $ F(0) = 0 $ ，$ F(1) = 1 $
当 n 小于或等于 0 时，fibonacci 函数返回 0
当 n 等于 1 时，fibonacci 函数返回 1
否则，fibonacci 函数调用自身进行递归
flowchart TD
f4["fibonacci(4)"] --> f3["fibonacci(3)"] & f2["fibonacci(2)"]
f3 --> f1["fibonacci(1)"] & f2
f2 --> f1 & f0["fibonacci(0)"]
f1 --> 1["1"]
f0 --> 0["0"]
n1(["..."]) -.-> f4
示例代码：
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)}")
注意，递归必须存在 终止条件（Base Case），不能无限循环地自我调用。
例如上面代码中当 n 小于等于 1 时返回最终的值，而不再继续向下调用。
因为函数在调用时需要消耗内存创建新的局部作用域，直到函数返回时释放。
无限的自我调用将导致无限的内存消耗，这是对计算机程序来说是致命的错误。
和很多流行的编程语言不同，Python 不支持尾递归优化。
Python 中函数调用深度上限默认为 1000，超过这个上限时会产生 RecursionError: 异常。
求阶乘：
阶乘的计算公式为 \(n! = 1 \times 2 \times 3 \times \cdots \times n\)
# 求阶乘
def factorial(n):
if n == 0:
return 1 # 终止条件
else:
return n * factorial(n - 1) # 递归调用
n:int = int(input("请输入项数 n: "))
print(f"{n} 的阶乘为 {factorial(n)}")
求和：
求和符号的计算公式为 \(\sum_{i=1}^{n} a_i = a_1 + a_2 + \cdots + a_n\)
# 通项公式，这里是 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} 是圆周率的近似值")
汉诺塔问题:
你有 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} 次")