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

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;
}

现在,我们总是进行两次递归调用.

我的问题是,是否有一个工具可以对程序进行静态或动态分析(用你喜欢的任何语言;我不太挑剔!),它可以检测程序是否正在进行完全不必要的递归调用."完全没必要"我的意思是

1. 之前已经进行了递归调用,
2. 通过相同的递归函数(或其后代之一)的调用,和
3. 呼叫本身没有可观察到的副作用.

这通常可以通过手工确定,但我认为如果有一些工具可以自动标记这样的事情作为一种帮助学生获得关于如何避免在他们的程序中制造简单但昂贵的错误的反馈的方式,那将是很好的这可能导致巨大的低效率.

有谁知道这样的工具？

Answer 1

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

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

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

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

不过，我找不到这方面的工具，但如果埃里克·利珀特碰巧遇到你的问题，他可能知道这一点。