Tìm int tích cực lớn nhất trong một mảng bằng cách đệ quy

Question

Tôi quyết định triển khai một chương trình rất đơn giản đệ quy, để xem Java xử lý đệ quy tốt như thế nào, và xuất hiện một chút ngắn. Đây là những gì tôi đã kết thúc bằng văn bản:

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

Và điều đó hoạt động tốt, nhưng vì nó hơi xấu xí, tôi tự hỏi nếu có cách nào tốt hơn. Nếu bất cứ ai có bất kỳ suy nghĩ/lựa chọn thay thế/cú pháp đường để chia sẻ, mà sẽ được nhiều đánh giá cao!

P.s. Nếu bạn nói "sử dụng Lisp" bạn giành chiến thắng không có gì (nhưng tôn trọng). Tôi muốn biết nếu điều này có thể được thực hiện để trông đẹp trong Java.

* và tốt như thế nào tôi xử lý đệ quy

Answer 1

2 cải tiến:

• không sao chép của mảng (chỉ sử dụng bù đắp)

• không cần phải cung cấp cho tối đa hiện tại

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

Bắt đầu đệ quy với recursive(ints, 0).

Answer 2

Bạn có thể vượt qua các chỉ số hiện tại như một tham số thay vì sao chép gần như toàn bộ mảng mỗi lần hoặc bạn có thể sử dụng một cách tiếp cận phân chia và chinh phục.

Answer 3

Đây là cách tôi có thể làm cho phương pháp đệ quy trông đẹp hơn:

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

Điều này tránh sự sao chép mảng đắt tiền, và làm việc cho một mảng đầu vào trống. Bạn có thể thực hiện một phương pháp quá tải bổ sung với chỉ có hai thông số cho chữ ký giống như chức năng lặp đi lặp lại:

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

Answer 4

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

Answer 5

Mã đệ quy của bạn sử dụng System.arrayCopy, nhưng mã lặp lại của bạn không làm điều này, vì vậy, microbenchmark của bạn sẽ không chính xác. Như những người khác đã đề cập, bạn có thể xóa mã đó bằng cách sử dụng Math.min và sử dụng chỉ mục mảng thay vì cách tiếp cận giống như hàng đợi mà bạn có.

Answer 6

... để xem Java xử lý đệ quy

tốt như thế nào Câu trả lời đơn giản là Java không xử lý đệ quy tốt. Cụ thể, các trình biên dịch Java Sun và các JVM Hotspot không thực hiện tối ưu hóa đệ quy đuôi gọi, vì vậy các thuật toán chuyên sâu đệ quy có thể dễ dàng tiêu thụ rất nhiều không gian ngăn xếp.

Tuy nhiên, tôi đã thấy các bài viết nói rằng các JVM của IBM làm hỗ trợ tối ưu hóa này. Và tôi đã thấy một email từ một người không phải là Sun, người đã nói rằng anh ấy đã thêm nó làm phần mở rộng Hotspot thử nghiệm làm dự án luận án.

Answer 7

Dưới đây là một biến thể nhẹ thể hiện như thế nào danh sách liên kết thường một chút đẹp hơn cho đệ quy, trong đó "đẹp hơn" có nghĩa là "ít thông số trong chữ ký phương pháp"

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

Answer 8

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

Answer 9

Tôi thực sự có một lớp học trước khi thực hiện điều đó Tôi thiết lập để tìm số nguyên lớn nhất của bất kỳ tập hợp các giá trị nào. Bạn có thể đưa lớp này vào dự án của mình và chỉ cần sử dụng lớp này trong bất kỳ lớp nào như vậy:

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

Điều này sẽ trả về giá trị "120" và đặt nó vào đầu ra. Dưới đây là các mã nguồn phương pháp nếu bạn quan tâm đến việc sử dụng nó:

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

Answer 10

Sau đây là mã mẫu được hướng dẫn bởi người hướng dẫn Java của tôi, Giáo sư Penn Wu, trong một bài giảng của ông. Hy vọng nó giúp.

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

Answer 11

Đây là tôi thay thế

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