Đệ quy – ngăn xếp lời gọi và cây lời gọi

Thuộc chủ đề Giải quyết vấn đề với sự trợ giúp của máy tính (Tin học 12), gắn với kĩ thuật đệ quy. Trình mô phỏng chạy thật các hàm đệ quy – giai thừa, Fibonacci, tổng danh sách, tìm kiếm nhị phân, tháp chuyển đĩa và sắp xếp trộn – và ghi lại mọi lời gọi: mỗi lời gọi đẩy một khung lên ngăn xếp, trường hợp cơ sở trả về mà không gọi tiếp, rồi các khung lần lượt được lấy ra khi giá trị trả về đi ngược lên. Học sinh chọn hàm, đặt n rồi bấm Bước tiếp hoặc Chạy để xem ngăn xếp lời gọi lớn dần rồi rút lại, cây lời gọi phân nhánh, dòng mã đang chạy và biểu thức khai triển. Bật Ghi nhớ để thấy Fibonacci có ghi nhớ chỉ cần số lời gọi tăng tuyến tính thay vì tăng theo hàm mũ; bỏ trường hợp cơ sở để thấy tràn ngăn xếp. Biểu đồ và bảng so sánh số lời gọi và độ sâu ngăn xếp của bản đệ quy với số vòng lặp của bản dùng vòng lặp, viết bằng Python hoặc mã giả. Câu hỏi gợi ý: – Tính fib(6) không ghi nhớ thì fib(2) được gọi bao nhiêu lần? Có ghi nhớ thì sao? – factorial(5) làm ngăn xếp lời gọi sâu nhất bao nhiêu khung? Bản dùng vòng lặp cần bao nhiêu? – Vì sao bỏ trường hợp cơ sở lại gây tràn ngăn xếp chứ không cho ra kết quả sai?