Giai thừa¶
Yêu cầu¶
Sử dụng kỹ thuật đệ quy, viết chương trình tính
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:
Theo công thức trên:
-
Trường hợp cơ sở là
n == 0
hoặcn == 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
. -
Trường hợp đệ quy là các giá trị
còn lại. (Giả sử ta không nhậpn
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 , rồi nhân thêm .Ví dụ:
Để tính , hàm đệ quy sẽ gọi lại chính nó để tính , rồi nhân thêm .Phân tích cụ thể:
- Hàm
factorial(5)
sẽ gọi đệ quy hàmfactorial(4)
. - Hàm
factorial(4)
sẽ gọi đệ quy hàmfactorial(3)
. - Hàm
factorial(3)
sẽ gọi đệ quy hàmfactorial(2)
. - Hàm
factorial(2)
sẽ gọi đệ quy hàmfactorial(1)
. - Hàm
factorial(1)
không gọi đệ quy nữa, mà sẽ trả về giá trị là 1.
- Hàm
Như vậy, hàm factorial
được viết như sau:
Mã nguồn¶
-
Chương trình C++ hoàn chỉnh đặt tại Gist của GitHub
-
Chương trình Python hoàn chỉnh đặt tại Google Colab