使递归函数迭代?

2024-03-29 12:38:21 发布

您现在位置: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

我知道为什么会这样,因为我今天读了关于递归限制的文章,但我想知道的是如何将递归公式转化为迭代公式。我完全不知道怎么做,我需要一个知道怎么做的人的帮助。你知道吗


Tags: indebugifcalcusersfileprinterin
1条回答
网友
1楼 · 发布于 2024-03-29 12:38:21

首先,在本部分中,第一行是不必要的,因为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猜想,但是递归地执行它是没有意义的。你知道吗

我认为这是因为你混淆了这个项目的两个不同部分:

  1. 你要检查每个自然数的Collatz猜想。你知道吗
  2. 你要计算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

在这里,我将全局变量(xListcalcListxStartdebug)转换为这个最外层函数的局部变量。(您可能还想为它们选择更具描述性的名称。)请注意,我已经完全消除了calcs变量,因为它似乎与xStart相同,只是总是低1。你知道吗

现在,为了计算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循环而不是一个)。您的原始代码已经基本上是迭代的,所以将其转换为递归代码并不是很复杂。你知道吗

另请注意,通过将函数拆分为两个单独的函数,现在的变量要少得多,代码更易于阅读。你知道吗

相关问题 更多 >