Recursion (Đệ Quy) trong JavaScript

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

();

    }

}
 

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, 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 () 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ề 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):

• 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 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]
 

hàm reduce()

Để tối ưu hơn, chúng ta có thể sử dụng kết 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 END

Như vậy, trong bài viết này bạn đã được tìm hiểu vềthông qua một số ví dụ cụ thể.

—

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: [email protected]

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

 

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