Java - Đệ quy phân tích bài toán tính giai thừa(Factorial).

Để tiếp tục hiểu rõ hơn về tính đệ quy trong lập trình ta tiếp tục phân tích một bài toán có tính chất đệ quy là tính giai thừa.

Để hiểu bài viết trước tiên bạn cần tìm hiểu đệ quy là gì, bạn thể xem bài viết đệ quy tại blog.vnlives.net







Đầu tiên ta sẽ phân tích khai miện của giai thừa để hiểu rõ giai thừa là gì?

Thừa số được định nghĩa bởi một số nguyên dương theo sau bởi dấu chấm than(ví dụ: 8!).

Giá trị của giai thừa là tích số của tất cả các số từ 1 đến số đã cho của thừa số. Như vậy ta sẽ không có trường hợp 0 giai thừa hoặc có thể hiểu 0! = 1.

Ví dụ 8! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 40320

Giai thừa thường được sử dụng trong xác định tổ hợp, hoán vị và xác xuất.

Dựa vào định nghĩa trên ta có thể phân tích tính đệ quy như sau:

• Giai thừa của 1! là 1 (Trường hợp cơ bản)
• Giai thừa của 2! là 1 * 2 (Trường hợp đệ quy)
• Giai thừa của 3! là 1 * 2 * 3 (Trường hợp đệ quy)

Hoặc bạn có thể định nghĩa như sau:

• Giai thừa của 1! là 1 (Trường hợp cơ bản)
• Giai thừa của 2! là 1! * 2 (Trường hợp đệ quy)
• Giai thừa của 3! là 2! * 3 (Trường hợp đệ quy)

Như phân tích trên tra thấy giai thừa của 2 sử dụng lại định nghĩa của giai thừa thừa 1 và giai thừa của 3 thì sử dụng lại giai thừa của 2, từ đây ta suy ra được phép tính giai thừa có tính chất đệ quy.

Bây giờ đề bài đặt ra là viết một chương trình tính giai thừa của một số bất kỳ được nhập vào bằng phương pháp đệ quy.

Như trong phân tích trên giá trị của giai thừa 2 được định nghĩa bằng cách lấy giá trị của giai thừa 1 nhân cho 2(chính bản thân giá trị của giai thừa) và tương tự giá trị của giai thừa 3 được lấy giá trị của giá trị 2 và nhân cho 3(chính bản thân giá trị của giai thừa).

Dựa trên nhưng định nghĩa và phân tích trên trên ta có thể phân tích ra được thuật toán tính n giai thừa bằng đệ quy như sau:

Bây giờ ta sẽ áp dụng công thức vào lập trình Java như sau:

/**
 * @(#)TinhGiaiThua.java
 *
 * TinhGiaiThua application
 *
 * @author VNLIVES.NET
 * @version 1.00 2013/9/23
 */

public class TinhGiaiThua {
   
    public static void main(String[] args) {
       
        // TODO, add your application code
        System.out.println("Giai thua cua 1 la :" + tong_giai_thua(1));
        System.out.println("Giai thua cua 2 la :" + tong_giai_thua(2));
        System.out.println("Giai thua cua 3 la :" + tong_giai_thua(3));
        System.out.println("Giai thua cua 4 la :" + tong_giai_thua(4));
        System.out.println("Giai thua cua 5 la :" + tong_giai_thua(5));
        System.out.println("Giai thua cua 6 la :" + tong_giai_thua(6));
        System.out.println("Giai thua cua 7 la :" + tong_giai_thua(7));
        System.out.println("Giai thua cua 8 la :" + tong_giai_thua(8));
       
    }
   
    public static int tong_giai_thua(int n) {
        if (n == 1) {
            return 1;
        }
        return tong_giai_thua(n-1) * n;
    }
}

Sau khi thực thi chương trình ta sẽ được kết quả như sau:

Giai thua cua 1 la :1
Giai thua cua 2 la :2
Giai thua cua 3 la :6
Giai thua cua 4 la :24
Giai thua cua 5 la :120
Giai thua cua 6 la :720
Giai thua cua 7 la :5040
Giai thua cua 8 la :40320

Khiếp viết xong đọc lại thấy cũng chả hiểu ra làm sao? Mà cũng chả biết viết lại như thế nào, thôi thì chỗ nào không hiểu các bạn comment lại mình phát rùi mình chỉnh sửa lại sau.