时间戳

首页 > 解决方案 > Python计算递归调用的迭代次数

python - Python计算递归调用的迭代次数

问题描述

我试图计算 collat​​z_chain() 函数被递归调用的次数。特别是，下面的代码似乎在最后（在递归调用之外）将 count 变量设置为 1，即使它在递归函数内部正确递增。

def collatz_longest_chain(limit):
    iter = 1
    while(iter < limit):
        count = 0
        _next_num, count = collatz_chain(iter, count)
        iter += 1

    print('----')
    return count

def collatz_chain(n, count):
    if n == 1:
        count += 1
        print("n=1" + " count: " + str(count) + " | inside n == 1")
        return 1, count
    elif n % 2 == 0:
        count += 1
        print("n: " + str(n) + " count: " + str(count) + " | inside n % 2 == 0")
        return collatz_chain(n/2, count), count
    else:
        count += 1
        print("n: " + str(n) + " count: " + str(count) + " | inside 3*n + 1")
        return collatz_chain(3*n + 1, count), count

print(collatz_longest_chain(10))

输出是：

...
n: 9 count: 1 | inside 3*n + 1
n: 28 count: 2 | inside n % 2 == 0
n: 14.0 count: 3 | inside n % 2 == 0
n: 7.0 count: 4 | inside 3*n + 1
n: 22.0 count: 5 | inside n % 2 == 0
n: 11.0 count: 6 | inside 3*n + 1
n: 34.0 count: 7 | inside n % 2 == 0
n: 17.0 count: 8 | inside 3*n + 1
n: 52.0 count: 9 | inside n % 2 == 0
n: 26.0 count: 10 | inside n % 2 == 0
n: 13.0 count: 11 | inside 3*n + 1
n: 40.0 count: 12 | inside n % 2 == 0
n: 20.0 count: 13 | inside n % 2 == 0
n: 10.0 count: 14 | inside n % 2 == 0
n: 5.0 count: 15 | inside 3*n + 1
n: 16.0 count: 16 | inside n % 2 == 0
n: 8.0 count: 17 | inside n % 2 == 0
n: 4.0 count: 18 | inside n % 2 == 0
n: 2.0 count: 19 | inside n % 2 == 0
n=1 count: 20 | inside n == 1
----
1

如何从递归调用中传递正确的计数变量值，以便输出为：

...
n=1 count: 20 | inside n == 1
----
20

标签： pythonpython-3.xalgorithmrecursion

解决方案

在您的基本情况下，您将返回一个元组和计数：

return 1, count

但是在递归调用中，您将返回递归的结果（这是一个元组）和计数

return collatz_chain(3*n + 1, count), count
# collatz_chain already returns the count

所以你最终会在_next_num. 如果要返回最终计数，则需要从递归调用中返回与基本情况相同形状的值，例如：

def collatz_chain(n, count):
    count += 1
    if n == 1:
        print("n=1" + " count: " + str(count) + " | inside n == 1")
        return 1, count
    elif n % 2 == 0:
        print("n: " + str(n) + " count: " + str(count) + " | inside n % 2 == 0")
        return collatz_chain(n/2, count)
    else:
        print("n: " + str(n) + " count: " + str(count) + " | inside 3*n + 1")
        return collatz_chain(3*n + 1, count)

这将打印：

n: 20.0 count: 13 | inside n % 2 == 0
n: 10.0 count: 14 | inside n % 2 == 0
n: 5.0 count: 15 | inside 3*n + 1
n: 16.0 count: 16 | inside n % 2 == 0
n: 8.0 count: 17 | inside n % 2 == 0
n: 4.0 count: 18 | inside n % 2 == 0
n: 2.0 count: 19 | inside n % 2 == 0
n=1 count: 20 | inside n == 1
----
20

但是，请注意，这不是对collatz_chain(). 它是循环最后一次调用中的递归调用次数while。

如果您想要总计数，则需要使用上述更改，然后从 while 循环中获取所有调用的总数。就像是：

def collatz_longest_chain(limit):
    iter = 1
    total_count = 0
    while(iter < limit):
        count = 0
        print("calling iter: ", iter, count)
        _next_num, count = collatz_chain(iter, count)
        iter += 1
        total_count += count

    print('----')
    return count, total_count

另一个注意事项：iter是 Python 中的内置函数，因此您可能不应该将其用作变量名。它会覆盖内置的。

推荐阅读