Khái niệm cơ bản về đệ qui (Recursion)
Đệ qui (Recursion) là gì?
Một số ngôn ngữ lập trình cho phép việc một module hoặc một hàm được gọi tới chính nó. Kỹ thuật này được gọi là Đệ qui (Recursion). Trong đệ qui, một hàm a có thể: gọi trực tiếp chính hàm a này hoặc gọi một hàm b mà trả về lời gọi tới hàm a ban đầu. Hàm a được gọi là hàm đệ qui.
Ví dụ: một hàm gọi chính nó
int function(int value) { if(value < 1) return; function(value - 1); printf("%d ",value); }
Ví dụ: một hàm mà gọi tới hàm khác mà trả về lời gọi tới hàm ban đầu
int function(int value) { if(value < 1) return; function(value - 1); printf("%d ",value); }
Đặc điểm của hàm đệ qui
Một hàm đệ qui có thể tiếp tục diễn ra vô số lần giống như một vòng lặp vô hạn. Để tránh điều này, bạn phải ghi nhớ hai thuộc tính sau của hàm đệ qui:
Điều kiện cơ bản: phải có ít nhất một điều kiện để khi mà gặp điều kiện này thì việc gọi chính hàm đó (gọi đệ qui) sẽ dừng lại.
Tiệm cận: mỗi khi hàm đệ qui được gọi thì nó càng tiệm cận tới điều kiện cơ bản.
Sự triển khai hàm đệ qui
Nhiều ngôn ngữ lập trình triển khai sự đệ qui theo cách thức của các ngăn xếp (stack). Nói chung, mỗi khi một hàm (hàm gọi – caller) gọi hàm khác (hàm được gọi – callee) hoặc gọi chính nó (callee), thì hàm caller truyền điều khiển thực thi tới callee. Tiến trình truyền này cũng có thể bao gồm một số dữ liệu từ caller tới callee.
So sánh đệ qui và vòng lặp
Ai đó có thể nói rằng tại sao lại sử dụng đệ qui trong khi sử dụng vòng lặp cũng có thể làm được các tác vụ tương tự. Lý do đầu tiên là đệ qui làm cho chương trình dễ đọc hơn và với các hệ thống CPU cải tiến ngày nay thì đệ qui là hiệu quả hơn rất nhiều khi so với các vòng lặp.
Độ phức tạp thời gian (Time complexity) của hàm đệ qui
Với vòng lặp, chúng ta lấy số vòng lặp để tính độ phức tạp thời gian. Tương tự với đệ qui, giả sử mọi thứ là hằng số, chúng ta tính thời gian một lời gọi đệ qui được tạo ra. Một lời gọi được tạo ra tới một hàm sẽ là Ο(1), Do đó với n là thời gian một lời gọi đệ qui được tạo ra thì độ phức tạp thời gian hàm đệ qui sẽ là Ο(n).
Độ phức tạp bộ nhớ (Space complexity) của hàm đệ qui
Độ phức tạp bộ nhớ được ước lượng dựa vào lượng bộ nhớ cần thêm cho một module được thực thi. Với vòng lặp, trình biên dịch hầu như không cần thêm bộ nhớ. Trình biên dịch sẽ tự cập nhật giá trị của biến được sử dụng ngay trong vòng lặp. Nhưng với đệ qui, hệ thống cần lưu giữ các bản ghi động mỗi khi một lời gọi đệ qui được tạo. Do đó có thể nói rằng, độ phức tạp bộ nhớ của hàm đệ qui là cao hơn so với vòng lặp.
Theo Tutorialspoint
Bài trước: Cấu trúc dữ liệu Heap
Bài tiếp: Bài toán Tháp Hà Nội (Tower of Hanoi)
Bạn nên đọc
-
Cách viết file README tốt nhất
-
Công thức tính thể tích khối trụ và ví dụ minh họa
-
Công thức tính thể tích hình chóp cụt, diện tích xung quanh và toàn phần của hình chóp cụt
-
Các công thức đạo hàm và đạo hàm lượng giác đầy đủ nhất
-
Công thức tính diện tích xung quanh hình nón cụt, diện tích toàn phần hình nón cụt, thể tích hình nón cụt
-
Công thức tính diện tích xung quanh hình nón, diện tích toàn phần hình nón, thể tích hình nón, V nón

- Code NgầuThích · Phản hồi · 4 · 17/08/20

Cũ vẫn chất
-
Lời cảm ơn, tri ân thầy cô hay và xúc động
Hôm qua 1 -
Các công thức đạo hàm và đạo hàm lượng giác đầy đủ nhất
Hôm qua -
Thơ về hoa sen, câu nói về hoa sen hay và ý nghĩa
Hôm qua -
5 cách lấy kim cương miễn phí trong Free Fire
Hôm qua 3 -
Các câu lệnh trong Logo đầy đủ nhất 2025
Hôm qua 32 -
Công thức tính diện tích xung quanh hình nón cụt, diện tích toàn phần hình nón cụt, thể tích hình nón cụt
Hôm qua -
Code All Star Tower Defense 08/02/2025 mới nhất, đổi gems và stardust
Hôm qua 3 -
Công thức tính diện tích xung quanh hình nón, diện tích toàn phần hình nón, thể tích hình nón, V nón
Hôm qua -
Một vạn bằng bao nhiêu?
Hôm qua 4 -
Cách điều chỉnh kích thước ô trong bảng Word bằng nhau
Hôm qua