Python递归仅在必要时评估

Question

假设我有这两个功能:

def s(x,y,z):
   if x <= 0:
       return y
   return z

def f(a,b):
    return s(b, a+1, f(a,b-1)+1)

如果我尝试在脑海中找到 f(5,2)，它会是这样的:

f(5,2) = s(2,6,f(5,1)+1)
f(5,1) = s(1,6,f(5,0)+1)
f(5,0) = s(0,6,f(5,-1)+1) = 6
f(5,1) = 7
f(5,2) = 8

我从不评估 f(5,-1) 因为不需要它。 s 函数将返回 6，因为参数 x 为零，因此不需要对参数 z 求值。

但是，如果我尝试在 python 中运行它，它将永远递归或直到我得到最大递归深度错误，大概是因为 python 想要在执行 s 之前评估所有参数> 功能。

我的问题是，我将如何着手实现这些功能或任何类似的场景，以便在不再需要递归时停止递归？是否可以延迟对每个参数的评估，直到在函数中使用它？

Answer 1

您的大脑正在使用关于如何 s() 的“内幕知识”作品。 Python 不能，因此它只能遵循严格的规则，即在调用之前必须评估调用的所有参数表达式。

Python 是一种高度动态的语言，在执行的每一步，s和 f可以反弹指向不同的对象。这意味着 Python 无法优化递归或内联函数逻辑。它无法提升 if x <= 0测试 s()以避免评估 z 的值首先。

如果您作为程序员知道在某些情况下需要避免使用第三个表达式，那么您需要自己进行优化。要么合并 s 中的逻辑进入f手动:

def f(a, b):
    if b <= 0:
        return a + 1
    return f(a, b - 1) + 1

或者将第三个表达式的计算推迟到s()通过传入一个可调用对象并生成 s 来确定是否需要计算它负责评估它:

def s(x, y, z):
   if x <= 0:
       return y
   return z()   # evaluate the value for z late

def f(a, b):
    # make the third argument a function so it is not evaluated until called
    return s(b, a+1, lambda: f(a, b - 1) + 1)