c - 写递归算法时使用 'static'是作弊吗？

Question

作为编程作业的一部分，我需要编写一个递归函数来确定数组中的最大整数。引用确切的任务:

Write a recursive function that finds the largest number in a given list of integers.

我想出了两个解决方案，第一个进行了两次递归调用:

int largest(int arr[], int length){
    if(length == 0)
        return 0;
    else if(arr[length - 1] > largest(arr,length -1))
        return arr[length];
    else return largest(arr,length -1);
}

第二个只生成一个，但是它使用静态变量n:

int largest(int arr[], int length){
    static int n = -1;
    if(length == 0)
        return n;
    else if (arr[length - 1] > n)
        n = arr[length - 1];
    return largest(arr, length - 1);
}

我想知道使用静态变量来完成这样的任务是否会被视为作弊。无论哪种方式，哪一个被认为是更好的形式？是否有一种递归方法使两者都居首？

Answer 1

我不会说以这种方式使用 static 变量是作弊 - 我会说这是不正确的。 :-)

假设您在多个不同的数组上多次调用此函数。引入静态变量后，n 的值永远不会在调用之间重置，因此您最终可能会返回错误的值。一般来说，这样设置通常是糟糕的编码风格，因为它很容易得到错误的答案。此外，如果您的数组仅包含负值，您可能会返回 -1 作为答案，即使 -1 实际上比数组中的所有内容都大。

我确实认为第二个版本比第一个版本有一个很好的优势 - 它快得多，因为它只进行一次递归调用而不是两次。考虑使用第一个版本，但对其进行更新，以便缓存递归调用返回的值，这样就不会进行两次调用。这将以指数方式加速代码；初始版本需要时间 Θ(2ⁿ)，而更新版本需要时间 Θ(n)。