代码收藏家技术教程 2023-06-20

Python函数递归案例详解

1、猴子吃桃

问题描述：

一个猴子第一天吃掉桃子的一半又多一个，第二天照此方法又吃掉剩下一半加一个，以后每天如此，直到第十天早上，只剩下了一个桃子，问第一天原本多少个桃子

代码实现：

def myfunc(n):
    if n==1:
        return 1
    else:
        return 2*(myfunc(n-1)+1)

a = myfunc(10)
print(a)

1534

2、杨辉三角形

问题描述：

打印杨辉三角形

算法设计：

杨辉三角形中的数正好是（x+y）的N次幂的展开式各项系数。

第x行有x个值

对于第x行的第y（y>=3）个值，有当y=1或y=x时，其值为1，剩下的值为第x-1行的第y-1个值和第y个值的和

$c(x,y)=\left\{\begin{matrix} 1\\c(x-1,y-1)+c(x-1,y) \end{matrix}\right.$

代码实现：

def myfunc(x,y):
    if y==1 or y==x:
        return 1
    else:
        z = myfunc(x-1,y-1)+myfunc(x-1,y)
        return z

n = int(input("请输入杨辉三角形的行数："))
for i in range(1,n+1):
    for j in range(1,i+1):
        print(myfunc(i,j),end=" ")
    print()
    

请输入杨辉三角形的行数：10
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1

3、年龄问题

问题描述：

有5个人坐在一起，问第 5 个人多少岁，他说比第 4 个人大 2 岁，问第 4 个人，他说比第 3 个人大两岁，依次类推，第一个人是10岁，问第五个人多少岁

代码实现：

def myfunc(n):
    if n==1:
        return 10
    else:
        z = myfunc(n-1)+2
        return z

n = int(input("共有人数："))
print(myfunc(n))

共有人数：5
18

4、分🐟问题

问题描述：

A,B,C,D,E 5个人合伙捕鱼，A将🐟平分5份，把多余的一条扔回河中，B将剩下的🐟平分5份，再将多余的一条仍会河中，然后依次同样的方法，问每个人醒来看到的是多少条鱼。

算法设计：

由于每个人都是将🐟5等份再扔掉一条，因此每一次分的🐟都是 (x-1)/5，那么剩下的就是 4(x-1)/5，而对于这两个数都是整数

fish[1] = 全部的🐟

fish[2] = 4 * (fish[1]-1) // 5

fish[3] = 4 * (fish[2]-1) // 5

…

即fish[n] = 4*(fish[n-1]-1) // 5

代码实现：

def fish(n,z):
    if (z-1)%5==0:
        if n==1:
            return 1
        else:
            return fish(n-1,(z-1)/5*4)
    return 0
i = 0
while True:
    i+=1
    x=i*5+1
    if (fish(5,x)):
        print(x)
        break

3121

5、逆序输出数字

问题描述：

编程实现输入的数字逆序输出

代码设计：

def reverse(n):
    if n!=0:
        print(n%10,end='')
        reverse(n//10)
num = int(input("请输入一个整数： "))
reverse(num)

请输入一个整数： 123456789
987654321

6、逆序输出字符串

代码设计：

def rvstr(s):
    if len(s)<=1:
        return s
    else:
        return rvstr(s[1:]) +s[0]    #切片

str = str(input("请输入字符串： "))
print(rvstr(str))


请输入字符串： abcdefg
gfedcba

7、汉诺塔

问题描述：

代码设计：

def hanoi(n, x, y, z):
    if n == 1:
        print(x, '-->', z)  # 如果只有 1 层，直接将金片从 x 移动到 z
    else:
        hanoi(n-1, x, z, y) # 将 x 上的 n-1 个金片移动到 y
        print(x, '-->', z)  # 将最底下的金片从 x 移动到 z
        hanoi(n-1, y, x, z) # 将 y 上的 n-1 个金片移动到 z
    
n = int(input('请输入汉诺塔的层数：'))
hanoi(n, 'A', 'B', 'C')