Làm thế nào để chuyển đổi đệ quy để lặp lại?

Question

Câu hỏi này được hỏi vài lần nhưng tôi vẫn thấy khó chuyển đổi dễ dàng mã dễ đọc và trực quan thành mã lặp. Ví dụ tôi đã thực hành một câu hỏi mã hóa và tôi đã đưa ra 26 số nguyên cho biết số lần mỗi ký tự xuất hiện trong chuỗi. Tôi nên in tất cả các chuỗi có thể. Sau đây là mã đệ quy của tôi

private static void combinatorial(String prefix, ArrayList<Integer> remainingToFill, 
     int totalLength) { 
    if (prefix.length() == totalLength) { 
     System.out.println(prefix); 
    } 
    for (int i = 0; i < remainingToFill.size(); i++) { 
     if (remainingToFill.get(i) > 0) { 
      ArrayList<Integer> toFill = new ArrayList<>(remainingToFill); 
      toFill.set(i, toFill.get(i) - 1); 
      combinatorial(prefix + (char) ('a' + i), toFill, totalLength); 
     } 
    } 
} 

Tôi đã mã hóa phiên bản lặp lại nhưng chức năng kết quả phức tạp hơn và không đọc được và mất nhiều thời gian hơn để viết mã. Làm cách nào để giải quyết vấn đề này? Có bất kỳ kỹ thuật đơn giản nào tôi có thể thực hiện theo đó sẽ dẫn đến mã dễ đọc và dễ đọc không?

Answer 1

Vâng, lý do ngôn ngữ lập trình hỗ trợ biểu thức đệ quy của chương trình là nó thường đơn giản hơn các biểu mẫu lặp lại rõ ràng. Vì vậy, câu hỏi của bạn gần như tự trả lời.

Tuy nhiên, có thực sự là một cách có phương pháp để chuyển đổi biểu mẫu đệ quy thành biểu mẫu lặp lại luôn hoạt động. Nó giúp để có một ngôn ngữ với goto, mà Java không.

Trước tiên hãy dọn sạch java. Chúng tôi muốn sử dụng một số lượng tối thiểu các đối số và biến địa phương vì những gì còn lại phải đi trên ngăn xếp rõ ràng của chúng tôi. Đây rồi. Chúng tôi loại bỏ tất cả ngoại trừ i và prefix.

class CombinationLister { 
    private final int[] counts; 
    private final int length; 

    CombinationLister(int[] counts) { 
    this.counts = counts.clone(); 
    this.length = Arrays.stream(counts).sum(); 
    } 

    private void list(String prefix) { 
    if (prefix.length() == length) { 
     System.out.println(prefix); 
    } 
    for (int i = 0; i < counts.length; i++) { 
     if (counts[i] > 0) { 
     --counts[i]; 
     list(prefix + (char) ('a' + i)); 
     ++counts[i]; 
     } 
    } 
    } 

    void run() { 
    list(""); 
    } 
} 

Bây giờ chúng ta hãy phiên âm thành C, có goto. Ở đây rất dễ dàng để loại bỏ ngay cả prefix bằng cách thêm bộ đệm chuỗi chung.

#include <stdio.h> 

char str[100]; 
int counts[] = { 1, 2, 3 }; 
int n_counts = 3; 
int total_count = 6; 
int len = 0; 

void list(void) { 
    if (len == total_count) printf("%.*s\n", total_count, str); 
    for (int i = 0; i < n_counts; i++) { 
    if (counts[i] > 0) { 
     str[len] = 'a' + i; 
     --counts[i]; 
     ++len; 
     list(); 
     --len; 
     ++counts[i]; 
    } 
    } 
} 

Bây giờ, các quy tắc là:

• Xây dựng một chồng hồ sơ với một lĩnh vực cho mỗi biến địa phương và tham số. Ở đây chúng tôi chỉ còn i, vì vậy chúng tôi thậm chí không cần bản ghi. Một ngăn gồm int sẽ thực hiện.
• Thay thế trang web gọi đệ quy với
  • một push vào stack, sau đó
  • thiết lập lại các thông số cho các giá trị mới của họ (ở đây chúng tôi không có bất kỳ), sau đó
  • nhảy khi bắt đầu và
  • ngay sau khi nhảy, đặt nhãn rtn:.
• Ở cuối hàm, thêm một epilog để kiểm tra xem ngăn xếp có trống không. Nếu không, nó bật ngăn xếp và nhảy đến rtn:.

