Hướng dẫn recursion in javascript - đệ quy trong javascript

Định nghĩa recursive function là gì thì chắc chúng ta đều đã biết. Tuy nhiên nếu bạn đang làm việc với một ngôn ngữ cho phép sử dụng vòng lặp như JavaScript (hay tất cả các ngôn ngữ không phải là một functional programming language), bạn sẽ hiếm khi thấy cần phải dùng đến recursive function. Đó là vì tất cả các recursive function đều có thể được viết dưới dạng một vòng lặp. Hơn nữa, trong các ngôn ngữ như vậy, hiệu năng của recursive function thường kém hơn nhiều so với vòng lặp. Dù vậy, vẫn có những trường hợp mà sử dụng recursive function sẽ dễ dàng hơn nhiều (ví dụ như khi làm việc với một cấu trúc cây) và giúp code dễ hiểu hơn, hoặc bạn muốn có một biến immutable nên không thể sử dụng vòng lặp.

Ví dụ đơn giản

Cũng như một recursive function luôn có thể viết được dưới dạng vòng lặp, các vòng lặp đều có thể viết lại được dưới dạng một recursive function. Lấy ví dụ một hàm với vòng lặp đơn giản thế này

function makeA(n) {
    let a = [];

    for (let i = 0; i < n; i++) {
        a.push(i);
    }

    return a;
}

Có thể được viết lại dưới dạng recursive function như sau

const makeA = (n) => makeARec(n, []);
const makeARec = (n, a) => n === 0 ? a : makeARec(n - 1, [n, ...a]);

Trông rõ ràng là rắc rối khó hiểu hơn. Nhưng nếu bạn so sánh hàm này

const fibonacci(n) => n <= 1 ? n : fibonacci(n - 1) + fibonacci(n - 2);

Và phiên bản sử dụng vòng lặp của nó

function fibonacci(n) {
    let a = 1, b = 0, temp;

    while (n > 0){
        temp = a;
        a = a + b;
        b = temp;
        n--;
    }

    return b;
}

Thì rõ ràng là dùng recursive function trong trường hợp này sẽ dễ hơn rất nhiều. Nói chung, các khái niệm toán học hoặc những thứ như như cấu trúc dữ liệu sẽ dễ dàng được thể hiện dưới dạng recursive function hơn vì chúng đều được định nghĩa dưới dạng các hàm. Viết lại chúng dưới dạng vòng lặp hẳn là sẽ tốn công sức hơn.

Tuy nhiên, chắc các bạn còn nhớ hàm

const makeA = (n) => makeARec(n, []);
const makeARec = (n, a) => n === 0 ? a : makeARec(n - 1, [n, ...a]);

Tail call optimization

Cùng xét một recursive function quen thuộc đó là tính giai thừa của một số

const factorial = (a) => {
    if (a < 0) {
        return -1;
    }

    if (a === 0) {
        return 1;
    }

    return a * factorial(a - 1);
}

Nếu bạn gọi hàm này với một số thật to, 300000 chẳng hạn, thì browser sẽ báo lỗi

Uncaught RangeError: Maximum call stack size exceeded

Đó là vì để chạy một function, máy tính phải nhớ vị trí hàm đó được gọi để sau khi thực hiện xong sẽ trả kết quả về vị trí đã gọi hàm đó. Đối với JavaScript, mỗi function sẽ được tạo một call stack. Để chạy một recursive function, browser sẽ phải tạo một đống call stack, và mỗi call stack không thể bị hủy cho đến khi các call stack bên trong nó được thực hiện xong. Khi có quá nhiều call stack thì browser sẽ báo lỗi như trên. Điều này cũng xảy ra với nhiều ngôn ngữ khác như Java, C++...

Tuy nhiên, nếu một hàm chỉ gọi lại chính nó và không làm gì khác ở câu lệnh return, ví dụ thế này

function a(n) {
    if (n === 1) {
        return n;
    }

    return a(n - 1);
}

thì call stack của nó sẽ trông như thế này

Call a(3)
-> Create call stack for a(3)
a(3) call a(2)
-> Create call stack for a(2)
a(2) call a(1)
-> Create call stack for a(1)
a(1) return 1 to a(2)
-> Pop call stack of a(1)
a(2) return 1 to a(3)
-> Pop call stack of a(2)
a(3) return 1
-> Pop call stack of a(3)

Bạn có thể thấy một đống call stack ở giữa hoàn toàn lãng phí, chỉ cần

const makeA = (n) => makeARec(n, []);
const makeARec = (n, a) => n === 0 ? a : makeARec(n - 1, [n, ...a]);

