Sự khác biệt cốt lõi giữa đệ quy tuyến tính (Linear Recursion) và đệ quy phi tuyến tính / đệ quy cây (Tree Recursion) trong việc quản lý tài nguyên hệ thống là gì?

Question

Accepted Answer

Bản chất vấn đề

Đệ quy tuyến tính: Trong mỗi lời gọi hàm chỉ có tối đa một lời gọi đệ quy chính nó (ví dụ: tính giai thừa). Số lượng khung nhớ trên Call Stack tăng trưởng tuyến tính O(n).
Đệ quy cây (Tree Recursion): Trong mỗi lời gọi hàm có từ hai lời gọi đệ quy trở lên (ví dụ: duyệt cây nhị phân, tính Fibonacci). Số lượng khung nhớ và số nhánh thực thi tăng trưởng theo cấp số nhân O(2^n).

Lưu ý cho Junior
Khi phỏng vấn, lập trình viên cần nhận thức rõ rằng đệ quy cây cực kỳ nguy hiểm nếu độ sâu của cây lớn, vì nó tạo ra số lượng nhánh và lời gọi hàm khổng lồ, dễ làm cạn kiệt bộ nhớ RAM và CPU của máy chủ.
Ví dụ đệ quy cây
function treeSum(node) {
    if (!node) return 0;
    return node.value + treeSum(node.left) + treeSum(node.right);
}

Sự khác biệt cốt lõi giữa đệ quy tuyến tính (Linear Recursion) và đệ quy phi tuyến tính / đệ quy cây (Tree Recursion) trong việc quản lý tài nguyên hệ thống là gì?

Bản chất vấn đề

Lưu ý cho Junior

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi recursion liên quan cùng chủ đề