python - 使递归函数迭代？

Question

当我运行以下模块时，它运行了大约 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

我知道为什么会发生这种情况，因为我今天读到了有关递归限制的内容，但我想知道的是如何将递归公式变成迭代公式。我完全不知道如何做到这一点，我需要知道如何做的人的帮助。

Answer 1

首先，在这部分中，第一行是不必要的，因为 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是一个局部变量，collat​​zCalc的其他实例无法修改该变量。该函数将永远循环下去。虽然在检查 Collat​​z 猜想时在“最外层”函数中永远循环是有意义的，但递归地执行它是没有意义的。

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

1. 您想要检查每个自然数的 Collat​​z 猜想。
2. 您想要计算 Collat​​z 序列。

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

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 相同，除了始终低于减一。

现在，为了计算 Collat​​z 序列，我可以重用您已有的内容(去掉 checkCollat​​z 中使用的部分):

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

没有必要使用round，因为 Collat​​z 序列始终是整数。此外，应该使用整数除法 (//) 而不是浮点除法 (/)，因为 / 会将您的数字强制转换为 float -点数。

请注意，这段代码中根本没有递归。递归已被消除并转换为 checkCollat​​z 中的循环(请注意，现在有两个 while 循环，而不是一个)。您的原始代码已经大部分是迭代的，因此将其转换为递归代码并不是很复杂。

顺便说一句，请注意，通过将函数拆分为两个单独的函数，现在变量少了很多，代码也更容易阅读。