Tui thì đó giờ hay cày rank trên Codewars, chủ yếu là vì giao diện của nó ngầu lòi hơn ba mấy web thuật toán chán ngắt khác 😄 Chơi một thời gian thì tui cũng lên được 4 kyu và gặp phải bài toán này The fusc function - Part 2. Bài này thú vị ở chỗ, thay vì như thông thường họ chỉ đưa mình đề bài, thì bài này họ còn đưa cho mình một bài khác ví dụ mẫu cho phương pháp mà họ muốn mình dùng. Nói chung là giải xong sẽ học được phương pháp gì đó mới, chỉ tiếc là tui lúc đó đã quyết định gập máy đi ngủ 🙂 Mới đầu năm nay thì tui thử mở ra làm lại, và congrats, não tui đã được thông, giờ tui đi thông ngược lại cho mấy bạn đây.

Trong bài viết này, tui sẽ đi giải quyết bài toán trên trước, mục tiêu bài toán là đưa từ một hàm đệ quy thành một hàm đệ quy đuôi (tail call elimination), đừng lo, tui sẽ giải thích kĩ hơn những thuật ngữ này ở phía dưới. Sau đó tui sẽ chia sẻ một chút về góc nhìn của tui tại sao phương pháp của bài toán này khá độc đáo so với thực tế. Okay triển thôi nào!

Nội dung bài toán

Dành cho những con người chây lười không chịu bấm vào link đọc trước (ừa tui đang nói bạn đó) thì tui sẽ trình bày lại bài toán ở đây luôn, chứ không phải vì tui muốn bài mình dài ra đâu nha. Với lại tui cũng sẽ làm rõ một số chỗ mà bài viết gốc không đề cập tới.

Cho hàm \(\operatorname{fusc}(n)\) được định nghĩa như sau:

\[\begin{cases} \operatorname{fusc}(0) = 0\\ \operatorname{fusc}(1) = 1\\ \operatorname{fusc}(2n) = \operatorname{fusc}(n)\\ \operatorname{fusc}(2n + 1) = \operatorname{fusc}(n) + \operatorname{fusc}(n + 1)\\ \end{cases} \]

Việc của bạn là hãy viết lại và tối ưu hàm \(\operatorname{fusc}(n)\) trên. Nhớ rằng \(n\) sẽ có giá trị rất lớn, cụ thể thì \(n\) sẽ lớn hơn 1000 bit (đối với Javascript) và 52 bit (đối với PHP), nên là cần lưu ý tới vấn đề stack overflow và timeouts.

Gợi ý phương pháp

Phần này trong lúc đọc mấy bạn không cần quá hoang mang những thứ như là tại sao phải đưa hai vế về cùng dạng, rồi tại sao phải đặt thêm biến a, b các thứ đâu, cứ đọc đến cuối là mọi thứ sẽ trở nên make sense thôi.

Tưởng tượng thay vì đề bài là hàm \(\operatorname{fusc}(n)\) mà là hàm \(\operatorname{fib}(n)\) (trả về số Fibonacci thứ \(n\)), thì lúc này hàm được định nghĩa như sau:

\[\begin{cases} \operatorname{fib}(0) = 1 & (1)\\ \operatorname{fib}(1) = 1 & (2)\\ \operatorname{fib}(n + 2) = \operatorname{fib}(n) + \operatorname{fib}(n + 1)\quad (n \geq 0) & (3) \end{cases} \]

Nếu dùng trực tiếp định nghĩa trên thì không được tối ưu cho lắm. Dĩ nhiên bạn hoàn toàn có thể dùng quy hoạch động, nhưng làm vậy thì lại tốn thêm bộ nhớ không cần thiết, nên là chúng ta sẽ cố thử tìm đệ quy đuôi (tail recursion) cho bài toán này.

Lại là góc nhỏ cho những con lười không chịu bấm vào đọc trước định nghĩa của tail recursion đây, thì tail recursion là loại hàm đệ quy mà việc gọi đệ quy là điều cuối cùng hàm đó thực hiện. Lấy ví dụ:
// Đây không là tail recursion vì sau khi gọi đệ quy
// fact(n-1) thì hàm phải thực hiện thêm phép nhân
// với n nữa mới kết thúc
function fact(n) {
    if (n === 1)
        return 1
    else
        return n * fact(n-1)
}

// Đây là tail recursion vì chỉ cần gọi fact(n-1, acc*n)
// xong thì hàm sẽ kết thúc
function fact(n, acc) {
    if (n === 1)
        return acc
    else
        return fact(n-1, acc*n)
}

