language-agnostic - 检测程序中不必要的递归调用的工具？

Question

编写递归函数时一个非常常见的初学者错误是不小心触发了来自同一函数的完全冗余的递归调用。例如，考虑这个在二叉树(不是二叉搜索树)中找到最大值的递归函数:

int BinaryTreeMax(Tree* root) {
    if (root == null) return INT_MIN;

    int maxValue = root->value;
    if (maxValue < BinaryTreeMax(root->left))
        maxValue = BinaryTreeMax(root->left);   // (1)
    if (maxValue < BinaryTreeMax(root->right))
        maxValue = BinaryTreeMax(root->right);  // (2)

    return maxValue;
}

请注意，该程序可能会对 BinaryTreeMax 进行两次完全冗余的递归调用。在第 (1) 和 (2) 行中。我们可以重写这段代码，这样就不需要通过简单地缓存之前的值来进行这些额外的调用:

int BinaryTreeMax(Tree* root) {
    if (root == null) return INT_MIN;

    int maxValue = root->value;
    int leftValue = BinaryTreeMax(root->left);
    int rightValue = BinaryTreeMax(root->right);

    if (maxValue < leftValue)
        maxValue = leftValue;
    if (maxValue < rightValue)
        maxValue = rightValue;

    return maxValue;
}

现在，我们总是恰好进行两次递归调用。

我的问题是是否有一种工具可以对程序进行静态或动态分析(使用您喜欢的任何语言；我不是太挑剔!)，可以检测程序是否正在进行完全不必要的递归调用。 “完全没有必要”我的意思是

之前已经进行过递归调用，

通过递归函数(或其后代之一)的相同调用，和

调用本身没有可观察到的副作用。

这通常可以手动确定，但我认为如果有一些工具可以自动标记这样的事情，作为帮助学生获得有关如何避免在他们的程序中犯下简单但代价高昂的错误的反馈的方式，那就太好了这可能会导致严重的低效率。

有谁知道这样的工具？

Answer 1

首先，你对“完全没有必要”的定义是不够的。两个函数调用之间的某些代码可能会影响第二个函数调用的结果。

其次，这与递归无关，同样的问题适用于任何函数调用。如果之前使用完全相同的参数调用过它，则没有副作用，并且两次调用之间的代码不会更改函数访问的任何数据。

现在，我很确定完美的解决方案是不可能的，因为它可以解决 The Halting Problem ，但这并不意味着没有办法检测到足够多的这些情况并优化掉其中的一些。

一些编译器知道如何做到这一点(GCC 有一个特定的标志，当它这样做时会警告你)。这是我在 2003 年找到的关于该问题的文章:http://www.cs.cmu.edu/~jsstylos/15745/final.pdf .

不过，我找不到用于此的工具，但这可能是 Eric Lipert 知道的，如果他碰巧遇到您的问题。