ES6 đã hỗ trợ Tail call optimization trong strict mode nên hãy thử viết lại hàm

const makeA = (n) => makeARec(n, []);
const makeARec = (n, a) => n === 0 ? a : makeARec(n - 1, [n, ...a]);

const factorial = (a) => a < 0 ? -1 : a === 0 ? 1 : factorialRec(a, 1);
const factorialRec = (n, accumulator) => n === 1 ? accumulator : factorialRec(n - 1, n * accumulator);

Lần này thì không bị lỗi nữa

factorial(300000) // Infinity

Do it elegantly

Bạn có thể thấy chúng ta thường cần đến hai hàm. Như trong ví dụ trên, hàm

const makeA = (n) => makeARec(n, []);
const makeARec = (n, a) => n === 0 ? a : makeARec(n - 1, [n, ...a]);

const makeA = (n) => makeARec(n, []);
const makeARec = (n, a) => n === 0 ? a : makeARec(n - 1, [n, ...a]);

const factorial = (a, accumulator = 1) => {
    if (a === 0) {
        return -1;
    }

    if (a === 1) {
        return accumulator;
    }

    return factorial(a - 1, a * accumulator);
}

It doesn't work

Tại thời điểm viết bài này (Chrome 54, Firefox 49, Node 7.0), nếu bạn thử chạy hàm

const makeA = (n) => makeARec(n, []);
const makeARec = (n, a) => n === 0 ? a : makeARec(n - 1, [n, ...a]);

Uncaught RangeError: Maximum call stack size exceeded

Đó là vì để chạy một function, máy tính phải nhớ vị trí hàm đó được gọi để sau khi thực hiện xong sẽ trả kết quả về vị trí đã gọi hàm đó. Đối với JavaScript, mỗi function sẽ được tạo một call stack. Để chạy một recursive function, browser sẽ phải tạo một đống call stack, và mỗi call stack không thể bị hủy cho đến khi các call stack bên trong nó được thực hiện xong. Khi có quá nhiều call stack thì browser sẽ báo lỗi như trên. Điều này cũng xảy ra với nhiều ngôn ngữ khác như Java, C++...

Tuy nhiên, nếu một hàm chỉ gọi lại chính nó và không làm gì khác ở câu lệnh return, ví dụ thế này

Trampoline

Nếu bạn nhất định muốn dùng recursive function với JavaScript thì thật may là JavaScript là một ngôn ngữ có first-class function nên ta có thể dễ dàng sử dụng một kĩ thuật khác đó là Trampoline. Nội dung thì giống như tên của nó vậy, chúng ta sẽ gọi đi gọi lại hàm đó trong một vòng lặp. Nhờ vậy mỗi lần gọi xong, call stack của nó sẽ bị hủy và số call stack sẽ không bị vượt quá mức cho phép.

Có thể viết hàm Trampoline đơn giản thế này

const makeA = (n) => makeARec(n, []);
const makeARec = (n, a) => n === 0 ? a : makeARec(n - 1, [n, ...a]);

Hàm factorial sẽ phải viết lại một chút

const makeA = (n) => makeARec(n, []);
const makeARec = (n, a) => n === 0 ? a : makeARec(n - 1, [n, ...a]);

Sử dụng trampoline vẫn sẽ không cho hiệu năng như với vòng lặp hoặc khi có tail call optimization vì chúng ta vẫn phải tạo ra rất nhiều call stack thay vì chỉ dùng 1 call stack. Ngoài ra bạn còn phải sửa lại hàm nữa, như thế có chút bất tiện. Bạn có thể xem một cách implement hàm trampoline khác mà không cần phải sửa lại hàm recursive ở đây.

Lời kết

Dù không phổ biến trong JavaScript do hầu hết mọi người đều quen với vòng lặp hơn, bạn vẫn sẽ gặp những trường hợp mà recursive function thật sự sẽ giúp giải quyết vấn đề dễ dàng hơn. Làm quen với recursive function sẽ giúp bạn đến gần hơn với functional programming, một mô hình lập trình khác trong JavaScript bên cạnh mô hình mà có thể bạn đã rất quen thuộc - object-oriented programming. Nếu bạn có hứng thú với functional programming, hãy thử qua Elm, một ngôn ngữ lập trình hàm được compile thành JavaScript. Còn nếu bạn đã từng làm việc với một ngôn ngữ lập trình hàm, mình tin là bạn thậm chí còn muốn dùng recursive function hơn là vòng lặp nữa.