递归几何序列

Question

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

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)

希望有人能帮助我

Answer 1

仅仅因为你每次都给出参数 k+1 ，所以基本上 i 永远不会 <= 0 ，所以这意味着你的函数将一次又一次地调用自己

Answer 2

递归需要一个基本案例。您有 none（或 none 会命中）。公式趋于无穷大，但这不切实际。您需要弄清楚何时足够接近答案才能停止。这可以是迭代次数（Python 的最大递归深度是一个上限）或精度级别。

此外，函数似乎并不代表公式。该公式看起来像 q^k 的总和，其中 q ^ (q ^ (q ^ (q ^ ...)))。没有求和发生。

Answer 3

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

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

通常的方法是定义一个 limit 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

递归几何序列

recursive geometric sequence

python

recursion

function

sequence