Hàm tính tổng trong Javascript
Đây chỉ là ví dụ minh họa về hàm đệ quy trong JavaScript. Thực tế, bạn có thể sử dụng vòng lặp 4 để giải quyết bài toán trên: Show
Kết quả hoàn toàn tương đương. Tuy nhiên, có rất nhiều trường hợp việc sử dụng hàm đệ quy lại giúp code trở nên ngắn gọn, rõ ràng và dễ bảo trì hơn sử dụng vòng lặp. Vì vậy, mình hãy cùng tìm hiểu về hàm đệ quy trong JavaScript để biết cách áp dụng khi cần thiết. Các thành phần cơ bản của hàm đệ quyHàm đệ quy nói chung và hàm đệ quy trong JavaScript nói riêng, có hai thành phần đặc trưng:
Cũng tương tự như điều kiện để thoát vòng lặp, nếu không có điều kiện cơ sở thì hàm đệ quy sẽ không bao giờ dừng lại (đệ quy vô hạn), dẫn đến tràn stack. Ví dụ bỏ qua điều kiện cơ cở của hàm đệ quy trên:
Kết quả là Hello world! được in ra khoảng hơn 5 lần thì bị lỗi tràn stack, cụ thể: Uncaught RangeError: Maximum call stack size exceeded.Kết quả Hello world! Hello world! ... Hello world! Uncaught RangeError: Maximum call stack size exceeded
Call stack là gì?
Khi gọi hàm, JavaScript Engine đưa các lời gọi hàm vào trong một ngăn xếp.
Việc lưu lời gọi hàm vào ngăn xếp là tốn bộ nhớ. Vì vậy, JavaScript Engine sẽ giới hạn kích thước của ngăn xếp (khoảng 5 hoặc hơn, tùy thuộc vào engine).Khi sử dụng hàm đệ quy trong JavaScript, bạn cần chú ý đến điều kiện cơ sở để thoát đệ quy, tránh đệ quy vô hạn dẫn đến tràn stack như ví dụ trên. Sử dụng hàm đệ quy khi nào?Khi một bài toán có thể chia ra thành nhiều bài toán con và bài toán con có dạng tương tự như bài toán cha thì bạn có thể sử dụng hàm đệ quy. Ví dụ bài toán tính giá trị của lũy thừa 8 (a mũ b) với định nghĩa toán học là:
Theo định nghĩa trên, bài toán cha là tính 8 lại dựa trên bài toán con 0. Vì vậy, bạn có thể áp dụng hàm đệ quy để tính giá trị 8 như sau:
So sánh hàm đệ quy và vòng lặpBài toán tính lũy thừa trên có thể giải quyết bằng cách sử dụng vòng lặp:
Đa số các bài toán có thể sử dụng hàm đệ quy thì đều có thể giải bằng cách sử dụng vòng lặp. Tùy thuộc vào yêu cầu của từng bài toán mà bạn lựa chọn cách làm phù hợp: |