Recursion (Đệ Quy) trong JavaScript

Posted on by adminChuyên mục:Kiến thức Internet

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.

Recursive trong JavaScript (Recursion Function)

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 kèm theo

    / / Đú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();

}

}
 

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).Nói chung, những hàm đệ quy được sử dụng để chia một yếu tố lớn thành những yếu tố nhỏ hơn. Bạn sẽ thường thấy nó trong những cấu trúc tài liệu như cây nhị phân, đồ thị và những thuật toán như tìm kiếm nhị phân ( ) và thuật toán sắp xếp nhanh ( ) .

Ví dụ về Hàm Đệ quy

Hãy cùng làm một vài ví dụ để tìm hiểu và khám phá 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, tất cả 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 tác dụng :

…
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):

  • 456 bằng 450 + 6
  • 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 thành phần trong mảng. Nếu thành phần đó 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ì liên tục lặp qua từng thành phần 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]
 

hàm reduce()Để tối ưu hơn, tất cả chúng ta hoàn toàn có thể sử dụng tích hợp


/ / 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

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 ENDNhư vậy, trong bài viết này bạn đã được khám phá vềthông qua 1 số ít ví dụ đơn cử .

—

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 tiễn + Tuyển dụng ngay !

Đc : Tầng 3, 25T2, N05, Nguyễn Thị Thập, CG cầu giấy, TP.HN

SĐT : 02435574074 – 0383.180086

E-Mail : [email protected]

Fanpage: https://facebook.com/NIIT.ICT/

# niit # icthanoi # niithanoi # niiticthanoi # hoclaptrinh # khoahoclaptrinh # hoclaptrinhjava # hoclaptrinhphp

admin