时间戳

首页 > 解决方案 > 递归几何序列

python - 递归几何序列

问题描述

我无法让我的代码正常工作。我需要写一个递归函数

geometric_recursive

公式是在此处输入图像描述

我的问题是我无法停止循环。此外，该函数应具有与迭代版本相同的参数

def geometric(n: int) -> float:
'''
Calculates a finite geometric series with q=0.5 as the base. 
'''
result = 0

for k in range(0, n+1):
    result += 0.5**k

我的代码是

    def geometric_recursive(k : int) -> float:
if k <= 0:
    return 1
else:
    return 0.5 ** geometric_recursive(k+1)

目标是断言应该通过

assert geometric_recursive(2) == geometric(2)

我希望有一个人可以帮助我

标签： pythonfunctionrecursionsequence

解决方案

首先让我们从数学的角度来看这个公式：SUM[0<=i<n](q**i) is (1 - q**n) / (1 - q)。所以对于q=0.5预期的结果是2。

并且数学证明我们可以计算它提供q < 1。

常见的方法是定义一个限制epsilon 并在q**n < epsilon. 我们知道这个数字将大于 1，并且 Python 浮点数的精度接近 15 位十进制数字（尾数为 48 位）

所以我们可以写：

def g_recurs(q, term=1, tot=0):
    # print(q, term, tot)  # uncomment for intermediate results
    tot += term
    term *= q
    if term < 1E-16:       # stop recursion when q**n < 1E-16
        return tot
    else:
        return g_recurs(q, term, tot)

它按预期给出：

>>> g_recurs(0.5)
2.0

编辑后，您只想计算特定数量的术语，并且q固定在0.5. 公式将变为：

 def g_recurs(n: int, term=1, tot=0) -> float:
    # print(q, term, tot)  # uncomment for intermediate results
    tot += term
    term *= 0.5
    if n == 0:
        return tot
    else:
        return g_recurs(n-1, term, tot)

它给出了期望值：

>>> g_recurs(2)
1.75

上面的公式避免了求幂，因为乘法要简单得多，但我现在认为您只是在寻找：

def geometric_recursive(n:int) -> float:
    if n == 0:
        return 1
    term = 0.5 ** n
    return term + geometric_recursive(n-1)

这也验证了：

>>> geometric_recursive(2)
1.75

推荐阅读