Các quy tắc này về cơ bản bắt chước mã trình biên dịch sẽ tạo để xử lý các cuộc gọi đệ quy.

Đưa nó tất cả cùng nhau, chúng ta có:

int stk[100]; 
int p = 0; // stack pointer 

void list(void) { 
    int i; 
start: 
    if (len == total_count) printf("%.*s\n", total_count, str); 
    for (i = 0; i < n_counts; i++) { 
    if (counts[i] > 0) { 
     str[len] = 'a' + i; 
     --counts[i]; 
     ++len; 
     stk[p++] = i; // push i on stack 
     goto start; 
    rtn: 
     --len; 
     ++counts[i]; 
    } 
    } 
    // epilog 
    if (p > 0) { 
    i = stk[--p]; // restore i from stack 
    goto rtn; 
    } 
} 

Nếu bạn làm theo các bước một cách cẩn thận, mã của bạn sẽ chạy đầu tiên thử mỗi lần.Mẹo bổ sung duy nhất là khi có nhiều hơn một trang gọi đệ quy, bạn sẽ cần một nhãn trả về cho mỗi rtn1:, rtn2:, v.v. và thêm một trường int trong ngăn xếp có nghĩa là trang web trả về, với câu lệnh chuyển đổi trong epilog để nhảy đến đúng.

Tất nhiên đây không phải là mã đẹp. Chúng tôi muốn loại bỏ số goto s. Nó chỉ ra điều này luôn luôn có thể bằng cách làm "đại số" để chuyển đổi các gotos thành vòng lặp. Có một vài chục kỹ thuật chuyển đổi ... quá nhiều để mô tả ở đây. Nó giống như đơn giản hóa một phương trình trong lớp toán học. Đôi khi cần thêm cờ Boolean. Trong trường hợp này, mặc dù, chúng tôi không cần phải. Tôi đã hoàn thành với điều này:

void list(void) { 
    for (int i = 0;;) { 
    while (i < n_counts && counts[i] == 0) i++; 
    if (i < n_counts) { 
     --counts[i]; 
     str[len] = 'a' + i; 
     stk[p++] = i; 
     if (++len == total_count) printf("%.*s\n", total_count, str); 
     i = 0; 
    } else if (p > 0) { 
     i = stk[--p]; 
     --len; 
     ++counts[i++]; 
    } 
    else break; 
    } 
} 

Just for fun, trở lại Java:

class CombinationLister { 
    private final int[] counts; 
    private final char[] str; 
    private final int[] stk; 
    private int p = 0; 
    private int len = 0; 

    CombinationLister(int[] counts) { 
    this.counts = counts.clone(); 
    this.str = new char[Arrays.stream(counts).sum()]; 
    this.stk = new int[str.length]; 
    } 

    void run() { 
    for (int i = 0;;) { 
     while (i < counts.length && counts[i] == 0) i++; 
     if (i < counts.length) { 
     --counts[i]; 
     str[len] = (char) ('a' + i); 
     stk[p++] = i; 
     if (++len == str.length) System.out.println(str); 
     i = 0; 
     } else if (p > 0) { 
     i = stk[--p]; 
     --len; 
     ++counts[i++]; 
     } else break; 
    } 
    } 
} 

Answer 2

public static void combinatorial(ArrayList<Integer> remainingToFill, int totalLength) { 
    Stack st = new Stack(); 
    st.push(new Pair<String,Integer>("", 0)); 
    while(!st.empty()){ 
     Pair<String,Integer> top = (Pair<String,Integer>) st.pop(); 
     String prefix = top.getKey(); 
     Integer i = top.getValue(); 
     if (prefix.length() == totalLength) { 
      System.out.println(prefix); 
      int index= prefix.charAt(prefix.length()-1)-'a' ; 
      remainingToFill.set(index , remainingToFill.get(index) + 1); 
     } 
     else{ 
      if(i== remainingToFill.size()){ 
       if(prefix.length()>0){ 
        int index= prefix.charAt(prefix.length()-1)-'a' ; 
        remainingToFill.set(index , remainingToFill.get(index) + 1); 
       } 
      } 
      else{ 
       st.push(new Pair<String,Integer>(prefix, i+1)); 
       if(remainingToFill.get(i) > 0){ 
        remainingToFill.set(i, remainingToFill.get(i) - 1); 
        st.push(new Pair<String,Integer>(prefix+(char)('a'+i), 0)); 
       } 
      } 
     } 
    } 
}