Python递归函数详解：小球落地高度与路程计算

问题描述

假设一个小球从100米的高度自由落下，每次落地后反弹回原高度的一半。请计算第10次弹起时的高度，以及小球在运动过程中经过的总路程。

递归函数的基本概念

函数的递归调用是函数嵌套调用的一种特殊形式。在调用一个函数的过程中，如果又直接或者间接地调用了该函数本身，这种调用方式被称为函数的递归调用。

需要注意的是，无限递归导致的死循环是没有实际意义的，程序会因栈溢出而崩溃。

有效的递归调用必须包含两个明确的阶段：

第一阶段为回溯：即不断进行递归调用，这本质上是一个重复的过程。

• 但在回溯过程中，每一次重复的问题规模必须有所减少，
• 直到逼近一个最终的基础结果。因此，回溯阶段必须设定一个明确的结束条件（基准情况）。

第二阶段为递推：在满足结束条件后，结果从最深层开始，一层一层地向回推算，最终得出初始调用的结果。

递归示例：年龄计算

假设共有5个人，第五个人的年龄比第四个人大2岁，依此类推，直到第一个人。

'''
age(5) = age(4) + 2
age(4) = age(3) + 2
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 18
'''

我们可以将第n个人的年龄定义为一个数学公式：

age(n) = age(n-1) + 2     # n>1
age(n) = 18               # n=1

基于此逻辑，只需创建相应的函数，将上述两个阶段的逻辑写入，即可完成递归函数的构建：

def age(n):
    if n == 1:
        return 18
    if n > 1:
        return age(n-1) + 2
print(age(5))

小球落地问题的解题思路

在解决此问题时，需要特别注意以下三个关键点：

第一，小球从100米高度落下，因此在第一次弹起的过程中，它已经行走了100米的距离。

第二，小球最后一次弹起后并没有再次下落，因此计算总路程时需排除最后一次下落的路程。

第三，每次弹起的高度乘以2才是该次弹起所对应的往返距离（上升+下落，最后一次除外）。

far = [100]
def jump(n):     
    if n == 1:
        far.append(100)
        return 50
    else:
        b = jump(n-1) / 2
        far.append(b*2)    
        return b
print(jump(10))
print(far)
print(sum(far)-jump(10))

Python递归函数代码实现

以下是具体的Python代码实现：

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
print([fibonacci(x) for x in range(10)])

运行结果截图如下：

补充说明与注意事项

【1】递归函数必须包含终止条件，否则会导致无限递归。

【2】递归的每次调用规模必须比上一次更小，以确保能最终到达基准情况。

【3】递归的效率通常较低。通过程序调试可以看出，进入递归时层层深入，退出时层层返回，这会导致存储空间占用较大。在实际应用中，需权衡代码可读性与执行效率。

以上为个人经验分享，希望能给大家提供一个参考，也希望大家多多支持本站。