Trong hướng dẫn này, mình sẽ hướng dẫn bạn sử dụng kỹ thuật Đệ quy (Recursion) để phát triển một hàm đệ quy (Recursive Function) trong JavaScript.
Về cơ bản, Hàm đệ quy là các hàm tự gọi lại chính nó.
Giới thiệu về các hàm đệ quy JavaScript
Một hàm đệ quy là một hàm gọi chính nó cho đến khi không thể gọi. Kỹ thuật này được gọi là Đệ quy (Recursion).
Giả sử, bạn có một hàm được gọi là recurse(). Hàm recurse() này sẽ là một hàm đệ quy (Recursive Function) nếu nó gọi chính nó bên trong phần thân của nó, như thế này:
// Hàm đệ quy
function recurse() {
// ...
// Tự gọi lại chính nó
recurse();
// ...
}
Tuy nhiên, phải lưu ý là, một hàm đệ quy luôn phải có điều kiện ngừng gọi chính nó, nếu không, nó sẽ tự gọi lại vô hạn.
Vì thế, một hàm đệ quy thường có thêm điều kiện ngừng trông giống như sau:
// Hàm đệ quy
function recurse() {
// Kiểm tra điều kiện
// Đúng: Ngừng gọi lại chính nó
// Sai: Gọi lại chính nó
if(condition) {
// Code ngừng gọi lại
} else {
recurse();
}
}
Nói chung, các hàm đệ quy được sử dụng để chia một vấn đề lớn thành những vấn đề nhỏ hơn.
Bạn sẽ thường thấy nó trong các cấu trúc dữ liệu như cây nhị phân, đồ thị và các thuật toán như tìm kiếm nhị phân (binary serarch) và thuật toán sắp xếp nhanh (quicksort).
Ví dụ về Hàm Đệ quy
Hãy cùng làm một vài ví dụ để tìm hiểu về cách sử dụng hàm đệ quy trong JavaScript
VD1: Hàm đệ quy đơn giản
Giả sử rằng bạn cần tạo ra một hàm đếm ngược từ một số được chỉ định đến 1. Ví dụ: Đếm ngược từ 5 đến 1
Đầu tiên, ta tạo hàm countDown() như sau:
function countDown(fromNumber) {
console.log(fromNumber);
}
countDown(5);
Nhưng như thế thì hàm countDown() này luôn chỉ hiển thị kết quả là 5.
Và để đếm ngược từ 5 đến 1 bạn cần phải:
-
Gọi
countDown(5) và log ra 5
-
Gọi
countDown(4) và log ra 4
-
Gọi
countDown(3) và log ra 3
-
Gọi
countDown(2) và log ra 2
-
Gọi
countDown(1) và log ra 1
Ok, chúng ta tiến thêm một bước nữa, sửa đoạn code trên thành như sau:
function countDown(fromNumber) {
console.log(fromNumber);
// Gọi lại hàm countDown
// với fromNumber đi 1
countDown(fromNumber-1);
}
countDown(5);
Chạy chương trình trên ta được kết quả:
...
Uncaught RangeError: Maximun call stack size exceeded.
Hàm vẫn chạy đếm ngược, nhưng nó không dừng lại, dẫn đến lỗi.
Vì thế chúng ta phải thêm điều kiện để dừng lại khi số tiếp theo là 0:
function countDown(fromNumber) {
console.log(fromNumber);
// Tính số tiếp theo
let nextNumber = fromNumber - 1;
// Kiểm tra số tiếp theo
// Lớn hơn 0 thì in nó ra console
if (nextNumber > 0) {
countDown(nextNumber);
}
}
countDown(5);
Kết quả chạy lại chương trình này ta được:
5
4
3
2
1
Đến đây, countDown() có vẻ như là đã hoạt động đúng với ý định của chúng ta.
Tuy nhiên, tên của hàm là một tham chiếu đến đối tượng hàm thực.
Nếu ở đâu đó trong code, tên hàm được đặt thành null, thì hàm đệ quy sẽ ngừng hoạt động.
Ví dụ, đoạn code sau sẽ dẫn đến lỗi:
let newYearCountDown = countDown;
// Ở đâu đó trong code
// ai đó đặt countDown thành null
countDown = null;
// Thế nên khi gọi hàm sẽ gây ra lỗi
newYearCountDown(10);
Lỗi:
Uncaught TypeError: countDown is not a function
Giải thích:
-
Đầu tiên, gán tên hàm
countDown cho biến newYearCountDown.
-
Thứ hai, đặt tham chiếu hàm
countDown thành null.
-
Thứ ba, gọi hàm
newYearCountDown.
Mã gây ra lỗi vì phần thân của hàm countDown() tham chiếu đến tên hàm countDown đã được đặt thành null tại thời điểm gọi hàm.
Để khắc phục, bạn có thể sử dụng một biểu thức hàm được đặt tên như sau:
// Hàm đệ quy
let countDown = function f(fromNumber) {
console.log(fromNumber);
// Tính số tiếp theo
let nextNumber = fromNumber - 1;
// Kiểm tra số tiếp theo
// Lớn hơn 0 thì in nó ra console
if (nextNumber > 0) {
f(nextNumber);
}
}
let newYearCountDown = countDown;
// Cố tình (hay vô ý) đặt countDown thành null
countDown = null;
// Gọi hàm đệ quy đếm ngược chào năm mới từ 5
newYearCountDown(5);
Kết quả khi chạy chương trình trên ta được:
5
4
3
2
1
VD2: Tính tổng các chữ số từ một số
Bài toàn đặt ra: Đưa cho một số (VD: 456), tính tổng từ các chữ số trong số đó như: 4 + 5 + 6 = 15
Để áp dụng kỹ thuật đệ quy, chúng ta phân tích (tách ra và tính %10):
-
450 % 10 bằng 45 => Tương đương với 40 + 5
-
40 % 10 bằng 4 => Tương đương với 4 + 0
Tương đương với:
-
Lần 1: f(456) = 6 + f(45)
-
Lần 2: f(456) = 6 + 5 + f(4)
-
Lần 3: f(456) = 6 + 5 + 6
Ta sử dụng giải pháp sau:
-
Đầu tiên, số phải khác
0. Nếu bằng 0 thì ngừng gọi hàm
-
Tìm số cuối cùng bằng phép chia lấy phần dư cho 10, ví dụ:
456 % 10 = 6
-
Sử dụng phép tính chia cho 10 và làm tròn để tìm phần đầu, ví dụ:
456 / 10 = 45.6. Ta sử dụng làm tròn số: Math.floor(num / 10) ta được 45
Code:
function sumOfDigits(num) {
if (num == 0) {
return 0;
}
return num % 10 + sumOfDigits(Math.floor(num / 10));
}
Bây giờ, chạy thử chương trình:
console.log(sumOfDigits(456));
Kết quả:
15
VD3: Sử dụng Recursion để làm phẳng mảng lồng nhau trong JS
Ta có một mảng lồng nhau như thế này:
let x = [1, 2, 3, [4, 5, 6, [7, 8]], 9];
Ý tưởng:
-
Lặp qua từng phần tử trong mảng. Nếu phần tử đó không phải là mảng thì thêm nó vào cuối một mảng mới
-
Nếu là một mảng thì tiếp tục lặp qua từng phần tử trong đó và lại kiểm tra xem có phải là mảng không. Nếu không thì thêm nó vào cuối mảng mới (đã tạo trước đó)
Code:
function flatten() {
var flat = [];
for (var i = 0; i < arguments.length; i++) {
if (arguments[i] instanceof Array) {
flat.push.apply(flat, flatten.apply(this, arguments[i]));
} else {
flat.push(arguments[i]);
}
}
return flat;
}
> Lưu ý: Sử dụng flatten.apply(this, arguments[i]) để truyền phần tử của mảng (chứ không phải là mảng gốc) (Xem thêm: hàm apply() trong JS)
Kết quả chạy chương trình làm phẳng mảng lồng nhau:
console.log(flatten(x));
Ta được:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Để tối ưu hơn, chúng ta có thể sử dụng kết hợp hàm reduce():
// Sử dụng đệ quy để làm phẳng mảng lồng nhau
function flatten(items) {
const flat = [];
items.forEach(item => {
if (Array.isArray(item)) {
flat.push(...flatten(item));
} else {
flat.push(item);
}
});
return flat;
}
Tổng kết về Recursion trong JavaScript
Như vậy, trong bài viết này bạn đã được tìm hiểu về Recursion trong JavaScript thông qua một số ví dụ cụ thể.
> Nếu bạn yêu thích JavaScript và muốn đi chuyên sâu. Hãy tham gia ngay KHÓA HỌC FRONT END với sự hướng dẫn của chuyên gia doanh nghiệp để học nhanh hơn, chuẩn hơn, đi thực tập / đi làm sớm hơn.
---
HỌC VIỆN ĐÀO TẠO CNTT NIIT - ICT HÀ NỘI
Học Lập trình chất lượng cao (Since 2002). Học thực tế + Tuyển dụng ngay!
Đc: Tầng 3, 25T2, N05, Nguyễn Thị Thập, Cầu Giấy, Hà Nội
SĐT: 02435574074 - 0383.180086
Email: hello@niithanoi.edu.vn
Fanpage: https://facebook.com/NIIT.ICT/
#niit #icthanoi #niithanoi #niiticthanoi #hoclaptrinh #khoahoclaptrinh #hoclaptrinhjava #hoclaptrinhphp