python - 使递归函数迭代？

当我运行以下模块时，它将运行约960次递归：

import matplotlib
import pylab

xStart = 1
debug = 'off'
xList = []
calcList = []

def collatzCalc(xStart,calcs):
    calc = 0
    xCalc = 0
    xCalc = xStart
    while xCalc > 0:
        if debug == 'on':
            print(round(xCalc))
            print(xList)
            print(calcList)

        if xCalc == 1:
            xList.append(xStart)
            calcList.append(calc)
            xStart += 1
            if debug == 'on':
                print(calcs)
                print('---------------------------')

            calcs += 1
            collatzCalc(xStart,calcs)
        else:
            if xCalc % 2 == 0:
                xCalc = xCalc / 2
                calc += 1
            else:
                xCalc = xCalc * 3 + 1
                calc += 1

calcs = 0
collatzCalc(xStart,calcs)

它引发以下错误：

Traceback (most recent call last):
  File "C:\Users\Erin Lynch\Desktop\collatzConjecture.py", line 49, in <module>
    collatzCalc(xStart,calcs)
File "C:\Users\Erin Lynch\Desktop\collatzConjecture.py", line 32, in collatzCalc
    collatzCalc(xStart,calcs)
  File "C:\Users\Erin Lynch\Desktop\collatzConjecture.py", line 14, in collatzCalc
    while xCalc > 0:
RuntimeError: maximum recursion depth exceeded in comparison

我知道为什么会这样，因为我今天阅读了有关递归限制的信息，但是我想知道的是如何将递归公式转换为迭代公式。我完全不知道该怎么做，我需要知道如何做的人的帮助。

最佳答案

首先，在这一部分中，第一行是不必要的，因为xCalc将立即被xStart覆盖：

    xCalc = 0
    xCalc = xStart

其次，如果仔细观察代码，就会发现如果xCalc到达1，它将永远循环下去：

def collatzCalc(xStart,calcs):
    ...
    xCalc = xStart
    while xCalc > 0:
        ...
        if xCalc == 1:
            ...
            collatzCalc(xStart,calcs)
        else:
            ...

由于xCalc是局部变量，因此collatzCalc的其他实例无法修改此变量。该功能将永远保持循环。尽管由于正在检查Collatz猜想而使永远在“最外层”函数中循环是有意义的，但递归地进行操作却没有意义。

我认为这是因为您混淆了该程序的两个不同部分：

您要检查每个自然数的Collatz猜想。
您要计算Collatz序列。

让我们解决第一个问题，因为它更容易。要检查Collatz猜想，您只需要一个简单的循环：

def checkCollatz(xStart=1, debug=False):
    xList = []
    calcList = []
    while True:
        calc = collatzCalc(xStart, debug=debug)
        xList.append(xStart)
        calcList.append(calc)
        if debug:
            print(xStart - 1)
            print('---------------------------')
        xStart += 1

在这里，我已将全局变量（xList，calcList，xStart和debug）转换为此最外层函数的局部变量。（您可能还希望为其选择更多的描述性名称。）请注意，我已完全删除了calcs变量，因为它似乎与xStart相同，但总是低一。

现在，要计算Collatz序列，我可以重用您已经拥有的序列（剥离checkCollatz中使用的部分）：

def collatzCalc(xCalc, debug=False):
    calc = 0
    while xCalc > 0:
        if debug:
            print(xCalc)
        if xCalc == 1:
            return calc
        else:
            if xCalc % 2 == 0:
                xCalc = xCalc // 2
            else:
                xCalc = xCalc * 3 + 1
            calc += 1

由于Collatz序列始终是整数，因此不需要使用round。另外，应该使用整数除法（//）而不是浮点除法（/），因为/会将您的数字强制为浮点数。

请注意，此代码中根本没有递归。递归已被消除，并转换为checkCollatz中的循环（注意，现在有两个while循环而不是一个）。您的原始代码已经大体上是迭代的，因此将其转换为递归代码并不十分复杂。

作为附带说明，请注意，通过将函数分成两个单独的函数，现在变量变少了很多，代码更易于阅读。

关于python - 使递归函数迭代？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27586744/