Function trong JavaScript (Phần 3) - Khái niệm về đệ quy

Dẫn nhập

Ở các bài trước, các bạn đã được tìm hiểu về Các kiến thức mở rộng về Function trong JavaScript

Trong bài này, chúng ta sẽ cùng nhau tìm hiểu về một cách làm việc mới mẻ hơn, đó là đệ quy (recursion).

---

Nội dung

Để nắm được bài này, bạn cần có kiến thức về:

• Các kiểu dữ liệu cơ bản trong JavaScript
• Kiểu dữ liệu function trong JavaScript
• Câu lệnh điều kiện trong JavaScript
• Vòng lặp trong JavaScript

Nội dung của bài này:

• Đặt vấn đề
• Khái quát về đệ quy
• Ví dụ về đệ quy
• Đệ quy và vòng lặp

---

Đặt vấn đề

Bạn cần phải thực hiện một công việc, và sẽ dừng lại ở một thời điểm nào đó.

Khi nhắc như vậy, chắc hẳn chúng ta sẽ nhớ ngay đến vòng lặp – một món vũ khí tiện lợi cho những thao tác có đặc điểm là lặp đi lặp lại.

Tuy nhiên, nếu như mong muốn một sự mới mẻ hơn cho những dòng code, đệ quy cũng là một sự lựa chọn đáng để thử, dành cho những chương trình đơn giản.

Vậy đệ quy là cái gì ? Mời các bạn theo dõi phần bên dưới.

---

Khái niệm về đệ quy

Các bạn đã được biết về function, hay còn được gọi là hàm, là chương trình con. Function có thể được gọi ra từ chương trình chính hoặc từ một function khác.

Vậy giả sử, function mà được gọi ngay trong chính functionđó thì sao nhỉ ? Cách gọi hàm như vậy được gọi là đệ quy.

Một yếu tố thiết yếu cần có trong việc đệ quy, chính là việc gọi hàm trong chính nó, và bắt buộc phải có một điểm dừng.

Nếu một hàm đệ quy mà không có điểm dừng thì sao ? Thì tất nhiên, nó sẽ chạy, và cũng dừng, nhưng nó dừng theo một cách chẳng ai mong muốn, đó là tràn bộ nhớ.

> function recursion(n) {
... recursion(n-1);
... }
undefined
> recursion(1) // Gọi hàm đệ quy recursion
Uncaught RangeError: Maximum call stack size exceeded
    at recursion (REPL3:2:1)
    at recursion (REPL3:2:1)
    at recursion (REPL3:2:1)
    at recursion (REPL3:2:1)
    at recursion (REPL3:2:1)
    at recursion (REPL3:2:1)
    at recursion (REPL3:2:1)
    at recursion (REPL3:2:1)
    at recursion (REPL3:2:1)
    at recursion (REPL3:2:1)

Hàm recursion sẽ chạy mãi, và mỗi lần chạy, nó sẽ tiêu tốn một lượng bộ nhớ nhất định. Đến một thời điểm nào đó, thì sẽ xảy ra lỗi tràn bộ nhớ.

Về cách bộ nhớ được lưu trữ trong máy tính khi chạy hàm đệ quy, Kteam sẽ có một bài viết để đề cập về nó.

---

Ví dụ về đệ quy

Như vậy, chắc hẳn các bạn đã biết đệ quy là gì rồi, giờ chúng ta hãy cùng nhau xem một ví dụ cụ thể. Cả 2 ví dụ dưới đây đều có thể giải quyết đơn giản bằng vòng lặp, nhưng đây là đệ quy, do đó nên đệ quy sẽ là cách tiếp cận cho những ví dụ bên dưới.

Ví dụ 1: Tính tổng các số trong đoạn [1..n] bằng đệ quy.

Phương pháp tiếp cận:

Như ta đã biết, đệ quy có 2 yếu tố chính, chính là lệnh gọi đệ quy và điểm dừng.

Nếu như để ý chi tiết, thì tổng các số trong đoạn [1..n] chính là tổng: 1 + 2 + 3 + … + n-2 + n-1 + n. Và trong tổng này, ta có tổng cộng là n số hạng. Vì vậy, một phương pháp khả dĩ sẽ là gọi đệ quy với mỗi số hạng tương ứng. Bắt đầu từ 1, đến 2, …

Vậy thì khi đó, ta có thể suy ra rằng, quá trình đệ quy sẽ dừng lại khi mà giá trị n được xét đến. Vì nó là giá trị cuối cùng.