Bạn có thể tự tìm hiểu kĩ hơn tại sao khi đưa về tail recursion thì sẽ tối ưu hơn, nhưng để nói sơ qua thì bình thường khi bạn gọi đệ quy, những giá trị, ô nhớ các thứ ở hiện tại sẽ được đẩy lên call stack, cứ mỗi lần gọi đệ quy lồng nhau thì call stack sẽ càng ngày càng cao lên, bộ nhớ phình to ra, cho đến khi vượt quá call stack size thì chương trình trả về lỗi stack overflow. Tail recursion thì lại khác, vì đệ quy là câu lệnh được thực hiện cuối cùng nên compiler sẽ thoải mái giải phóng stack hiện tại vì nó chắc chắn stack hiện tại không cần dùng nữa, nên dù có gọi đệ quy vô hạn lần thì cũng không lo bị stack overflow.

Tiếp tục nhé, bây giờ để biến \(\operatorname{fib}(n)\) thành tail recursion, ta lấy phương trình \((3)\) đem biến đổi thử, và chúng ta muốn sau khi biến đổi xong thì vế phải phải có dạng giống na ná vế trái, từ đó ta có thể định nghĩa một hàm phụ \(F\) nào đó sao cho vế trái và vế phải phụ thuộc vào nhau thông qua \(F\), kiểu như \(F(2n) = F(3n-1)\) chẳng hạn. Rồi vậy ta thử cộng \(\operatorname{fib}(n+1)\) vào hai vế xem sao:

\[\operatorname{fib}(n+1) + \operatorname{fib}(n+2) = \operatorname{fib}(n) + 2\cdot \operatorname{fib}(n+1) \]

Hai vế khá giống nhau rồi đó, \(\operatorname{fib}(n+1)\) (vế trái) tương ứng với \(\operatorname{fib}(n)\) (vế phải) là ổn rồi nè, còn \(\operatorname{fib}(n+2)\) (vế trái) tương ứng với \(\operatorname{fib}(n+1)\) (vế phải) thì vẫn chưa ổn vì bị khác hệ số, để khắc phục chuyện này thì ta sẽ đưa ra một biến khác, gọi là biến \(b\) đi. Giờ ta thử cộng \((b-1)\operatorname{fib}(n+2)\) vào hai vế xem sao (mục đích cộng như vậy là để \(\operatorname{fib}(n+2)\) có hệ số là \(b\)):

\[\operatorname{fib}(n+1) + b\cdot \operatorname{fib}(n+2) = b\cdot \operatorname{fib}(n) + (b+1)\cdot \operatorname{fib}(n+1) \]

Ta nhận thấy hệ số của \(\operatorname{fib}(n+1)\) và \(\operatorname{fib}(n)\) chưa giống nhau (bên là \(1\), bên là \(b\)), nên là ta đưa thêm biến \(a\) vào và làm tương tự, ta được:

\[a\cdot \operatorname{fib}(n+1) + b\cdot \operatorname{fib}(n+2) = b\cdot \operatorname{fib}(n) + (a+b)\cdot \operatorname{fib}(n + 1)\tag{4} \]

Tuyệt vời ông mặt trời, hai bên có cùng một dạng rồi đó, bây giờ ta định nghĩa hàm phụ \(F\) như sau:

\[F(a, b, n) = a\cdot \operatorname{fib}(n) + b\cdot \operatorname{fib}(n+1) \]

Từ đó ta có thể biểu diễn hai vế của \((4)\) dưới dạng:

\[F(a, b, n+1) = F(b, a+b, n) \tag{*} \]

Ngoài ra dựa vào định nghĩa của \(F\), ta được:

\[F(a, b, 0) = a\cdot \operatorname{fib}(0) + b\cdot \operatorname{fib}(1) = a + b \tag{5} \]

Hơn nữa:

\[\operatorname{fib}(n) = 1\cdot \operatorname{fib}(n) + 0\cdot \operatorname{fib}(n+1) = F(1, 0, n) \tag{6} \]

Ta đã hoàn toàn có đủ nguyên liệu để triển khai thuật toán rồi đó, để ý:

  • \((6)\) cho ta được định nghĩa tổng quát của \(\operatorname{fib}(n)\) dựa trên hàm phụ \(F\).
  • \((*)\) cho ta công thức đệ quy của \(F\).
  • \((5)\) cho ta base case đệ quy của \(F\).

