使用递归近似这个方程 4 * (1 - (1 /3 ) + (1 / 5) - (1 / 7)

Question

我将如何使用递归来近似以下等式？这是一种迭代方法：

def calculateFrac(num):

    result = 0

    for i in range(num):

        if i % 2 == 0:

            result = result + 1 / (2 * i + 1)

        else:

            result = result - 1 / (2 * i + 1)

        print(4 * result)

print(calculateFrac(10))

Answer 1

def calculateFraction(num):  if (num > 0):    return (-1)**(num) * 1/(num*2+1) + calculateFraction(num-1)  else:    return 1print(4 * calculateFraction(10))编辑奥利维尔的回答非常好，我希望我可以多次投票。鉴于此，我认为 OP 可能会从上述方法的二进制实现中受益。也就是说，每当递归时，将问题的一半发送到一个分支，另一半发送到另一个分支。 （这意味着，例如，要求 num=15 将导致深度为 4 而不是深度为 16。）import inspectdef calculateFraction(num, end=0):    result = 0    depth = 'Depth({:d}){:s}>'.format(len(inspect.stack())-1, '='*(len(inspect.stack())-1)*2)    # If there are an odd number of parts to calculate, do the highest one now    if (((num-end+1)&1) == 1):        result += ((-1)**(num)) / (num*2+1)        print('{:s} Fraction part {:d} = {:f}'.format(depth, num, result))        num-=1    # If there are still any parts to calculate, do them recursively    # (There must be an even number, as we did the odd one previously)    # (That may leave 0 still to do, in which case the recursion is skipped)    if (num > end):        mid = ((num-end)>>1) + end        # Do the upper half of the remaining parts        print('{:s} Recursing to {:d},{:d}'.format(depth, num, mid+1))        result += calculateFraction(num, mid+1)        # Do the lower half of the remaining parts        print('{:s} Recursing to {:d},{:d}'.format(depth, mid, end))        result += calculateFraction(mid, end)    return resultprint('Result: {:f}'.format(4*calculateFraction(10)))

Answer 2

首先，您也没有返回结果。这是您的代码的固定版本。def calculateFrac(num):    result = 0    for i in range(num):        if i % 2 == 0:            result = result + 1 / (2 * i + 1)        else:            result = result - 1 / (2 * i + 1)    return result # return the result instead of printing itprint(calculateFrac(10)) # 0.7604599047323508从那里，上面的代码非常好。不要使用递归不过，请注意，无限级数最好用 asum和 a表示，而generator不是递归。特别是在没有优化尾递归的Python 中。递归解决方案会更慢，使用更多内存并最终达到最大递归深度。from itertools import islice, countdef seq():    for n in count():        yield (-1) ** n / (2 * n + 1)print(sum(islice(seq(), 0, 10))) # 0.7604599047323508递归练习看来您想学习使用递归。因此，重要的是您还可以识别不需要高效递归的问题。递归通常更适合在每次迭代中出现分支的问题。也就是说形式的问题F（N）= F（N 1）+ F（N 2），其中Ñ 1和Ñ 2是子集Ñ。一个常见的例子是合并排序。您可以在网上找到许多针对此类问题的问题集。

Answer 3

我在问如何使用递归解决这个问题。我不同意@OlivierMelançon 关于这是一个糟糕的递归示例。我只提供了可怕的递归解决方案的一种可能实现：def calculateFrac(num):&nbsp; &nbsp; if num < 1:&nbsp; &nbsp; &nbsp; &nbsp; return 0.0&nbsp; &nbsp; return calculateFrac(num - 1) + (2 * (num % 2) - 1) / (2 * num - 1)print(calculateFrac(10))&nbsp; # 0.7604599047323508 (put in the 4 *)在我的系统上，它可以处理的最大参数是 997，而无需通过sys.setrecursionlimit(). 使用记忆技术无济于事。我们可能可以通过执行以下操作来制定尾递归解决方案：def calculateFrac(num, sum=0.0):&nbsp; &nbsp; if num < 1:&nbsp; &nbsp; &nbsp; &nbsp; return sum&nbsp; &nbsp; return calculateFrac(num - 1, sum + (2 * (num % 2) - 1) / (2 * num - 1))print(calculateFrac(10))&nbsp; # 0.7604599047323506 (put in the 4 *)并不是说 Python 关心这些事情。但是，如果它确实进行了尾调用优化，那么此类解决方案可能与迭代解决方案一样快，并且没有任何堆栈限制。