这个递归函数如何跟踪它执行了多少次？

Question

Project Euler问题14给出以下问题：

为正整数集定义以下迭代序列：

n→n/2（n为偶数）
n→3n 1（n为奇数）

使用上述规则，从13开始，我们生成以下序列：

13→ 40→ 20→ 10→ 5.→ 16→ 8.→ 4.→ 2.→ 1.

可以看出，该序列（从13开始，到1结束）包含10个术语。虽然这还没有被证明（科拉兹问题），但人们认为所有的起始数字都以1结束。

100万以下的哪个起始数字产生的链条最长？

我发现了这个递归函数，它计算给定数字的Collatz链的长度。数学逻辑非常简单且易于理解。然而，我不明白该函数如何跟踪链的长度。

代码如下：

def find_collatz_chain_length(x):
    if x == 1:
        print('here')
        return 1
    if x % 2 == 0:
        y = x // 2
        print(y)
    else:
        y = x * 3 + 1
        print(y)
    return find_collatz_chain_length(y) + 1

我添加了print语句以在执行时遵循逻辑。例如：

print(find_collatz_chain_length(13))

然后我得到以下输出：

40 
20
10
5
16
8
4
2
1
here
10

这（对我来说）是有意义的，直到它返回链的长度（10）。我知道这与最终返回语句中的1有关，因为更改此结果会导致错误的长度。如果有人能向我解释该函数如何在没有列表或计数器的情况下跟踪长度，那就太好了。

Answer 1

让我们用返回值替换函数调用。我们从

find_collatz_chain_length(13)

那会回来的

find_collatz_chain_length(40) + 1

查看函数调用，它会返回find_collatz_chain_length（20）1，但是我们已经有了第一次调用函数时的1：

(find_collatz_chain_length(20) + 1) + 1

该函数调用返回find\u collatz\u chain\u length（10）1：

(((find_collatz_chain_length(10) + 1) + 1) + 1)

每次调用函数时，它都会添加一个1，直到函数的输入为1，此时它停止调用自己，只返回1。您最终会得到类似的东西

(((((1) + 1) + 1) + 1) ... + 1)

每次调用函数时，都有一个1。把它们加起来，你就得到了你的链条长度。