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

调用函数时，所有参数在传递给函数之前都会被完全求值。换句话说，f(5,-1)甚至在s启动之前就被执行了。你知道吗

幸运的是，有一种按需计算表达式的简单方法：函数。不是将f(a,b-1)的结果传递给z，而是传递一个计算该结果的函数：

def s(x,y,z):
   if x <= 0:
       return y
   return z()  # z is a function now

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

print(f(5,2))  # output: 8

Answer 2

你的大脑正在与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()通过传入一个callable并使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)