如何跟踪其中包含 return 函数的递归函数

Question

我正在尝试跟踪这个递归函数，但我尝试了我通常做的事情，但它并没有像你 return 你需要向它添加一些东西的函数那样工作。有人可以向我解释并让我更好地理解如何在下面的代码中使用 table（或任何其他方法）来跟踪这样的函数：

def NumberPatern(Value1,Value2,EndValue):
    print(Value1)
    if Value1<= EndValue:
        temp = Value2
        Value2 = Value1
        Value1 = Value1 + temp

       
        return NumberPatern(Value1,Value2,EndValue)+1
    else:
        return 0

将其用作函数的输入

NumberPatern(1,1,12)

我也得到这个table来跟踪函数：

Answer 1

将函数的结果赋给一个变量。然后你可以在返回之前打印 table 的所有列。

def NumberPatern(Value1,Value2,EndValue):
    if Value1<= EndValue:
        temp = Value2
        Value2 = Value1
        Value1 = Value1 + temp

        output = NumberPatern(Value1,Value2,EndValue)+1
    else:
        temp = 'N/A'
        output = 0

    print(Value1, Value2, temp, EndValue, output)
    return output

Answer 2

假装你是电脑，逐行解释这个函数。

每次调用该函数时，在 table.

中的新行中记录调用它的“Value1”、“Value2”和“EndValue”

每次分配 temp 时填写“温度”列。

只要程序产生输出（即调用 print().

，就填写“输出”列

当你击中return语句时，填写“RETURN”栏，并提高一个级别。

例如：

第一步：第一次调用函数

Value1	Value2	Temp	EndValue	OUTPUT	RETURN value
1	1		12

第 2 步：遍历函数直到我们遇到递归条件，边走边填写数据：

Value1	Value2	Temp	EndValue	OUTPUT	RETURN value
1	1	1	12	1

第 3 步：由于函数已被再次递归调用，因此将调用它的参数添加到 table：

Value1	Value2	Temp	EndValue	OUTPUT	RETURN value
1	1	1	12	1
2	1		12

第 4 步：重复以下两个步骤，直到找到基本情况第 5 步：当您遇到基本情况时，填写 returned 值（因为基本情况中从未分配 temp，因此将其留空）

Value1	Value2	Temp	EndValue	OUTPUT	RETURN value
1	1	1	12	1
2	1	1	12	2
3	2	2	12	3
5	3	3	12	5
8	5	5	12	8
13	8		12	13	0

第 13 步：现在从您所在的位置返回链，并填写现在计算的 return 值：

Value1	Value2	Temp	EndValue	OUTPUT	RETURN value
1	1	1	12	1	5
2	1	1	12	2	4
3	2	2	12	3	3
5	3	3	12	5	2
8	5	5	12	8	1
13	8		12	13	0

这就是完成的table。

Answer 3

代数

现在是回顾代数学习的好时机

def NumberPatern(Value1,Value2,EndValue):
    print(Value1)
    if Value1<= EndValue:
        temp = Value2
        Value2 = Value1
        Value1 = Value1 + temp

        # focus here
        return NumberPatern(Value1,Value2,EndValue)+1
    else:
        return 0

这个问题的挑战性部分是 Value1 和 Value2 正在重新分配。但是我们可以用一种不那么令人困惑的方式重写它。

首先将Value1替换为它的值-

temp = Value2
值 2 = 值 1
# 值 1 = 值 1 + 温度
return NumberPattern(<b>Value1 + temp</b>,Value2,EndValue)+1

现在将 Value2 替换为其值 -

temp = Value2
# 值 2 = 值 1
# 值 1 = 值 1 + 温度
return NumberPattern(Value1 + temp,<b>Value1</b>,EndValue)+1

最后用它的值替换temp -

#temp = Value2
# 值 2 = 值 1
# 值 1 = 值 1 + 温度
return NumberPattern(Value1 + <b>Value2</b>,Value1,EndValue)+1

现在让我们看看修改后的程序。我们将在每一步打印 each Value1、Value2 和 EndValue -

def NumberPatern(Value1,Value2,EndValue):
    print(f"v1:{Value1} v2:{Value2} end:{EndValue}")
    if Value1 <= EndValue:
        # temp = Value2
        # Value2 = Value1
        # Value1 = Value1 + temp
        return NumberPatern(<b>Value1 + Value2,Value1,EndValue</b>)+1
    else:
        return 0

print(NumberPatern(1,1,12))

v1:1 v2:1 end:12
v1:2 v2:1 end:12
v1:3 v2:2 end:12
v1:5 v2:3 end:12
v1:8 v2:5 end:12
v1:13 v2:8 end:12
5                     # <- final answer

这可能不是您的家庭作业要求的确切输出，但希望它能向您展示递归函数中使用的变量重新分配所引起的麻烦。输出与删除重复值后的 Green 答案相同。

跟踪装饰器

在我刚刚写的中，我创建了一个简单的 @trace 装饰器，可以与任何函数一起使用。这个装饰器允许我们可视化复杂函数的评估 -

from functools import wraps

def trace(f):
  frame = 0
  @wraps(f)
  def wrapper(*args):
    nonlocal frame
    space = " "*2*frame
    argstring = ", ".join(map(str, args))
    print(f"{space}-> [frame:{frame}] {f.__name__}({argstring})")
    frame = frame + 1
    result = f(*args)
    frame = frame - 1
    print(f"{space}<- [frame:{frame}]", result)
    return result
  return wrapper

我们可以将它与您的 NumberPatern 函数一起使用，只需在上面的行中写入 @trace 即可。请注意，我还注释掉了您的内部 print 语句 -

@trace
def NumberPatern(Value1,Value2,EndValue):
    # print(Value1)                         # <-
    if Value1<= EndValue:
        temp = Value2
        Value2 = Value1
        Value1 = Value1 + temp
        return NumberPatern(Value1,Value2,EndValue)+1
    else:
        return 0

现在当我们运行函数时，我们可以看到“跟踪”输出 -

print(NumberPatern(1,1,12))

-> [frame:0] NumberPatern(1, 1, 12)
  -> [frame:1] NumberPatern(2, 1, 12)
    -> [frame:2] NumberPatern(3, 2, 12)
      -> [frame:3] NumberPatern(5, 3, 12)
        -> [frame:4] NumberPatern(8, 5, 12)
          -> [frame:5] NumberPatern(13, 8, 12)
          <- [frame:5] 0
        <- [frame:4] 1
      <- [frame:3] 2
    <- [frame:2] 3
  <- [frame:1] 4
<- [frame:0] 5
5

如何跟踪其中包含 return 函数的递归函数

How do I trace a recursive function with a return function in it

python

recursion

trace

function

subroutine