在编写递归算法时使用'static'是否作弊？

Question

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

编写一个递归函数,找到给定整数列表中的最大数字.

我提出了两个解决方案,第一个解决方案是两个递归调用:

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).

Answer 2

使用静态内部函数,递归或其他方式没有任何作弊行为.

为什么要这样做有很多很好的理由,但在你的情况下,我怀疑你提出了一个错误的解决方案 - 因为largest只会在运行它的程序的生命周期中工作一次.

考虑以下(伪)代码;

main() {
    largest([ 9, 8, 7]) // would return 9 -- OK
    largest([ 1, 2, 3]) // would return 9 ?? bad
}

原因是你largest无法分辨这两个电话之间的区别,但如果这就是你想要的那么那就没问题了.

编辑: 在回答你的评论时,这样的东西会比你的初始代码有更好的大O符号;

int largest(int arr[], int length){
    int split, lower,upper;
    switch (length) {
      case 1: return arr[0];
      case 2: if (arr[1]>arr[0]) return arr[1]; else return arr[0];
      default:
              if (len <= 0) throw error;
              split = length/2;
              lower = largest(arr,split);
              upper = largest(arr+split,length-split);
              if (lower > upper) return lower; else return upper;
    }
}

或者,显而易见的解决方案是;

int largest(int arr[], int length){
    if (length <= 0) thor error;
    int max = arr[0];
    for (int i=1; i<length; i++)
       if (arr[i] > max) max = arr[i];
    return max;
}

根本没有递归