Một hàm được gọi là đệ quy nếu bên trong thân nó có một lời gọi đến chính nó. Nghe có vẻ vô lý nhỉ ? Một hàm làm sao có thể gọi nó mãi được, vì nếu như vậy sẽ sinh ra một vòng lặp vô tận. Nhưng trong thực tế, một hàm đệ quy luôn có điều kiện đừng được gọi là “điểm neo”. Khi đạt tới điểm neo, hàm sẽ không gọi chính nó nữa.
Cú pháp tổng quát:
void tenhamdequi()
{
tenhamdequi(); /* goi chinh no */
}
int main()
{
tenhamdequi();
}
Hàm đệ quy không thể gọi tới nó mãi, cần phải có một điểm dừng (còn gọi là điểm neo) tại một trường hợp đặc biệt, gọi là trường hợp suy biến (degenerate case).
Thành phần của một hàm đệ quy
Hàm đệ quy gồm 2 phần:
- Phần cơ sở: Điều kiện thoát khỏi đệ quy
- Phần đệ quy: Thân hàm có chứa lời gọi đệ quy
Thiết kế giải thuật đệ quy
Thực hiện 3 bước sau:
- Tham số hóa bài toán
- Phân tích trường hợp chung: Đưa bài toán về bài toán nhỏ hơn cùng loại, dần dần tiến tới trường hợp suy biến
- Tìm trường hợp suy biến
Ưu và nhược điểm
Giải thuật đệ quy có ưu điểm là thuận lợi cho việc biểu diễn bài toán, đồng thời làm gọn chương trình. Tuy nhiên cũng có nhược điểm, đó là không tối ưu về mặt thời gian (so với sử dụng vòng lặp), gây tốn bộ nhớ.
Ví dụ tính giai thừa của N dùng đệ quy:
#include <stdio.h>
int giathua(int n)
{
if (n<0)
return -1;
if(n==0)
return 1;
return (n*giathua(n-1));
}
int main()
{
int x=0;
x = giathua(5);
printf("\n Giai thua cua 5 la %d",x);
return 0;
}
Hàm trên hoạt động như hình sau:
