Tail recursion là gì? Tại sao nên áp dụng tail recursion khi dùng đệ quy.

[viettrungphan]

Bắt đầu với functional programming, chúng ta phải làm quen và nắm vững recursive, thay vì for, while sử dụng phổ biếng trong OOP. Chính vì thế việc tối ưu bộ nhớ khi sử dụng đệ quy là điểm cần lưu ý. Vậy Tail recursion là gì, nó giúp thế nào trong việc tối ưu bộ nhớ?

Cho ví dụ bài toán tính giai thừa sử dụng đệ quy sử dụng ngôn ngữ Elixir

defmodule Math do
  defp factorial(0) do
    1
  end
  defp factorial(n) when n > 0 do
    n * factorial(n-1)
  end
end

Các bước gọi hàm Math.factorial(3) => Phân tích ra

factorial(3) 3 factorial(3-1) 3 factorial(2 factorial(2-1)) 3 factorial(2 factorial(1 factorial(1-1))) 3 factorial(2 factorial(1 factorial(0))) 3 (2 (1 1))

Đối với đệ quy (body recursion), mỗi bước function gọi lại chính nó thì 1 lượng bộ nhớ lại được cấp phát thêm cho function mới và giữ trong RAM cho đến khi tất cả các sub function được tính toán xong, gộp kết quả lại, do đó bộ nhớ sẽ tăng lên rất nhanh nếu hàm đệ quy của chúng ta gọi nhiều lần. ví dụ gọi hàm giai thừa cho 10.000.000 ~ 5.6GB bộ nhớ dùng cho hàm tính toán giai thừa này.

Improve hàm đệ quy trên, thay vì chờ kết quả của các sub function, ta lưu giữ kết quả tính toán qua từng bước gọi. Thay vì hold các function(multiple heavyweight) ta chỉ hold kết quả tính toán và truyền qua từng bước(one lightweight object).

defmodule MathWithTailRecusive do
  def factorial(n), do: factorial_of(n, 1)
  defp factorial_of(0, acc) do
    acc
  end
  defp factorial_of(n, acc) when n > 0 do
    factorial_of(n-1, n * acc)
  end

end

Các bước gọi hàm MathWithTailRecusive.factorial(3) => Phân tích ra

factorial (3) factorial_of (2, 3 1) factorial_of (1, 3 2) factorial_of (0, 6) 6

So sánh bộ nhớ sử dụng khi tính toán giai thừa 10.000.000 bằng tail recursion , chỉ 42MB so với 5.6GB của body recursion, một sự khác biệt cực lớn.

Kết luận:

• Body Recursive: +Nhược điểm: tốn bộ nhớ, cần lưu ý khi khi hàm của chúng ta lặp nhiều lần +Ưu điểm: dễ đọc và nắm bắt logic có thể dùng cho các hàm giai thừa mà chúng ta đoán biết số bước gọi đệ quy nhỏ. -Tail Recursive: +Nhược điểm: Khó viết đối với các bài toán phức tạp, khó nắm bắt logic khi đọc code. +Ưu điểm: tối ưu bộ nhớ.

Tham khảo thêm tại: https://stackoverflow.com/questions/33923/what-is-tail-recursion