Từ cách tiếp cận như trên, ta có thể viết được mã giả như sau:

Hàm Sum(n, k = 1) {
          Nếu k = n à Trả về n, kết thúc đệ quy.
          Ngược lại (nếu k ≠ n), thì trả về k + Sum(n, k+1);
}

Để có thể hiểu được đoạn mã giả này, ta sẽ thử lấy ví dụ với n = 4:

• Với k = 1 (<n), trả về 1 + Sum(4, 2).
• 1 + Sum(4, 2): Lúc này, k = 2 (<n), thì trả về 1 + (2 + Sum(4, 3)) (Giá trị 1 vẫn được giữ lại do lệnh gọi đệ quy trước)
• 1 + (2 + Sum(4, 3)): k = 3 (<n), trả về 1 + (2 + 3 + Sum(4, 4)).
• 1 + (2 + (3 + Sum(4, 4))): k = 4, trả về k.

Sau cùng, tổng này sẽ có dạng: 1 + (2 + (3 + (4))) và bằng với 10.

Sau khi đã “ngấm” được đoạn mã giả trên, ta sẽ chuyển thành ngôn ngữ mà chúng ta đang dùng:

> function Sum(n, k = 0) {
... if(n == k) return n;
... return k + Sum(n, k + 1);
... }
undefined

Và, khi gọi hàm với một số bất kì, thì kết quả cho ra sẽ chính xác:

> Sum(4)
10

---

Ví dụ 2: Tính , với n và k cho trước

Phương pháp tiếp cận:

Về mặt bản chất, thì  =  (k số n).

Từ đây, một cách để đệ quy là sử dụng số mũ của lũy thừa.

Ý tưởng được trình bày trong đoạn mã giả sau:

Hàm pow(n, k) {
          Nếu p = 1 à trả về n (do )
          Nếu p > 0 à trả về n * pow(n, k-1)
}

Cũng tương tự như ví dụ 1, dưới đây chúng ta cùng xem xét cách chương trình chạy với n = 2 và k = 4:

• Đầu tiên, k = 4 (>1) à trả về 2 * pow(2, 3)
• k = 3 (>1) à gọi 2 * (2 * pow(2, 2)) (Giữ lại 2 ban đầu do kế thừa từ lệnh đầu tiên)
• k = 2 (>1) à gọi 2 * (2 * (2 * pow(2, 1)))
• k = 1 (=1) à trả về 2 * 2 * 2 * 2 = 16

Và, từ đoạn mã giả đó, ta có thể chuyển thành code, và cách code như sau:

> function pow(n, k) {
... if(k == 0) return 1;
... return n * pow(n, k-1);
... }
undefined
> pow(2, 5)
32
> pow(4, 4)
256

Hai chương trình trên chỉ là 2 chương trình cơ bản đối với đệ quy. Về thực chất, đệ quy không khó, nhưng nó khá trừu tượng. Chính vì thế, khi đã nắm được bản chất của nó, việc sử dụng đệ quy thành thạo hoàn toàn nằm trong tầm tay.

---

Mở rộng

Cả 2 ví dụ trên, đều có thể sử dụng vòng lặp để hoàn thành một cách dễ dàng. Trên thực tế, thời gian chạy của đệ quy và vòng lặp (trong 2 trường hợp trên) là như nhau.

Bây giờ là một thử thách dành cho bạn: hãy sửa lại hàm pow bên trên sao cho khi chạy, số bước chạy ít hơn so với cách mà Kteam đã đề cập.

Gợi ý:  với k chẵn.

---

Đệ quy và vòng lặp

Hai ví dụ bên trên chính là điển hình cho cách mà vòng lặp có thể thay thế đệ quy: Ở ví dụ 1, chỉ cần lặp các số từ 1 đến n, sau đó cộng lại là được, còn ở ví dụ 2, thì lặp các số từ 1 đến k, với mỗi lần lặp ta nhân n vào biến kết quả là xong (ban đầu biến kết quả phải bằng 1).

Và, tất nhiên, vì tính trừu tượng của nó, đệ quy không được khuyến khích sử dụng một cách lung tung. Trong tất cả các trường hợp, nếu có thể, hãy dùng vòng lặp.

---

Kết luận

Qua bài này, các bạn đã có kiến thức về một skill mới, đó là đệ quy.

Trong bài tiếp theo, các bạn sẽ được củng cố lý thuyết cũng như thực hành thêm một vài bài tập về Function trong JavaScript

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

---

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.