Câu hỏi Factorial sử dụng đệ quy trong Java


Tôi đang học Java bằng cách sử dụng cuốn sách Java: Tài liệu tham khảo đầy đủ. Hiện tại tôi đang làm việc về chủ đề Recursion.

Xin lưu ý: Có những câu hỏi tương tự trên stackoverflow. Tôi đã tìm kiếm chúng nhưng tôi không tìm thấy giải pháp cho câu hỏi của mình. Tôi bối rối với logic trong chương trình sau đây.

Nếu tôi chạy chương trình dưới đây, nó tạo ra đầu ra chính xác, nhưng tôi không hiểu logic.

  • Tôi không hiểu logic trong dòng sau: result = fact (n-1) * n;
  • Từ kiến ​​thức của tôi, Nếu chúng ta chuyển giá trị n = 4 như được hiển thị trong chương trình dưới đây,
  • Sau đó, 3 * 4 được lưu trữ trong kết quả tức là, 12.
  • Một lần nữa, thực tế (n-1) được gọi. Sau đó n trở thành 3.
  • Sau đó, 2 * 3 được lưu trữ trong kết quả thay thế 12 trước đó.
  • Tôi nghĩ rằng bạn hiểu nơi tôi đang mắc kẹt / bối rối.

  • Cảm ơn bạn.

class Calculation
{
    int fact(int n)
    {
        int result;

       if(n==1)
         return 1;

       result = fact(n-1) * n;
       return result;
    }
}

public class Factorial
{
     public static void main(String args[])
     {
       Calculation obj_one = new Calculation();

       int a = obj_one.fact(4);
       System.out.println("The factorial of the number is : " + a);
     }
}

24
2017-11-18 13:48


gốc


Lời khuyên của tôi trước khi đào sâu vào Java, trước tiên bạn cần phải hiểu toán học đằng sau đệ quy. Nếu bạn chưa làm như vậy, đây sẽ là một khởi đầu rất tốt cho bạn en.wikipedia.org/wiki/Recursion - GETah
Hy vọng điều này làm cho bạn rõ ràng hơn nhiều programmerinterview.com/index.php/recursion/… - Rangesh


Các câu trả lời:


result là một biến cục bộ của fact phương pháp. Vì vậy, mỗi khi phương thức thực tế được gọi, kết quả được lưu trữ trong một biến khác với lời gọi thực tế trước đó.

Vì vậy, khi thực tế được gọi với 3 là đối số, bạn có thể tưởng tượng rằng kết quả của nó là

 result3 = fact(2) * 3
 result3 = result2 * 3
 result3 = 1 * 2 * 3

9
2017-11-18 13:53





Trước tiên, bạn nên hiểu cách hoạt động của giai thừa.

Cho phép mất 4! làm ví dụ.

4! = 4 * 3 * 2 * 1 = 24

Hãy để chúng tôi mô phỏng mã bằng cách sử dụng ví dụ trên:

int fact(int n)
    {
        int result;
       if(n==0 || n==1)
         return 1;

       result = fact(n-1) * n;
       return result;
    }

Trong hầu hết các ngôn ngữ lập trình, chúng ta có những gì chúng ta gọi function stack. Nó giống như một cỗ bài, nơi mỗi thẻ được đặt ở phía trên thẻ kia - và mỗi thẻ có thể được coi là một hàm. fact:

Ngăn xếp cấp 1: fact(4) // n = 4 and is not equal to 1. So we call fact(n-1)*n 

Ngăn xếp cấp 2: fact(3) 

Ngăn xếp cấp 3: fact(2)

Ngăn xếp cấp 4: fact(1) // now, n = 1. vì vậy chúng ta trả về 1 từ hàm này.

trở về giá trị ...

Ngăn xếp cấp 3: 2 * fact(1) = 2 * 1 = 2

Ngăn xếp cấp 2: 3 * fact(2) = 3 * 2 = 6

Ngăn xếp cấp 1: 4 * fact(3) = 4 * 6 = 24

vì vậy chúng tôi có 24.

Lưu ý những dòng này:

result = fact(n-1) * n;
           return result;

hoặc đơn giản:

return fact(n-1) * n;

Điều này gọi chính hàm đó. Sử dụng 4 làm ví dụ,

Theo thứ tự theo ngăn xếp chức năng ..

return fact(3) * 4;
return fact(2) * 3 * 4
return fact(1) * 2 * 3 * 4

Thay thế kết quả ...

return 1 * 2 * 3 * 4 = return 24

Tôi hy vọng bạn có được điểm.


49
2017-11-18 13:57



