Recursive Function in 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 fibonacci viết dưới dạng recursive function ở trên có độ phức tạp là O(2^n). Trong khi phiên bản sử dụng vòng lặp có độ phức tạp là O(n). Như thế rõ ràng là recursive function có hiệu năng cực tệ và chúng ta trăm ngàn lần không nên dùng nó. Tất nhiên không phải vậy vì các ngôn ngữ lập trình hàm đều không có vòng lặp và chúng ta chỉ có thể sử dụng recursive function. Thế thì vì cái gì mà recursive function lại được các ngôn ngữ đó yêu quí như vậy. Không chỉ vì nó là hàm mà nó được yêu quí hơn trong các ngôn ngữ lập trình hàm mà còn vì nó có thể có hiệu năng hoàn toàn không thua kém so với vòng lặp.

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 a(1) trả kết quả về đoạn code ban đầu đã gọi recursive function là xong thay vì truyền qua một đống call stack như thế. Vậy nên thay vì tạo ra một đống call stack, compiler có thể sử dụng lại call stack ban đầu. Kĩ thuật này gọi là Tail call optimization. Nhờ vậy, một tail recursive function sẽ chỉ cần một stack, tương tự như một vòng lặp.

ES6 đã hỗ trợ Tail call optimization trong strict mode nên hãy thử viết lại hàm factorial theo kiểu tail recursive function.

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 factorialRec có vai trò giống như vòng lặp trong hàm factorial. Tham số accumulator chính là giá trị đầu tiên của vòng lặp. Nhờ có tính năng default argument trong ES6, ta có thể viết nó lại như thế này

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 factorial trên Node hoặc hầu hết browser trừ Safari hoặc Chrome với flag --enable-javascript-harmony thì bạn vẫn sẽ nhận được

Uncaught RangeError: Maximum call stack size exceeded

Vì dù có trong specification của ES6, hầu hết browser vẫn chưa hỗ trợ Tail call optimization. Bạn có thể đọc thêm về lí do tính năng này vẫn còn bị trì hoãn trong mục Proper Tail Calls ở đây. Mà dù cho nó có được hỗ trợ thì chúng ta vẫn còn phải hỗ trợ các phiên bản cũ của browser và phải rất rất lâu nữa mới có thể thoải mái sử dụng tính năng này.

Nếu bạn đang sử dụng Babel thì Babel v5 có tính năng transpile tail recursive function thành một vòng lặp, như đã nói trước đó, tất cả recursive function đều có thể được viết lại thành một vòng lặp. Nhưng đến v6 thì tính năng này lại bị bỏ mất tiêu. Hãy hi vọng nó sẽ trở lại trong v7.

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

function trampoline(fun) {
  let result = fun();

  while (result && typeof result === 'function') {
    result = result();
  }

  return result;
};

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

var factorialRec = (accumulator, n) => n > 0 ? () => factorialRec(accumulator * n, n - 1) : accumulator;
var factorial = (n) => trampoline( () => factorialRec(n, n - 1) );

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.