Tái cấu trúc phương pháp đệ quy này?

Question

Tôi khá mới với ý tưởng đệ quy và đây thực sự là nỗ lực đầu tiên của tôi khi viết một phương pháp đệ quy.

Tôi đã cố gắng triển khai hàm đệ quy Max chuyển một mảng, cùng với một biến chứa kích thước của mảng để in phần tử lớn nhất.

Nó hoạt động, nhưng nó không chỉ cảm thấy đúng!

Tôi cũng đã nhận thấy rằng tôi dường như sử dụng các modifier tĩnh hơn nhiều so với các bạn cùng lớp của tôi nói chung ...

Ai có thể vui lòng cung cấp bất cứ lời khuyên nói chung cũng như thông tin phản hồi như thế nào tôi có thể cải thiện mã của tôi?

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

}

Answer 1

Việc bạn sử dụng biến tĩnh để giữ trạng thái bên ngoài hàm sẽ là một nguồn khó khăn.

Một ví dụ về thực hiện đệ quy của một max() chức năng trong giả có thể là:

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

Mấu chốt ở đây là tiếng gọi đệ quy để Max(), nơi bạn vượt qua tất cả mọi thứ trừ phần tử đầu tiên và một ít hơn kích thước. Ý tưởng chung là chức năng này nói "giá trị tối đa trong dữ liệu này là phần tử đầu tiên hoặc giá trị tối đa của các giá trị trong phần còn lại của mảng, tùy theo giá trị nào lớn hơn".

Triển khai này không yêu cầu phải có dữ liệu tĩnh bên ngoài định nghĩa hàm.

Một trong những điểm nổi bật của triển khai đệ quy là cái gọi là "điều kiện chấm dứt" ngăn cản việc đệ quy tiếp diễn mãi mãi (hoặc, cho đến khi bạn bị tràn ngăn xếp). Trong trường hợp trên, kiểm tra cho size == 1 là điều kiện chấm dứt.

Answer 2

A "max" chức năng là loại sai điều cần viết một hàm đệ quy cho - và thực tế bạn đang sử dụng giá trị tĩnh cho "hiện tại" và "maxvalue" làm cho bạn chức năng không thực sự là một hàm đệ quy.

Tại sao không làm điều gì đó dễ hiểu hơn đối với thuật toán đệ quy, như giai thừa?

Answer 3

Trước tiên, chúng ta hãy quan tâm đến vấn đề phạm vi tĩnh ... Lớp của bạn đang xác định một đối tượng, nhưng không bao giờ thực sự là một đối tượng. Kể từ khi chính là tĩnh scoped, điều đầu tiên cần làm là có được một đối tượng, sau đó thực hiện nó là phương pháp như thế này:

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

} 

Vì vậy, bây giờ chúng tôi có một đối tượng tên là RecursiveTry maxObject mà không yêu cầu phạm vi tĩnh. Tôi không chắc rằng việc tìm kiếm tối đa có hiệu quả khi sử dụng đệ quy vì số lần lặp trong phương thức lặp truyền thống tương đương nhau, nhưng số lượng stack được sử dụng lớn hơn khi sử dụng đệ quy. Nhưng đối với ví dụ này, tôi sẽ giảm nó xuống rất nhiều.

Một trong những ưu điểm của đệ quy là trạng thái của bạn thường không cần phải được duy trì trong các thử nghiệm lặp lại như trong quá trình lặp lại. Ở đây, tôi đã thừa nhận việc sử dụng một biến để giữ điểm khởi đầu, bởi vì nó ít CPU chuyên sâu mà đi qua một int mới [] có chứa tất cả các mục ngoại trừ cái đầu tiên.

Answer 4

Về cơ bản, bạn đang viết một phiên bản lặp lại nhưng sử dụng đệ quy đuôi cho vòng lặp. Ngoài ra, bằng cách tạo quá nhiều biến tĩnh, về cơ bản bạn đang sử dụng các biến toàn cục thay vì các đối tượng. Đây là một nỗ lực tại một cái gì đó gần gũi hơn với một thực hiện đệ quy điển hình. Tất nhiên, trong cuộc sống thực nếu bạn đang sử dụng một ngôn ngữ như Java không tối ưu hóa các cuộc gọi đuôi, bạn sẽ thực hiện một chức năng "Max" bằng cách sử dụng một vòng lặp.

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

Answer 5

"không phải bài tập về nhà"?

Dù sao đi nữa. Điều đầu tiên đầu tiên.

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

không có gì liên quan đến các thông số của Max() mà chúng chia sẻ tên của chúng. Di chuyển chúng đến chính và mất các "specifier" tĩnh. Chúng chỉ được sử dụng một lần, khi gọi trường hợp đầu tiên của Max() từ bên trong main(). Phạm vi của chúng không được mở rộng ra ngoài chính().

Không có lý do nào cho tất cả các lệnh gọi Max() chia sẻ một chỉ mục "hiện tại". "current" phải là local thành Max(). Nhưng sau đó làm thế nào sẽ lặp lại liên tiếp của Max() biết những gì giá trị của "hiện tại" để sử dụng? (Gợi ý: Max() đã vượt qua mức tối thiểu khác của Max() xuống dưới dòng dữ liệu đó. Thêm "hiện tại" vào dữ liệu này.)