Tôi nghĩ rằng bạn có nghĩa là / / n = 4 và không bằng 1. Không chắc chắn nơi 12 đến từ. - Gray
vâng .. chỉnh sửa .. cảm ơn .. - Neigyl R. Noval
Ý tôi là, giai thừa 4 = 4 * 3 * 2 * 1. Câu hỏi của tôi, lúc đầu tôi nghĩ giá trị 4 * 3 sẽ được lưu trong kết quả. - user907629
vâng .. nó sẽ được lưu trữ trong kết quả .. tuy nhiên, chúng tôi gọi chức năng một lần nữa, do đó, nó không phải là kết quả thực .. Kết quả đó sẽ được gọi khi chúng tôi đang trở về giá trị ... ACtually, đó là 4 * thực tế (3 ). Tuy nhiên, trên thực tế (3), chúng tôi cũng có 3 * thực tế (2). Trong thực tế (2), chúng tôi cũng có 2 * thực tế (1). Bây giờ chúng ta kết thúc trong thực tế (1) bởi vì n = 1. Vì vậy, chúng tôi trả về giá trị. 2 * 1, rồi 3 * 2 * 1 và cuối cùng là 4 * 3 * 2 * 1 - Neigyl R. Noval


Đây là một giải thích khác về cách thức tính giai thừa sử dụng đệ quy công trinh.

Hãy sửa đổi mã nguồn một chút:

int factorial(int n) {
      if (n <= 1)
            return 1;
      else
            return n * factorial(n - 1);
}

Đây là tính toán của 3! chi tiết:

enter image description here

Nguồn: RECURSION (Java, C ++) | Thuật toán và cấu trúc dữ liệu


15
2017-09-22 17:34





Sự nhầm lẫn của bạn, tôi tin rằng, xuất phát từ thực tế là bạn nghĩ rằng chỉ có một result biến, trong khi thực sự có result biến cho mỗi cuộc gọi hàm. Do đó, kết quả cũ không được thay thế, nhưng được trả lại.

ĐỂ TUYÊN BỐ:

int fact(int n)
{
    int result;

   if(n==1)
     return 1;

   result = fact(n-1) * n;
   return result;
}

Giả sử một cuộc gọi đến fact(2):

int result;
if ( n == 1 ) // false, go to next statement
result = fact(1) * 2; // calls fact(1):
|    
|fact(1)
|    int result;  //different variable
|    if ( n == 1 )  // true
|        return 1;  // this will return 1, i.e. call to fact(1) is 1
result = 1 * 2; // because fact(1) = 1
return 2;

Hy vọng nó rõ ràng hơn bây giờ.


9
2017-11-18 13:53



Ya, bạn có quan điểm của tôi. Bạn có thể vui lòng xây dựng. - user907629


Điều gì xảy ra là cuộc gọi đệ quy tự kết quả trong hành vi đệ quy hơn nữa. Nếu bạn viết nó ra, bạn sẽ nhận được:

 fact(4)
 fact(3) * 4;
 (fact(2) * 3) * 4;
 ((fact(1) * 2) * 3) * 4;
 ((1 * 2) * 3) * 4;

5
2017-11-18 13:58





public class Factorial {

    public static void main(String[] args) {
        System.out.println(factorial(4));
    }

    private static long factorial(int i) {

        if(i<0)  throw new IllegalArgumentException("x must be >= 0"); 
        return i==0||i==1? 1:i*factorial(i-1);
    }
}

5
2018-03-21 04:57



Xin vui lòng cho tôi biết lý do tại sao downvote? - SanA
có lẽ bởi vì bạn đã không giải thích bất cứ điều gì, nhưng tôi thích giải pháp của bạn và tôi đã upvoted. - another


Điểm mấu chốt mà bạn bỏ lỡ ở đây là biến "kết quả" là một biến ngăn xếp, và như vậy nó không nhận được "thay thế". Để xây dựng, mỗi khi thực tế được gọi, một biến MỚI được gọi là "kết quả" được tạo bên trong trong trình thông dịch và được liên kết với lời gọi đó của các phương thức. Điều này trái ngược với các trường đối tượng được liên kết với cá thể của đối tượng và không phải là một cuộc gọi phương thức cụ thể


2
2017-11-18 13:54





Mặc dù đây là cũ, nó vẫn tiếp tục lên khá tốt trong google. Vì vậy, tôi figured tôi muốn đề cập đến điều này. Không ai đề cập đến khi kiểm tra x = 0.

0! và 1! cả hai = 1.

Điều này không được kiểm tra với các câu trả lời trước đó, và sẽ gây ra tràn ngăn xếp, nếu thực tế (0) được chạy. Dù sao sửa chữa đơn giản:

public static int fact(int x){
    if (x==1 | x==0)
        return 1;
    return fact(x-1) * x;
}// fact

1
2017-09-29 02:48





Một giải pháp đệ quy sử dụng toán tử bậc ba.

public static int fac(int n) {
    return (n < 1) ? 1 : n*fac(n-1);
}

1
2018-05-06 17:55



return n == 1 || n == 0? 1: n * fac (n - 1); - ggb667
return (n <= 1)? 1: n * thực tế (n-1) - Alican Balik


Theo ý kiến ​​của tôi, và đó là ý kiến ​​của một ai đó với kiến ​​thức cấp độ mới bắt đầu của java, tôi sẽ đề nghị rằng n == 1 được thay đổi thành n <= 1 hoặc (n == 0) || (n == 1) bởi vì giai thừa của 0 là 1.


0
2018-03-30 20:28