Hiểu Đệ quy & Ghi nhớ qua JavaScript
Trong bài viết này, bạn sẽ tìm hiểu cách sử dụng lập trình đệ quy, nó là gì và cách tối ưu hóa nó để sử dụng trong các thuật toán. Ta sẽ sử dụng JavaScript làm ngôn ngữ lập trình mà ta lựa chọn để hiểu khái niệm đệ quy.
Yêu cầu
Tôi sẽ sử dụng Ký hiệu Big O để so sánh các chiến lược tối ưu hóa mà bạn có thể tìm hiểu tại đây .
Đệ quy là gì?
Đệ quy là bất kỳ lúc nào một hàm tự gọi bên trong chính nó, có khả năng tạo ra một vòng lặp vô hạn. Nếu bạn đã từng làm việc với hình ảnh động vải sau đó bạn đã sử dụng đệ quy vì ta sử dụng một animate chức năng cập nhật hình ảnh động của ta trước khi chạy lại chính nó.
Trong ví dụ dưới đây, ta đang chuyển một số, nhân đôi nó, sau đó chuyển lại giá trị đó cho chính nó. Về lý thuyết, điều này sẽ tiếp tục mãi mãi nhưng vì máy tính có giới hạn nên ta thường không thể có đệ quy vô hạn. Bạn sẽ gặp lỗi như too much recursion hoặc Maximum call stack size exceeded nếu bạn không bao gồm một số điều kiện thoát để dừng chức năng, trong trường hợp sau ngay khi nó vượt quá 100:
const double = num => {
num = num + num;
console.log(num);
if (num > 100) return 'Exit'; // Try removing this
return double(num);
};
console.log(double(4));
Có thể bạn đang nghĩ, “Điều đó thật tuyệt, nhưng tôi không thể chỉ sử dụng một vòng lặp cho bất cứ điều gì mà đệ quy có thể làm được?”. Vâng, có, nhưng thực sự là không. Đệ quy có ích khi xử lý các thuật toán tìm kiếm và sắp xếp khác nhau hoặc duyệt qua các cấu trúc dữ liệu phức tạp hơn danh sách đơn giản. Khi thực hiện đúng, bạn cũng có thể nhận được hiệu suất tốt hơn nhiều, như O (log n) trong khi tất cả các vòng lặp là O (n).
Ghi nhớ
Bạn không cần phải chơi với đệ quy quá lâu để nhận ra rằng nó khá dễ làm máy tính của bạn bị áp đảo. Điều này là do hầu hết các hàm đệ quy là O (n ^ 2) hoặc thậm chí là O (n!). Vì JavaScript chạy trên các ngăn xếp cuộc gọi mỗi khi một lớp đệ quy mới được thêm vào, rất nhiều bộ nhớ và sức mạnh xử lý phải được sử dụng để quản lý tất cả, mặc dù phần lớn nó là dư thừa.
Hãy thử một cái gì đó đơn giản như tạo một chuỗi fibonacci. Một dãy fibonacci là nơi mỗi chữ số là tổng của hai mục trước nó, 0, 1, 1, 2, 3, 5, 8, 12…
const fibonacci = num => {
if (num < 2) return num;
return fibonacci(num - 1) + fibonacci(num - 2);
};
for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 3 minutes before page crashed...
Thật là kinh khủng. Sử dụng hết tài nguyên cho 1.000 lớp thông tin giống nhau là quá nhiều ngay cả đối với máy tính tương đối, khá của tôi.
Thay vào đó, ta có thể giải quyết vấn đề này bằng cách thêm một biến lưu trữ, hoặc “bản ghi nhớ”, sẽ chứa các giá trị của ta khi ngăn xếp tiến triển. Mỗi khi hàm của ta chạy, giá trị của nó sẽ được thêm vào index tương ứng của nó trong bản ghi nhớ và lớp tiếp theo sẽ tham chiếu đến nó để tính toán kết quả của ta .
const fibonacci = (num, memo) => {
memo = memo || {};
if (memo[num]) return memo[num];
if (num < 2) return num;
return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);
};
for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 143 Milliseconds
Vấn đề
Hãy thử áp dụng điều này cho một hàm đệ quy khác. Điều này nhận một số và xuất ra giai thừa của nó, vì vậy 3! nên trả về 6 vì 3x2x1 = 6.
const factorial = n => {
let num = n;
if (n === 0) return 1;
for (let i = 0; i < n; i++) {
num = n * factorial(n - 1);
};
return num;
};
console.log(factorial(3)); // 7 Milliseconds
console.log(factorial(6)); // 8 Milliseconds
console.log(factorial(9)); // 15 Milliseconds
console.log(factorial(12)); // 11,588 Milliseconds
Đối với tôi, bất kỳ thứ gì trên 12 đều làm hỏng trang bởi vì hàm này có độ phức tạp là O (n!) Vì mỗi lớp trong ngăn xếp phải xử lý độ phức tạp của lớp trước nó.
Thay vào đó, hãy thử ghi nhớ nó và xem sự khác biệt.
const factorial = (n, memo) => {
memo = memo || {};
if (memo[n]) return memo[n];
if (n === 0) return 1;
for (let i = 0; i < n; i++) {
memo[n] = n * factorial(n - 1, memo);
};
return memo[n];
};
console.log(factorial(12)); // 4 milliseconds
console.log(factorial(120)); // 12 milliseconds
console.log(factorial(1200)); // 24 milliseconds
console.log(factorial(12000)); // 1408 milliseconds
Tôi không biết bạn thế nào, nhưng tôi nghĩ đó là một sự cải tiến đáng kinh ngạc, nó hiện có thể xử lý 10.000 lần các phép tính trong 1/8 thời gian.
Bớt tư tưởng
Đệ quy là một trong những thứ bạn cần phải thực hiện rất thoải mái vì nó sẽ quay trở lại nhiều lần hoặc ám ảnh bạn trong suốt sự nghiệp lập trình của bạn. Nó sẽ rất cần thiết cho việc học cách duyệt qua các cây và danh sách cũng như sắp xếp các tập dữ liệu khác nhau trong tương lai.
Các tin liên quan
Đọc và xử lý tệp với API JavaScript FileReader2020-01-23
Tìm hiểu ký hiệu Big O qua JavaScript
2020-01-20
Cách sử dụng API BroadcastChannel trong JavaScript
2020-01-13
Đa năng hóa chuỗi trong JavaScript bằng Simplur
2020-01-10
Hướng dẫn nhanh về phương pháp đối sánh chuỗi trong JavaScript
2020-01-07
Tham quan API quyền JavaScript
2020-01-05
V8 của V8: Chuỗi liên kết tùy chọn và kết hợp Nullish trong JavaScript
2019-12-29
Phân tích cú pháp, xác thực, thao tác và hiển thị ngày và giờ trong JavaScript với Day.js
2019-12-28
Cách bắt đầu với API hiệu suất JavaScript
2019-12-25
Xem xét tất cả 13 bẫy proxy JavaScript
2019-12-19
