Chức năng đệ quy lấy tuổi để chạy

Question

Tôi đã lược tả mã của mình và nhận thấy rằng chương trình của tôi đã dành khoảng 85% thời gian thực hiện chức năng đệ quy đặc biệt này. Hàm này nhằm tính toán xác suất đạt được một tập hợp các trạng thái trong một chuỗi markov, với một vị trí ban đầu (x, y).

private static boolean condition(int n){ 
    int i = 0; 
    while (n >= i){ 
     if(n == i*4 || n == (i*4 - 1)) 
      return true; 
      i++; 
     } 
    return false; 
} 

public static double recursiveVal(int x, int y, double A, double B){ 

    if(x> 6 && (x- 2 >= y)){ return 1;} 
    if(y> 6 && (y- 2 >= x)){ return 0;} 
    if(x> 5 && y> 5 && x== y){ return (A*(1-B)/(1 -(A*B) - ((1-A)*(1-B))));} 

    if(condition(x+ y)){ 
     return (recursiveVal(x+1, y,A,B)*A + recursiveVal(x, y+1,A,B)*(1-A)); 
    } 
    else{ 
     return (recursiveVal(x+1, y,A,B)*(1-B) + recursiveVal(x,y+1,A,B)*B); 
    } 
} 

Tôi đã từng nói rằng 99% hàm đệ quy có thể được thay thế bằng vòng lặp while. Tôi đang gặp khó khăn khi làm điều này mặc dù. Có ai biết làm thế nào tôi có thể cải thiện thời gian thực hiện hoặc viết lại này như là một vòng lặp lặp?

Cảm ơn

Answer 1

Bạn có thể cố gắng sử dụng kỹ thuật ghi nhớ kết quả đã tính toán trước đó cho các cuộc gọi đệ quy.

• Wikipedia article on memoization.

Lưu ý phụ, tôi khuyên bạn nên định dạng lại mã của mình một chút. Đây là một phiên bản đơn giản của mã yoru.

private static boolean condition(int n){ 
    for (int i = 0; i <= n; i++) 
     if(n == i*4 || n == (i * 4 - 1)) 
      return true; 
    return false; 
} 

public static double recursiveVal(int x, int y, double A, double B){ 

    if (x > 6 && (x - 2 >= y)) 
     return 1; 

    if (y > 6 && (y - 2 >= x)) 
     return 0; 

    if(x > 5 && y > 5 && x == y) 
     return A*(1-B)/(1 -(A*B) - ((1-A)*(1-B))); 

    double val1 = recursiveVal(x+1, y, A, B); 
    double val2 = recursiveVal(x, y+1, A, B); 

    return condition(x + y) 
     ? A * val1 + val2 * (1-A) 
     : (1-B) * val1 + B * val2; 
} 

Answer 2

Để chuyển đổi thành dạng lặp lại, lưu ý rằng bạn đang tính toán một hàm trên hai biến (rời rạc). Bạn có thể sử dụng một bảng để lưu trữ các giá trị của hàm, và điền vào bảng theo một thứ tự cụ thể để bạn đã tính toán các giá trị bạn cần theo thời gian bạn cần chúng. (trong trường hợp này, từ các giá trị cao hơn là x và y).

Trong trường hợp này, các trường hợp ranh giới (tương ứng với các trường hợp cơ sở trong đệ quy gốc) là:

f(7, y..5), f(8, 6) 
f(x..5, 7), f(6, 8) 
f(7, 7) 

Sau đó chúng tôi điền vào f(7, 6) và f(6, 7) và sau đó tiến hành "xuống" - tức là f (6 , 6), f (5, 6) ... f (x, 6), f (6, 5), f (5, 5) ... f (x, 5) ... f (x, y).

Lưu ý rằng cú pháp gọi hàm chức năng tương ứng với tra cứu bảng (nó thực sự chuyển thành cú pháp mảng).

Answer 3

Nếu bạn muốn cấu trúc lại một hàm đệ quy để là một lặp đi lặp lại các bước như sau:

1) Xác định các trường hợp cơ sở của Đệ quy. Trường hợp cơ sở, khi đạt được, sẽ khiến cho đệ quy kết thúc. Mỗi đệ quy phải có một trường hợp cơ sở được xác định. Ngoài ra, mỗi cuộc gọi đệ quy phải thực hiện một tiến trình đối với trường hợp cơ bản (nếu không các cuộc gọi đệ quy sẽ được thực hiện vô hạn).
2) Thực hiện một vòng lặp sẽ lặp lại cho đến khi đạt được trường hợp cơ bản.
3) Thực hiện tiến trình đối với trường hợp cơ sở. Gửi các đối số mới lên đầu vòng lặp thay vì phương thức đệ quy.

Answer 4

Ví dụ về cách cố gắng để hiểu những gì nó đang làm có thể làm cho đoạn code nhanh hơn/đơn giản hơn ...

Phương pháp này đang cố gắng xác định xem 'n' là bội số của 4 hoặc n + 1 là một bội số của 4. Điều này có thể được viết ngắn hơn nhiều.

private static boolean condition(int n){ 
    return (n+1) & 3 <= 1; 
}