5

我对递归的想法很陌生，这实际上是我第一次尝试编写递归方法。

我试图实现一个递归函数 Max，它传递一个数组，以及一个保存数组大小的变量，以便打印最大的元素。

它有效，但感觉不对！

我还注意到，我似乎比一般同学更多地使用静态修饰符......

任何人都可以提供任何一般提示以及有关如何改进代码的反馈吗？

public class RecursiveTry{

static int[] n = new int[] {1,2,4,3,3,32,100};
static int current = 0;
static int maxValue = 0;
static int SIZE = n.length;

public static void main(String[] args){
    System.out.println(Max(n, SIZE));
}   

public static int Max(int[] n, int SIZE) {
    if(current <= SIZE - 1){
        if (maxValue <= n[current]) {
            maxValue = n[current];
            current++;
            Max(n, SIZE);                       
        }
        else {
            current++;
            Max(n, SIZE);
        }
    }
    return maxValue;
}

}

4

11 回答 11

9

您使用静态变量来保持函数外部的状态将是一个困难的来源。

在伪代码中递归实现 max() 函数的示例可能是：

function Max(data, size) {
    assert(size > 0)
    if (size == 1) {
        return data[0]
    }
    maxtail = Max(data[1..size], size-1)
    if (data[0] > maxtail) {
        return data[0]
    } else {
        return maxtail
    }
}

这里的关键是对 Max() 的递归调用，您可以在其中传递除第一个元素之外的所有元素，并且比大小小一个。一般的想法是这个函数说“这个数据中的最大值是第一个元素，或者是数组其余部分中的最大值，以较大者为准”。

此实现不需要函数定义之外的静态数据。

递归实现的标志之一是所谓的“终止条件”，它可以防止递归永远进行（或者，直到堆栈溢出）。在上述情况下，测试为size == 1终止条件。

于 2008-10-29T01:17:42.850 回答
4

让你的函数依赖于静态变量并不是一个好主意。这是递归 Max 函数的可能实现：

int Max(int[] array, int currentPos, int maxValue) {
    // Ouch!
    if (currentPos < 0) {
        raise some error
    }
    // We reached the end of the array, return latest maxValue
    if (currentPos >= array.length) {
        return maxValue;
    }
    // Is current value greater then latest maxValue ?
    int currentValue = array[currentPos];
    if (currentValue > maxValue) {
        // currentValue is a new maxValue
        return Max(array, currentPos + 1, currentValue);
    } else {
        // maxValue is still a max value
        return Max(array, currentPos + 1, maxValue);
    }
}
...

int[] array = new int[] {...};
int currentPos = 0;
int maxValue = array[currentPos] or minimum int value;  
    maxValue = Max(array, currentPos, maxValue);
于 2008-10-29T01:28:45.887 回答
3

“max”函数是编写递归函数的错误类型 - 而且您使用“current”和“maxValue”的静态值这一事实使您的函数不是真正的递归函数。

为什么不做一些更适合递归算法的事情，比如阶乘？

于 2008-10-29T01:14:03.777 回答
2

“不做作业”？

反正。第一件事。这

static int[] n = new int[] {1,2,4,3,3,32,100};
static int SIZE = n.length;

与它们共享名称的 Max() 的参数无关。将这些移到 main 并丢失“静态”说明符。当从 main() 内部调用 Max() 的第一个实例时，它们只使用一次。它们的范围不应超出 main()。

没有理由让 Max() 的所有调用共享一个“当前”索引。“当前”应该是 Max() 的本地。但是，Max() 的连续重复如何知道要使用的“当前”值是什么？（提示：Max() 已经在传递其他 Max() 的下线一些数据。将“当前”添加到此数据。）

maxValue 也是如此，尽管这里的情况有点复杂。您不仅需要将当前的“maxValue”向下传递，而且当递归完成时，您必须将其一直传递回第一个 Max() 函数，该函数会将其返回给 main()。您可能需要查看其他一些递归示例并花一些时间研究这个。

最后，Max() 本身是静态的。但是，一旦您消除了引用外部数据（静态变量）的需要；没关系。这只是意味着您可以调用 Max() 而无需实例化对象。

于 2008-10-29T01:28:38.117 回答
2

正如其他人所观察到的，实现 Max 函数不需要递归，但使用熟悉的算法来试验新概念可能是有益的。所以，这里是简化的代码，下面有解释：

public class RecursiveTry
{
    public static void main(String[] args)
    {
        System.out.println(Max(new int[] {1,2,4,3,3,32,100}, 0, 0));
    }   

    public static int Max(int[] n, int current, int maxValue) 
    {
        if(current < n.Length)
        {
            if (maxValue <= n[current] || current == 0))
            {
                return Max(n, current+1, n[current]);
            }
            return Max(n, current+1, maxValue);
        }
        return maxValue;
   }
}

所有的静态都没有必要了；相反，所有内容都在堆栈上传递。Max函数的内部逻辑是流线型的，我们用两种不同的方式递归只是为了好玩

于 2008-10-29T01:29:40.703 回答
2

这是适合您的 Java 版本。

public class Recursion {

