使用递归近似这个方程 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 1

print(4 * calculateFraction(10))

编辑

奥利维尔的回答非常好，我希望我可以多次投票。

鉴于此，我认为 OP 可能会从上述方法的二进制实现中受益。也就是说，每当递归时，将问题的一半发送到一个分支，另一半发送到另一个分支。 （这意味着，例如，要求 num=15 将导致深度为 4 而不是深度为 16。）

import inspect

def 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 result

print('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 it

print(calculateFrac(10)) # 0.7604599047323508

从那里，上面的代码非常好。

不要使用递归

不过，请注意，无限级数最好用 asum和 a表示，而generator不是递归。特别是在没有优化尾递归的Python 中。

递归解决方案会更慢，使用更多内存并最终达到最大递归深度。

from itertools import islice, count

def seq():

    for n in count():

        yield (-1) ** n / (2 * n + 1)

print(sum(islice(seq(), 0, 10))) # 0.7604599047323508

递归练习

看来您想学习使用递归。因此，重要的是您还可以识别不需要高效递归的问题。

递归通常更适合在每次迭代中出现分支的问题。也就是说形式的问题F（N）= F（N ₁）+ F（N ₂），其中Ñ ₁和Ñ ₂是子集Ñ。一个常见的例子是合并排序。

您可以在网上找到许多针对此类问题的问题集。

Answer 3

我在问如何使用递归解决这个问题。

我不同意@OlivierMelançon 关于这是一个糟糕的递归示例。我只提供了可怕的递归解决方案的一种可能实现：

def calculateFrac(num):

    if num < 1:

        return 0.0

    return calculateFrac(num - 1) + (2 * (num % 2) - 1) / (2 * num - 1)

print(calculateFrac(10))  # 0.7604599047323508 (put in the 4 *)

在我的系统上，它可以处理的最大参数是 997，而无需通过sys.setrecursionlimit(). 使用记忆技术无济于事。我们可能可以通过执行以下操作来制定尾递归解决方案：

def calculateFrac(num, sum=0.0):

    if num < 1:

        return sum

    return calculateFrac(num - 1, sum + (2 * (num % 2) - 1) / (2 * num - 1))

print(calculateFrac(10))  # 0.7604599047323506 (put in the 4 *)

并不是说 Python 关心这些事情。但是，如果它确实进行了尾调用优化，那么此类解决方案可能与迭代解决方案一样快，并且没有任何堆栈限制。