不必要的递归调用

Question

考虑此递归功能：

bool foo(u_int d){
    if (d > 1) return foo(d - 1) or foo(d - 2);
    return true;
}

对于d的所有值，此函数均返回。如果对其进行天真的评估，它将进行o（f_n）递归电话，其中f_n是nth fibonacci编号。

如何有效地评估“或”表达式。如果一个术语为true，则不会评估另一个术语，因为它不会改变表达式的值。因此，从来没有称呼

foo(d-2)

，因此该函数的复杂性为o（d）。

我通过致电

foo(100)

来检查了一下，这很快就完成了。 f_100≈3.5e20，因此没有这样的递归电话。

如果我们将“和“”和“ true”交换为“ false”，则其行为非常相似，因为“和“表达”也被优化。

bool foo(u_int d){
    if (d > 1) return foo(d - 1) and foo(d - 2);
    return false;
}

现在考虑此功能：

bool bar(){
    return 0 * bar();
}

这种引起无限的递归，即使0 *始终为0.

。 我还尝试了以下功能：

bool bar(u_int d){
    if (d > 1) return 0 * bar(d - 1) * bar(d - 2);
    return 1;
}

在这里也进行了所有递归电话。我跑了

bar(40)

，有一个明显的延迟。我将函数的运行时间与

bar

baz

它们非常相似。他们俩都进行了o（f_n）递归电话。
我的问题是，为什么不以布尔表达式类似的方式优化乘法。 0 *某些东西总是0，因此无需评估递归电话。
    

构建

bool baz(u_int d){
    if (d > 2) return baz(d - 1) and baz(d - 2);
    return true;
}

（和

or

）必须做简短的插图，这就是它们通过语言定义的方式。

and

没有短时间的时间。

Answer 1

*

最终是否返回还是抛出异常通常是编译时间无法解决的问题。