Đệ quy

Hàm đệ quy gọi lại chính nó trên bài toán nhỏ hơn. Cần có điều kiện dừng và mỗi lần gọi phải tiến về điều kiện đó. Các lời gọi chưa hoàn thành nằm trên , vì vậy đệ quy quá sâu có thể vượt ngăn xếp.

Lĩnh vực: Giải thuật & cấu trúc dữ liệu

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Bài giảng dùng khái niệm này

• Thuật toán sắp xếpCTDL & Giải thuật
• Cây & cây nhị phânCTDL & Giải thuật

Giải thích kỹ thuật

Hai yêu cầu kết thúc. Có ít nhất một trường hợp cơ sở, và mọi nhánh lời gọi phải tiến về trường hợp cơ sở. Một hàm có câu lệnh dừng nhưng nhánh khác gọi lại với cùng tham số vẫn có thể không kết thúc.

Để phân tích, viết quan hệ truy hồi của số bước và độ sâu . Chứng minh bằng thường đi cùng cấu trúc đệ quy.

Ví dụ

factorial(n) = n × factorial($n-1$), với factorial(0) = 1. Từ $n=3$, ta lần lượt về 2, 1, 0.

Khi nào cần dùng?

Hiểu DFS, chia để trị, quay lui và chứng minh bằng .

Câu hỏi ôn lại

Nếu hàm cứ gọi lại với cùng n và không dừng, chuyện gì xảy ra?

Xem đáp án

Lời gọi tiếp tục tăng tới khi vượt hoặc tài nguyên.

Thuật ngữ liên quan

• Ngăn xếp
• Quy nạp toán học
• Cây
• Độ phức tạp