bài này tui xài đệ quy đuôi (tail recursive), bạn mới học nếu chưa biết đệ quy đuôi là gì thì google tìm hiểu thêm (dễ hiểu lắm), ở đây tui giải thích đại khái thôi, đó là truyền kết quả tính được từ lần gọi trước cho lần gọi sau thông qua tham số hàm, hàm lúc này sẽ có thêm 1 tham số phụ, giống cái dq(n, a) của bạn ở trên thì a chính là tham số phụ để truyền giữa các lần gọi đệ quy đó
giờ phân tích thử bài này, tui thử cách đặt nhân tử chung để coi có thể tính được các cụm nhân theo từng bước hay không
s = 1 + 1.2 + 1.2.3 + 1.2.3......n
nếu đặt 1 là nhân tử chung thì sẽ được
1(1 + 2 + 2.3 + 2.3......n)
tiếp tục đặt 2 là nhân tử chung thì được
1(1 + 2(1 + 3 + 3......n))
tiếp tục đặt 3 là nhân tử chung
1(1 + 2(1 + 3(1 + ......n)))
cứ đặt như vậy cuối cùng sẽ thành ra
1(1 + 2(1 + 3(1 + ............ (n - 1).(1 + n)
xong, quy luật giờ quá dễ thấy, nếu viết hàm đệ quy có n giảm dần thì
1/tại mỗi lần gọi ta tính 1 + n*kết quả từ lần gọi trước, xong truyền cái kết quả này cho lần gọi sau, tiếp tục như vậy cho tới khi n <= 1
2/ở lần gọi đầu tiên, do kết quả trước đó chưa có nên chỉ là 1 + n thôi
viết thành code
C:
unsigned int tinh(int n, unsigned int kq_tu_lan_goi_truoc = 1)
{
if(n <= 1)
return kq_tu_lan_goi_truoc;
tinh(n - 1, n*kq_tu_lan_goi_truoc + 1);
}
vài lưu ý
1/ở lần gọi đầu tiên thì kết quả trước đó chưa có nên phải gán giá trị mặc định cho biến kq_tu_lan_goi_truoc là 1
2/kết quả thường rất lớn nên bạn nhớ cho kiểu trả về của hàm lớn lớn chút, chẳng hạn như long long int hay gì đó
xong rồi, test thôi, ở đây tui viết luôn 1 cái hàm thường tính bằng vòng lặp để so sánh
thử n = 5, kết quả = 153
thử n = 8, kết quả = 46233
tạm như vậy, chưa nghĩ ra cách nào hay hơn