Điều tương tự cũng xảy ra với maxValue, mặc dù tình hình ở đây có nhiều hơn một chút phức tạp. Bạn không chỉ cần truyền một "maxValue" hiện tại xuống dòng, nhưng khi đệ quy kết thúc, bạn phải truyền nó trở lại tất cả các cách tới hàm Max() đầu tiên, hàm này sẽ trả về hàm main(). Bạn có thể cần phải xem xét một số ví dụ khác về đệ quy và dành thời gian với việc này.

Cuối cùng, chính Max() là tĩnh. Một khi bạn đã loại bỏ sự cần thiết phải đề cập đến dữ liệu bên ngoài (các biến tĩnh) tuy nhiên; nó không thực sự quan trọng. Nó chỉ có nghĩa là bạn có thể gọi Max() mà không cần phải khởi tạo một đối tượng.

Answer 6

Làm cho chức năng của bạn phụ thuộc vào biến tĩnh không phải là một ý tưởng hay. Đây là có thể thực hiện đệ quy Max chức năng:

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

Answer 7

Như những người khác đã quan sát, không có cần cho đệ quy để thực hiện một chức năng Max, nhưng nó có thể được bài học để sử dụng một thuật toán quen thuộc để thử nghiệm với một mới khái niệm. Vì vậy, đây là mã được đơn giản hóa, với giải thích bên dưới:

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

tất cả trạng thái tĩnh sẽ biến mất là không cần thiết; thay vào đó mọi thứ được truyền trên stack. logic nội bộ của hàm Max được sắp xếp hợp lý và chúng tôi recurse theo hai cách khác nhau chỉ để vui vẻ

Answer 8

Bạn đang thực sự lạm dụng quá mức. Bạn không thực sự cần quá nhiều biến toàn cục. Hãy thử di chuyển

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;

vào hàm main() của bạn để chúng là các biến cục bộ.

public static void main(String[] args) 
{ 
    int[] n = new int[] {1,2,4,3,3,32,100}; 
    int current = 0; 
    int maxValue = 0; 
    int SIZE = n.length; 
    ...other code 

} 

Không phải là một giải pháp cho câu hỏi chính của bạn, nhưng thực hành tốt của nó để sử dụng các biến địa phương trong những thế giới (nói chung)

--- Như tôi đã kết thúc này, tôi nhận ra rằng tôi chỉ gạt những gì Aib nói ở trên

Answer 9

Trong Đề án này có thể được viết rất ngắn gọn:

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

Cấp, điều này sử dụng danh sách liên kết và không mảng, đó là lý do tôi đã không vượt qua nó một kích thước ele nhưng tôi cảm thấy điều này làm cho vấn đề của nó trở nên trầm trọng. Đây là định nghĩa pseudocode:

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 

Answer 10

Đây là phiên bản Java dành cho bạn.

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

Quan hệ lặp lại là phần tử tối đa của mảng là phần tử đầu tiên hoặc tối đa phần còn lại của mảng. Điều kiện dừng đạt được khi bạn đạt đến cuối của mảng. Lưu ý việc sử dụng ghi nhớ để giảm các cuộc gọi đệ quy (gần một nửa).

Answer 11

Cách tốt hơn để nhận giá trị tối đa của một mảng đệ quy sẽ là triển khai quicksort (đây là thuật toán sắp xếp đệ quy tốt đẹp), và sau đó chỉ trả lại giá trị đầu tiên.

Đây là một số Java code for quicksort.

Answer 12

codesize nhỏ nhất tôi có thể nhận được:

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

Một vài điều:

1/Nếu mảng là zero-kích thước, nó sẽ trả tối đa là -1 (bạn có thể có một giá trị đánh dấu, nói, -MAX_INT, hoặc ném một ngoại lệ). Tôi đã thực hiện giả định cho mã rõ ràng ở đây để giả định tất cả các giá trị là số không hoặc nhiều hơn. Nếu không, tôi sẽ phải lấy mã với tất cả các loại công cụ không cần thiết (liên quan đến việc trả lời câu hỏi).

2/Hầu hết các cuộc khảo sát đều 'sạch' theo ý kiến ​​của tôi nếu trường hợp chấm dứt không có dữ liệu thay vì dữ liệu cuối cùng, do đó tôi trả về giá trị được đảm bảo nhỏ hơn hoặc bằng giá trị tối đa khi chúng tôi hoàn thành mảng. Những người khác có thể khác nhau trong quan điểm của họ nhưng nó sẽ không phải là lần đầu tiên hoặc lần cuối cùng họ đã sai :-).

3/Cuộc gọi đệ quy chỉ nhận được tối đa phần còn lại của danh sách và so sánh nó với phần tử hiện tại, trả về tối đa hai phần tử.

4/Giải pháp 'lý tưởng' sẽ là chuyển một mảng đã sửa đổi trên mỗi cuộc gọi đệ quy để bạn chỉ so sánh phần tử đầu tiên với phần còn lại của danh sách, loại bỏ nhu cầu về currPos. Nhưng điều đó sẽ không hiệu quả và sẽ mua lại cơn thịnh nộ của SO.

5/Điều này có thể không nhất thiết phải là giải pháp tốt nhất. Có thể do chất xám đã bị xâm phạm do sử dụng quá nhiều LISP với CAR, CDR và ​​các dấu ngoặc đơn vô tận này.