Skip to content

Giai thừa

Yêu cầu

Sử dụng kỹ thuật đệ quy, viết chương trình tính n!, biết rằng 0!=11!=1.

Input

Số nguyên dương n.

Output

Giai thừa của n.

Bộ test

STT Input Output
1 0 1
2 1 1
3 5 120
4 21 51090942171709440000

Cách giải đề xuất

Ta có công thức truy hồi tính giai thừa như sau:

n!={1nếu n=0 hoặc n=1(n1)!×nnếu n>1

Theo công thức trên:

  1. Trường hợp cơ sở là n == 0 hoặc n == 1.

    Với trường hợp này, hàm đệ quy không cần gọi đệ quy nữa, mà chỉ trả về giá trị là 1.

  2. Trường hợp đệ quy là các giá trị n còn lại. (Giả sử ta không nhập n nguyên âm).

    Với trường hợp này, hàm đệ quy sẽ gọi lại chính nó, tham số truyền vào là n - 1 để tính (n1)!, rồi nhân thêm n.

    Ví dụ:
    Để tính 5!, hàm đệ quy sẽ gọi lại chính nó để tính (51)!=4!, rồi nhân thêm 5.

    Phân tích cụ thể:

    • Hàm factorial(5) sẽ gọi đệ quy hàm factorial(4).
    • Hàm factorial(4) sẽ gọi đệ quy hàm factorial(3).
    • Hàm factorial(3) sẽ gọi đệ quy hàm factorial(2).
    • Hàm factorial(2) sẽ gọi đệ quy hàm factorial(1).
    • Hàm factorial(1) không gọi đệ quy nữa, mà sẽ trả về giá trị là 1.

Như vậy, hàm factorial được viết như sau:

1
2
3
4
5
6
7
def factorial(n):
    # Trường hợp cơ sở
    if n == 0 or n == 1:
        return 1

    # Trường hợp đệ quy
    return factorial(n - 1) * n

Mã nguồn

🛖