    public static void main(String[] args) {
        int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        System.out.println("Max: " + max(0, data));
    }

    public static int max(int i, int[] arr) {
        if(i == arr.length-1) {
            return arr[i];
        }

        int memo = max(i+1, arr);
        if(arr[i] > memo) {
            return arr[i];
        }
        return memo;
    }
}

递归关系是数组的最大元素要么是第一个元素，要么是数组其余部分的最大值。当您到达数组的末尾时，就达到了停止条件。请注意使用 memoization 将递归调用（大致）减少一半。

于 2008-10-29T02:44:36.233 回答
0

您实际上是在编写迭代版本，但使用尾递归进行循环。此外，通过将这么多变量设为静态，您实际上是在使用全局变量而不是对象。这是一种更接近典型递归实现的尝试。当然，在现实生活中，如果您使用像 Java 这样不优化尾调用的语言，您将使用循环实现“Max”函数。

public class RecursiveTry{
  static int[] n;

  public static void main(String[] args){
        RecursiveTry t = new RecursiveTry(new int[] {1,2,4,3,3,32,100});
        System.out.println(t.Max());
  }       

  RecursiveTry(int[] arg) {
    n = arg;
  }

  public int Max() {
    return MaxHelper(0);
  }

  private int MaxHelper(int index) {
    if(index == n.length-1) {
      return n[index];
    } else {
      int maxrest = MaxHelper(index+1);
      int current = n[index];
      if(current > maxrest)
        return current;
      else
        return maxrest;
    }
  }
}
于 2008-10-29T01:19:51.253 回答
0

在 Scheme 中，这可以非常简洁地写成：

(define (max l)
    (if (= (length l) 1)
        (first l)
        (local ([define maxRest (max (rest l))])
          (if (> (first l) maxRest)
              (first l)
              maxRest))))

当然，这使用了链表而不是数组，这就是为什么我没有将 size 元素传递给它的原因，但我觉得这将问题提炼到了本质。这是伪代码定义：

define max of a list as:
    if the list has one element, return that element
    otherwise, the max of the list will be the max between the first element and the max of the rest of the list
于 2008-10-29T01:49:02.677 回答
0

递归获取数组最大值的更好方法是实现快速排序（这是一种很好的递归排序算法），然后只返回第一个值。

这是一些用于快速排序的 Java 代码。

于 2008-10-29T03:12:39.763 回答
0

我能得到的最小代码大小：

public class RecursiveTry {
    public static void main(String[] args) {
        int[] x = new int[] {1,2,4,3,3,32,100};
        System.out.println(Max(x, 0));
    }   

    public static int Max(int[] arr, int currPos) {
        if (arr.length == 0) return -1;
        if (currPos == arr.length) return arr[0];
        int len = Max (arr, currPos + 1);
        if (len < arr[currPos]) return arr[currPos];
        return len;
    }
}

一些东西：

1/ 如果数组大小为零，则返回最大值 -1（您可以使用另一个标记值，例如 -MAX_INT，或引发异常）。为了代码清晰，我在这里假设所有值都为零或更多。否则我会在代码中加入各种不必要的东西（关于回答问题）。

2/如果终止情况是无数据而不是最后一个数据，我认为大多数递归是“更干净”的，因此当我们完成数组时，我返回一个保证小于或等于最大值的值。其他人的看法可能不同，但这不会是他们第一次或最后一次犯错:-)。

3/ 递归调用只获取列表其余部分的最大值并将其与当前元素进行比较，返回两者中的最大值。

4/“理想”的解决方案是在每次递归调用时传递一个修改后的数组，这样您只需将第一个元素与列表的其余部分进行比较，从而无需 currPos。但这将是低效的，并且会平息 SO 的愤怒。

5/ 这不一定是最好的解决方案。可能是由于过度使用 LISP 及其 CAR、CDR 和那些无休止的括号而损害了灰质。

于 2008-10-29T03:45:51.897 回答
-2

首先，让我们处理静态范围问题......您的类正在定义一个对象，但从未实际实例化一个对象。由于 main 是静态作用域的，首先要做的是获取一个对象，然后执行它的方法，如下所示：

public class RecursiveTry{

    private int[] n = {1,2,4,3,3,32,100};

    public static void main(String[] args){
        RecursiveTry maxObject = new RecursiveTry();
        System.out.println(maxObject.Max(maxObject.n, 0));
    }

    public int Max(int[] n, int start) {
        if(start == n.length - 1) {
            return n[start];
        } else { 
            int maxRest = Max(n, start + 1);
            if(n[start] > maxRest) {
                return n[start];
            }
            return maxRest;
        }
    }

}

所以现在我们有一个名为 maxObject 的 RecursiveTry 对象，它不需要静态范围。我不确定使用递归找到最大值是否有效，因为传统循环方法中的迭代次数大致相等，但使用递归时使用的堆栈量更大。但是对于这个例子，我会减少很多。

递归的优点之一是您的状态通常不需要像在迭代中那样在重复测试期间保持不变。在这里，我承认使用变量来保存起点，因为传递一个包含除第一个项目之外的所有项目的新 int[] 的 CPU 密集度较低。

于 2008-10-29T01:18:53.893 回答