Hy vọng tới đây mọi thứ make sense được với bạn, nếu lú thì cũng không sao cứ đọc lại nhé, mấy lần đầu mình đọc cũng lú 🙂 Giờ thì code thôi (2 code dưới này đều là của tác giả bài toán hết nha, không phải của tui):

def fib(n):

    def F(a, b, n):
        if n == 0: return a + b    # see (5) above
        return F(b, a + b, n - 1)  # see (*) above

    return F(1, 0, n)              # see (6) above

Tới đây là \(QED\) rồi, nhưng nếu ngôn ngữ bạn dùng không hỗ trợ tối ưu đệ quy đuôi (tail call optimization) thì bạn có thể implement theo dạng khử đệ quy như sau:

def fib(n):
    a, b = 1, 0                    # see (6) above
    while n > 0:
        a, b, n = b, a + b, n - 1  # see (*) above
    return a + b .                 # see (5) above
Đây là một sức mạnh khác của tail recursion, một khi bạn đã đưa hàm về tail recursion rồi thì việc khử đệ quy là vô cùng đơn giản.

Tuyệt dời, làm “tương tự” với hàm \(\operatorname{fusc}(n)\) thôi nào 😉. Nếu đọc tới đây mà bạn đã có ý tưởng, hoặc muốn thử sức bản thân thì có thể pause lại. Thật ra theo tui thì một khi đã nắm được ý tưởng của phương pháp này rồi thì cũng không quá khó đâu.

Giải quyết bài toán

Nhắc lại định nghĩa của hàm \(\operatorname{fusc}(n)\). Để cho gõ đỡ mỏi tay đơn giản thì tui đặt hàm \(\operatorname{fusc}(n)\) là hàm \(f(n)\) luôn nhé:

\[\begin{cases} f(0) = 0 & (1)\\ f(1) = 1 & (2)\\ f(2n) = f(n) & (3)\\ f(2n + 1) = f(n) + f(n + 1) & (4)\\ \end{cases} \]

Tương tự như ví dụ trên, từ định nghĩa ta sẽ cố gắng tìm phương trình nào đó sao cho hai vế có cùng dạng, rồi từ đó đặt hàm phụ. Lấy \((3)\) và \((4)\) cộng lại với nhau thử coi sao:

\[f(2n)+f(2n+1)=2f(n) + f(n+1) \]

Thấy hai vế cũng na ná giống rồi nè, \(f(2n)\) tương ứng với \(f(n)\) và \(f(2n+1)\) tương ứng với \(f(n+1)\). Bây giờ tìm cách cân bằng hệ số thôi. Cụ thể, ta sẽ đưa biến \(b\) vào phương trình bằng cách cộng \((b-1)f(2n+1)\) hai vế, ta được:

\[f(2n)+bf(2n+1)=(b+1)f(n) + bf(n+1) \]

Tương tự, đưa biến \(a\) vào phương trình:

\[af(2n)+bf(2n+1)=(a+b)f(n) + bf(n+1) \tag{5} \]

Hai vế đã cùng dạng như mình ao ước rồi đó, giờ định nghĩa hàm phụ \(F\) thôi:

\[F(a, b, n) = af(n) + bf(n+1) \]

Từ đó ta biểu diễn \((5)\) theo \(F\) như sau:

\[F(a,b,2n) = F(a+b,b,n) \tag{*} \]

Ngoài ra từ định nghĩa của \(F\) suy ra được:

\[F(a,b,0) = af(0) + bf(1) = b \tag{6.1} \]

Và:

\[F(a,b,1) = af(1) + bf(2) = a + b \tag{6.2} \]

Hơn nữa:

\[f(n) = 1f(n) + 0f(n+1) = F(1,0,n) \tag{7} \]

Ngừng lại một chút, tới đây ta vẫn chưa thể triển khai thành thuật toán hoàn chỉnh được, tại sao ư? Để ý \((*)\) chỉ được định nghĩa với \(2n\), tức khi input là số chẵn, vậy còn lẻ thì sao? Đơn giản thôi, thế trường hợp input lẻ vào \(F\) rồi biến đổi, tức là:

\[\begin{align*} F(a,b,2n+1) &= af(2n+1) + bf(n+1)\\ &= a[f(n) + f(n+1)] + bf(n+1)\\ &= af(n) + (a+b)f(n+1)\\ &= F(a,a+b,n) \tag{**} \end{align*} \]

