代码之家 › 专栏 › 技术社区 › Rob Grant

递归求数组中最大正整数

puzzle recursion java

Rob Grant · 技术社区 · 15 年前

我决定递归地实现一个非常简单的程序,看看Java如何处理递归*,结果有点短。这就是我最后写的:

public class largestInIntArray {
  public static void main(String[] args)
  {
    // These three lines just set up an array of ints:
    int[] ints = new int[100];
    java.util.Random r = new java.util.Random();
    for(int i = 0; i < 100; i++) ints[i] = r.nextInt();

    System.out.print("Normal:"+normal(ints,-1)+" Recursive:"+recursive(ints,-1));
  }

  private static int normal(int[] input, int largest) {
    for(int i : input)
      if(i > largest) largest = i;

    return largest;
  }

  private static int recursive(int[] ints, int largest) {
    if(ints.length == 1)
      return ints[0] > largest ? ints[0] : largest;

    int[] newints = new int[ints.length - 1];
    System.arraycopy(ints, 1, newints, 0, ints.length - 1); 

    return recursive(newints, ints[0] > largest ? ints[0] : largest);
  }
}

这很好,但因为它有点难看,我想知道是否有更好的方法。如果有人有任何想法/备选方案/语法糖可以分享,那将不胜感激!

JAVA .

我句柄递归

11 回复 | 直到 15 年前

Jerome 15 年前

无需给出当前最大值

private static int recursive(int[] ints, int offset) {
    if (ints.length - 1 == offset) {
        return ints[offset];
    } else {
        return Math.max(ints[offset], recursive(ints, offset + 1));
    }
}

使用 recursive(ints, 0)

Greg Hewgill 15 年前

下面是我如何使递归方法看起来更好的方法:

  private static int recursive(int[] ints, int largest, int start) {
    if (start == ints.length) {
      return largest;
    }
    return recursive(ints, Math.max(ints[start], largest), start + 1);
  }

  private static int recursive(int[] ints, int largest) {
    return recursive(ints, largest, 0);
  }

Oleksii G. 15 年前

可以将当前索引作为参数传递,而不是每次复制几乎整个数组,或者可以使用分而治之的方法。

cletus 15 年前

public static int max(int[] numbers) {
  int size = numbers.length;
  return max(numbers, size-1, numbers[size-1]);
}

public static int max(int[] numbers, int index, int largest) {
  largest = Math.max(largest, numbers[index]);
  return index > 0 ? max(numbers, index-1, largest) : largest;
}

Stephen C 15 年前

... 看看Java如何处理递归

简单的答案是Java不能很好地处理递归。具体来说,Sun java编译器和Hotspot JVM没有实现尾部调用递归优化,因此递归密集型算法很容易消耗大量堆栈空间。

做支持此优化。我看到一封来自某个非太阳人的电子邮件,他说他将把它作为一个实验热点扩展作为一个论文项目。

Peter Recore 15 年前

  private static int recursive(LinkedList<Integer> list) {
    if (list.size() == 1){
      return list.removeFirst();
    }
    return Math.max(list.removeFirst(),recursive(list));
  }

Kristopher Ives 15 年前

递归代码使用 System.arrayCopy Math.min 使用数组索引,而不是像队列一样的方法。

Andrew Barber Eric Lafortune 12 年前

public class Maximum 
{

    /**
     * Just adapted the iterative approach of finding maximum and formed a recursive function
     */
    public static int max(int[] arr,int n,int m)
    {
        if(m < arr[n])
        {
            m = arr[n];
            return max(arr,n - 1,m);
        }
        return m;
    }
    public static void main(String[] args) 
    {
       int[] arr = {1,2,3,4,5,10,203,2,244,245,1000,55000,2223};
       int max1 =  max(arr,arr.length-1,arr[0]);
       System.out.println("Max: "+ max1);
    }
}

JeremyF 12 年前

 System.out.println(figures.getLargest(8,6,12,9,120));

这将返回值“120”,并将其放入输出中。如果您有兴趣使用,请参阅以下方法源代码:

public class figures {

public static int getLargest(int...f) {
   int[] score = new int[f.length];
    int largest=0;
    for(int x=0;x<f.length;x++) {
        for(int z=0;z<f.length;z++) {
            if(f[x]>=f[z]) {
                score[x]++;
            }else if(f[x]<f[z]) {

            }else {
                continue;
            }
            if(z>=f.length) {
                z=0;
                break;
            }
        }
    }
    for(int fg=0;fg<f.length;fg++) {
        if(score[fg]==f.length) {
            largest = f[fg];
        }
    }
    return largest;
    }
}

JavaStudent 10 年前

import java.util.Random;



public class Recursion

{

 static int s = 0;

 

 public static Double max(Double[] d, int n, Double max)

 {

  if (n==0) { return max;}

  else 

  {

  

   if (d[n] > max)

   {

    max = d[n];

   }

   

   return max(d, n-1, max);



  }   

 }



 public static void main(String[] args)

 {

  Random rn = new Random();

  Double[] d = new Double[15];

  

  for (int i=0; i
  {

   d[i] = rn.nextDouble();

   System.out.println(d[i]);

  }

  

  System.out.print("\nMax: " + max(d, d.length-1, d[0]));

 }

}

Tschaeggaer 9 年前

这是我的选择

public class recursion
{
  public static int max( int[] n, int index )
  {
    if(index == n.length-1)   // If it's simple, solve it immediately:
      return n[index];        // when there's only one number, return it
    if(max(n, index+1) > n [index]) // is one number bigger than n?
      return max(n, index+1); // return the rest, which contains that bigger number
    return n[index];          // if not, return n which must be the biggest number then
  }

  public static void main(String[] args)
  {
    int[] n = {100, 3, 5, 1, 2, 10, 2, 15, -1, 20, -1203}; // just some numbers for testing
    System.out.println(max(n,0));
  }
}