递归函数
- 函数内部直接或间接的调用函数自身
- 将复杂问题简单化
例子程序
def sum_digits(n):
"""Return the sum of the digits of positive integer n."""
if n < 10:
return n
else:
all_but_last, last = n // 10, n % 10
return sum_digits(all_but_last) + last- 各位数字之和问题分解为两个步骤
- 除了最后一个数字以外所有数字相加
- 然后加上最后一个数字
相互递归
def is_even(n):
if n == 0:
reutrn True
else:
return is_odd(n-1) def is_odd(n):
if n == 0:
return False
else:
return is_even(n-1) result = is_even(4)- game
- 一个双人游戏，桌上有n个鹅卵石，每次一个人能从桌子上拿走一个或两个鹅卵石，拿走最后一个鹅卵石的人胜利
- Alice每次只拿走一个鹅卵石
- Tom在鹅卵石是偶数的时候拿走两个鹅卵石，反之拿走一个鹅卵石
- 最终谁会获胜
def play_Alice(n):
if n == 0:
print("Tom wins!")
else:
play_Tom(n-1) def play_Tom(n):
if n == 0:
print("Alice wins!")
elif(n%2 == 0):
play_Alice(n-2)
else:
play_Alice(n-1)
树递归
- 一个函数调用自己大于一次
- 例子（斐波那契数列）：
-
def Fibo(n):
if n == 1:
return 0
if n == 2:
return 1
if n > 2:
return Fibo(n-2) + Fibo(n-1)def count_partitions(n, m):
"""Count the ways to partition n using parts up to m."""
if n == 0:
return 1
elif n < 0:
return 0
elif m == 0:
return 0
else:
return count_partitions(n-m, m) + count_partitions(n, m-1) - 不断将函数以m为界分段，直到全部分为1
-