一，认识递归函数
1，什么是递归?
递归的工作原理是，如果函数需要处理的问题大小合适，则直接求解并返回结果，
否则将问题分解成两个或多个更小的子问题，并对子问题进行相同的处理，
直到问题无法分解为止
2,什么是递归函数:
递归函数（recursive function）是指在函数体中可以调用自己的函数
3,语法
def fn():
# ...
if condition:
# 停止自我调用
else:
fn()
# ...4,递归函数的优点和缺点
递归函数的优点:它们可以帮助程序员在处理复杂问题时提供一种简单且易懂的解决方案。
递归函数使代码具有可读性和可重用性，
而且可以使用递归函数解决使用其他方法难以处理的问题。
递归函数的缺点: 递归函数可能会在运行时占用较多的系统资源，
因为它们需要在堆栈上存储多个函数调用
其次，递归函数可能导致代码变得不容易理解，
因为它具有一定的复杂度
说明：刘宏缔的架构森林—专注it技术的博客，
网址：https://imgtouch.com
本文: https://blog.imgtouch.com/index.php/2024/03/24/python-suan-fa-gong-jiao-che-wen-ti/
代码: https://github.com/liuhongdi/ 或 https://gitee.com/liuhongdi
说明：作者:刘宏缔 邮箱: [email protected]
二，公交车题目与解析
1,题目:
某路公共汽车，总共有八站，
从一号站发轩时车上已有n位乘客，
到了第二站先下一半乘客，再上来了六位乘客；
到了第三站也先下一半乘客，再上来了五位乘客，
以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，
到了终点站车上还有乘客六人，
问发车时车上的乘客有多少？
2,解析
思路：
到终点站第8站时，车上还有6位乘客
1号站发车时，车上是n位
2号站时，设车上乘客数量是f(x):
f(x)-f(x)*1/2+6 = f(x+1)
3号站时, 设车上乘客数量是f(x):
f(x)-f(x)*1/2+5 = f(x+1)
…
以此类推，可以得到离开第x站时
f(x)*1/2+(8-x) = f(x+1)
得到到达某站时人数和离开某站时人数的关系
f(x) = (f(x+1)-(8-x))*2
根据以上我们得到方程式:
三，编写代码:
1,递归函数解决
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# 递归函数，返回刚到第几站时(还没有上下车之前时)的乘客人数
# i: 到第几站时
def num(i):
if i == 8: # 到终点站第8站时的人数
return 6
elif i == 1: # 第一站没有下车，到第二站时的人数就是从第一站发车时的人数
return 0
else: # 根据方程式从到下一站人数，返回到本站时的人数
return (num(i + 1) - 8 + i) * 2
i = eval(input("请输入第几站:"))
person1 = num(i)
print(f"到达第{i}站时共{person1}乘客")
|
运行结果:
请输入第几站:2
到达第2站时共144乘客2,for循环
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# 函数，返回刚到第几站时(还没有上下车之前时)的乘客人数
# i: 到第几站时
def num(i):
if i <= 1: # 第一站没有下车，到第二站时的人数就是从第一站发车时的人数
i = 2
person = 6 # 初始化乘客人数,到第八i站时共6个人
for k in range(7, i-1, -1): # 循环，从到第7站时上溯到第i站时
person = (person - 8 + k) * 2
person1 = int(person)
print(f"到达第{i}站时共{person1}乘客")
i = eval(input("请输入第几站:"))
num(i)
|
运行结果:
请输入第几站:2
到达第2站时共144乘客