Ta tổng hợp lại được như sau:

  • \((7)\) cho ta định nghĩa tổng quát của \(f(n)\) dựa trên \(F\).
  • \((*)\) cho ta công thức đệ quy của \(F\) đối với trường hợp input chẵn, tương tự với \((**)\) ở trường hợp input lẻ.
  • \((6.1)\) và \((6.2)\) cho ta base case đệ quy của \(F\).

Code thoai:

function fusc(n) {

    function F(a, b, k) {
        if (k === 0)  // See (6.1)
            return b
        else if (k === 1)  // See (6.2)
            return a + b
        else if (k % 2 === 0)  // See (*)
            return F(a+b, b, Math.round(k / 2))
        else  // See (**)
            return F(a, a+b, Math.round((k-1) / 2))
    }

    return F(1, 0, n)  // See (7)
}

Submit thử:
submit-code-img
Ngon lành chứ hả, bonus cho mấy bạn thêm code Haskell nè:

fusc :: Integer -> Integer
fusc n = aux 1 0 n
  where
    aux _ b 0 = b
    aux a b 1 = a+b
    aux a b n
      | even n = aux (a+b) b (n `div` 2)
      | otherwise = aux a (a+b) ((n-1) `div` 2)

Tui biết có một số bạn đọc tới đây rồi thì ngứa lắm, có thể bạn sẽ thắc mắc tại sao không dùng quy hoạch động? Thì đầu tiên là tui đang muốn nhấn mạnh về phương pháp này, nên quy hoạch động không nằm trong khuôn khổ của bài viết. Thứ 2 là quy hoạch động thật ra cũng không hiệu quả bằng đâu, tui cũng có thử implement quy hoạch động xong submit thử rồi nhưng nó tốn quá nhiều bộ nhớ, codewars không accept (người ta tính hết rồi ^^).

Góc nhìn của tui về phương pháp này

Trong pure functional programming language (FP) như Haskell thì không có vòng lặp cho bạn dùng, thay vào đó nếu bạn muốn lặp thì bạn phải xây dựng đệ quy. Mà thực tế có những tính năng bạn cần lặp vô hạn hoặc lặp rất nhiều lần, để không bị stack overflow trên những tính năng đó thì họ phải hướng tới tail recursion. Vậy làm sao để xây dựng tail recursion? ừa thì linh cảm, tâm linh là chính thôi, lấy ví dụ cho hàm tính giai thừa:

// Đệ quy thông thường
function fact(n) {
    if (n === 1)
        return 1
    else
        return n * fact(n-1)
}

// Tail recursion
function fact(n, acc) {
    if (n === 1)
        return acc
    else
        return fact(n-1, acc*n)
}
fact(10, 1) // tính 10!

Hàm đệ quy thông thường thì đơn giản rồi mình sẽ không nhắc tới nhé. Còn phần tail recursion ở dưới mình có thể hiểu là ta cần 1 biến nhân dồn kết quả lại, gọi là acc (accumulator). acc có giá trị ban đầu là 1, mỗi lần gọi đệ quy thì ta nhân n vô acc, đồng thời giảm n xuống một đơn vị, rồi truyền vào đệ quy kế tiếp. Cứ truyền xuống như vậy, lúc này bạn sẽ thấy acc mang giá trị của tích n(n-1)(n-2)... và cũng là kết quả mình cần tìm khi n giảm xuống 1.

Đây cũng là pattern chung trong phương pháp tìm tail recursion, ta sẽ có biến tích luỹ acc là tham số được truyền dần xuống, và nó sẽ đem theo kết quả cho đến khi chạm base case. Nhưng ta có thể thấy pattern trên chỉ do mình cảm giác và tưởng tượng (aka tâm linh) chứ không được chứng minh rõ ràng, và ban đầu mình cũng nghĩ mấy thứ này không thể chứng minh được cho đến khi gặp bài toán xịn xò mà mình đã giải quyết bên trên.

Góc bài tập về nhà: Bạn có thể thử suy nghĩ cách chứng minh định nghĩa hàm fact(n, acc) bên trên là đúng dựa trên phương pháp chặt chẽ của bài viết. Và xây dựng lại tail recursion cho fib(n) dựa trên phương pháp tâm linh này, bạn sẽ bất ngờ vì nó cho cùng một kết quả đó.

Cảm ơn mấy bạn đã đọc hết đến đây (hoặc là do bạn lướt xuống và gặp được dòng này). Đây là bài viết đầu tiên trên blog của tui, tui xin nhận mọi ý kiến đóng góp, nhưng nếu bạn có ý định ném đá thì nên cân nhắc lời lẽ phù hợp với trái tim mỏng manh của tác giả 😢.