Đệ quy là một kỹ thuật được sử dụng để giải quyết các sự cố máy tính bằng cách tạo một hàm gọi chính nó cho đến khi chương trình của bạn đạt được kết quả mong muốn.
Hướng dẫn này sẽ giúp bạn tìm hiểu về đệ quy và so sánh nó với vòng lặp phổ biến hơn.
Đệ quy là gì?
Giả sử bạn có một hàm ghi lại các số từ 1 đến 5. Đây là cách bạn viết hàm đó bằng cách sử dụng đệ quy:
function log(num){
if(num > 5){
return;
}
console.log(num);
log(num + 1);
}
log(1);Khi bạn chạy đoạn mã trên, log chức năng sẽ chỉ gọi chính nó miễn là giá trị của num biến nhỏ hơn 5.
Một hàm đệ quy phải có ít nhất một điều kiện trong đó nó sẽ ngừng gọi chính nó hoặc hàm sẽ tự gọi nó vô thời hạn cho đến khi JavaScript đưa ra lỗi.
Điều kiện ngăn một hàm đệ quy gọi chính nó được gọi là trường hợp cơ sở. bên trong log chức năng trên, trường hợp cơ sở là khi num lớn hơn 5.
Tại sao bạn không sử dụng một vòng lặp?
Bất kỳ vấn đề nào bạn có thể giải quyết bằng cách sử dụng hàm đệ quy sẽ luôn có giải pháp vòng lặp thay thế. Ví dụ trên có thể được thay thế bằng đoạn mã sau:
for(let i = 1; i <= 5; i++){
console.log(i);
}Các ngôn ngữ lập trình hiện đại như JavaScript đã có for và while các câu lệnh thay thế cho các hàm đệ quy. Nhưng một số ngôn ngữ như Clojure không có bất kỳ câu lệnh lặp nào, vì vậy bạn cần sử dụng đệ quy để thực thi lặp lại một đoạn mã.
Vừa là for vòng lặp yêu cầu bạn biết bạn sẽ lặp lại việc thực thi mã bao nhiêu lần. Nhưng một hàm đệ quy và một while vòng lặp có thể được sử dụng để thực thi một đoạn mã mà không cần biết bạn cần lặp lại bao nhiêu lần. Bạn chỉ cần biết điều kiện dừng thực thi.
Ví dụ: giả sử bạn có một nhiệm vụ như sau:
- Chọn ngẫu nhiên một số từ 1 đến 10 cho đến khi bạn nhận được số 5.
- Ghi lại số lần bạn cần thực thi mã cho đến khi phương thức ngẫu nhiên trả về 5.
Đây là cách bạn làm điều đó với một hàm đệ quy:
function randomUntilFive(result = 0, count = 0){
if(result === 5){
console.log(`The random result: ${result}`);
console.log(`How many times random is executed: ${count}`);
return;
}
result = Math.floor(Math.random() * (10 - 1 + 1) + 1);
count++;
randomUntilFive(result, count);
}
randomUntilFive();Bạn không thể thay thế đoạn mã trên bằng for vòng lặp, nhưng bạn có thể thay thế nó bằng một while vòng:
let result = 0;
let count = 0;
while (result !== 5) {
result = Math.floor(Math.random() * (10 - 1 + 1) + 1);
count++;
}
console.log(`The random result: ${result}`);
console.log(`How many times random is executed: ${count}`);Ngoài các câu hỏi phỏng vấn mã hóa mà bạn được yêu cầu giải quyết vấn đề bằng cách sử dụng đệ quy, bạn luôn có thể tìm thấy một giải pháp thay thế sử dụng một trong hai cách sau: for hoặc while câu lệnh vòng lặp.
Cách đọc một hàm đệ quy
Một chức năng đệ quy không trực quan hoặc dễ hiểu ngay từ cái nhìn đầu tiên. Các bước sau đây sẽ giúp bạn đọc và hiểu một hàm đệ quy nhanh hơn:
- Luôn xác định trường hợp cơ sở của chức năng trước bất cứ điều gì khác.
- Truyền đối số cho hàm sẽ ngay lập tức tiếp cận trường hợp cơ sở.
- Xác định các đối số ít nhất sẽ thực hiện lời gọi hàm đệ quy một lần.
Hãy thử các bước này bằng cách sử dụng randomUntilFive() ví dụ trên. Bạn có thể xác định trường hợp cơ sở cho chức năng này bên trong if tuyên bố trên:
function randomUntilFive(result = 0, count = 0){
if(result === 5){
// base case is triggered
}
// recursively call the function
}
randomUntilFive();Điều này có nghĩa là bạn có thể tiếp cận trường hợp cơ bản bằng cách chuyển số 5 vào result thông số như sau:
function randomUntilFive(result = 0, count = 0){
if(result === 5){
console.log(`The random result: ${result}`);
console.log(`How many times random is executed: ${count}`);
return;
}
}
randomUntilFive(5);Trong khi count tham số không được bằng 0, chuyển số 5 làm đối số cho lệnh gọi hàm ở trên đáp ứng yêu cầu của bước hai.
Cuối cùng, bạn cần tìm một đối số ít nhất sẽ thực hiện lệnh gọi hàm đệ quy một lần. Trong trường hợp trên, bạn có thể chuyển bất kỳ số nào khác ngoài 5 hoặc không có gì cả:
function randomUntilFive(result = 0, count = 0){
if(result === 5){
console.log(`The random result: ${result}`);
console.log(`How many times random is executed: ${count}`);
return;
}
result = Math.floor(Math.random() * (10 - 1 + 1) + 1);
count++;
randomUntilFive(result, count);
}
randomUntilFive(4);
// any number other than five
// will execute the recursive callVà bạn đã hoàn tất. Bây giờ bạn hiểu rằng chức năng randomUntilFive() sẽ gọi đệ quy chính nó cho đến khi giá trị của result bằng năm.
Cách viết hàm đệ quy
Viết một hàm đệ quy gần giống như đọc một hàm:
- Tạo một hàm thông thường với trường hợp cơ sở có thể đạt được với các tham số của nó
- Truyền đối số vào hàm ngay lập tức kích hoạt trường hợp cơ sở
- Truyền các đối số tiếp theo kích hoạt lệnh gọi đệ quy chỉ một lần.
Giả sử bạn đang viết một hàm để tính giai thừa. Đây là giai thừa của năm:
5*4*3*2*1 = 120
Đầu tiên, trường hợp cơ sở cho chức năng này là một, vì vậy hãy tạo một factorial hàm trả về một:
function factorial(num){
if(num === 1){
return num;
}
}
console.log(factorial(1));Bây giờ đến bước ba. Chúng ta cần nhận một lời gọi đệ quy trong hàm và gọi nó ít nhất một lần. Vì phép tính giai thừa giảm số đi một trên mỗi phép nhân, bạn có thể mô phỏng nó bằng cách chuyển num-1 vào cuộc gọi đệ quy:
function factorial(num){
if(num === 1){
return num;
}
return num * factorial(num-1)
}
console.log(factorial(2));Và bây giờ bạn đã hoàn tất. Bạn có thể kiểm tra chức năng bằng cách chuyển five vào cuộc gọi:
console.log(factorial(5));Phần kết luận
Bạn vừa học hàm đệ quy là gì và nó so sánh với hàm đệ quy như thế nào for và while các câu lệnh lặp. Một hàm đệ quy phải luôn có ít nhất một trường hợp cơ sở để khiến nó ngừng gọi chính nó, nếu không nó sẽ gây ra lỗi.
Khi đọc một hàm đệ quy, bạn cần mô phỏng một tình huống trong đó trường hợp cơ sở được thực thi ngay lập tức mà không cần thực hiện lời gọi đệ quy.
Khi bạn đã giải quyết xong trường hợp cơ bản, hãy quay lại một bước và cố gắng thực hiện lệnh gọi đệ quy ít nhất một lần. Bằng cách này, bộ não của bạn sẽ lướt qua mã đệ quy và hiểu bằng trực giác những gì nó làm.
Viết hàm đệ quy cũng vậy. Luôn tạo trường hợp cơ sở trước rồi viết đối số chạy lệnh gọi đệ quy ít nhất một lần. Phần còn lại sẽ dễ dàng hơn từ đó.
Cảm ơn đã đọc hướng dẫn này
Nếu bạn muốn tìm hiểu thêm, tôi đã viết về cách tìm dãy số Fibonacci bằng đệ quy, đây là một trong những bài toán đệ quy phổ biến nhất.
Tôi cũng có một bản tin miễn phí hàng tuần về các hướng dẫn phát triển web (chủ yếu liên quan đến JavaScript).
