Khái niêm chung về đệ quy C không những cho phép hàm này gọi tới hàm khác, mà nó còn cho phép từ một điểm trong thân của một hàm gọi chính hàm đó. Hàm như vậy gọi là đệ quy. Vậy một chương trình sẽ chạy thế nào nếu như áp dụng đệ quy ? Cùng tham khảo ở phần dưới đây nhé Cách dùng đệ quy Phương pháp đệ quy thường áp dụng cho các bài toán phụ thuộc tham số có 2 đặc điểm sau : Các ví dụ về đệ quy
Mục này sẽ trình bày một số ví dụ đơn giản nhằm minh họa một cách dễ hiểu hàm đệ quy
Ví dụ 1 : Xét bài toán tìm USCLN của 2 số nguyên dương a,b+ Trường hợp suy biến là trường hợp a=b USCLN[a,b]=a. + Trường hợp x khác y thì có thể đệ quy như sau :USCLN[a,b]=USCLN[a-b,b] nếu a>b USCLN[a,b]=USCLN[a,b-a] nếu a1, hàm sẽ trả về n*Giaithua[n-1]. Chẳng hạn ta cho n nhận giá trị là 3, chương trình sẽ thực thi như sau:
Vậy mục đích của hàm đệ quy là chia vấn đề thành những vấn đề nhỏ hơn cho đến lúc đạt được điều kiện cơ bản. Lưu ý quan trọng khi dùng đệ quy là bắt buộc phải có điều kiện dừng, nếu không có thì sẽ làm hàm gọi hàm liên tục không có điểm dừng và dẫn đến chương trình không thể kết thúc được.
II. Cách Sử Dụng Đệ Quy Trong C++
Trong C++, một hàm gọi chính nó ta gọi đó là hàm đệ quy, nghĩa là trong thân hàm sẽ gọi đến chính tên hàm hiện tại và truyền đúng những tham số mà hàm đã khai báo.
Cú pháp: Cú pháp của hàm đệ quy trong C++ như sau:
HamDeQuy[]{ HamDeQuy[]; //goi lai chinh no }Ví dụ: Chúng ta cùng xem một ví dụ đơn giản về hàm đệ quy trong C++ đó là tính giai thừa của một số nguyên.
Trước khi giải bài toán tính giai thừa của một số nguyên trong C++ chúng ta cùng nhớ lại công thức tính giai thừa trong toán học trước đã nhé.
Theo định nghĩa giai thừa ta có:
- 0! = 1
- n! = 1 * 2 * 3 * … * n
Vậy là ta đã có công thức tính giai thừa của một số nguyên rồi. Nếu n = 0 thì giai thừa bằng 1. Nếu n > 0 thì giai thừa sẽ là tích từ 1 đến n. Và không có giai thừa của số âm.
Giải bằng vòng lặp For
Trước khi đi vào giải bài toán trên bằng hàm đệ quy, mình sẽ giải bằng vòng lặp for trong C++ trước nhé.
Ví dụ
#include using namespace std; int main[] { int n; while[true] { int giaithua = 1; cout > n; //Nhap n nho hon 0 de thoat khoi vong lap if[n < 0] { cout