Làm Chủ Đệ Quy & Memoization Ruby: Hướng Dẫn Thực Hành

Đệ quy (recursion) trong Ruby là gì?

Hàm đệ quy là hàm liên tục gọi chính nó cho đến khi đạt mục tiêu kết thúc (còn gọi là base case). Sau mỗi lời gọi hàm, bạn tiến gần base case, giảm công việc còn lại.

Khi base case đạt được, đệ quy kết thúc, và các hàm bắt đầu trả về.

Đệ Quy Ruby

Ví dụ kinh điển bắt đầu học đệ quy là tính giai thừa (factorial).

Xem cách làm trong Ruby dùng cả iteration & recursion!

Tính giai thừa số, nhân tất cả số từ 1 đến số mục tiêu. Ví dụ giai thừa 5: 1 * 2 * 3 * 4 * 5 = 120.

Xem cách dùng Ruby và đệ quy.

Ví dụ:

def iterative_factorial(n)
  (1..n).inject(:*)
end
def recursive_factorial(n)
  # Base case
  return 1 if n <= 1
  # Recursive call
  n * recursive_factorial(n-1)
end

Ví dụ này cho thấy hai cách tính giai thừa. Giải pháp lặp và giải pháp đệ quy.

Trong giải pháp đệ quy, tiến bộ bằng cách giảm số làm việc (n-1). Khi (n <= 1) không còn lời gọi đệ quy, và đây là chuyện xảy ra:

return 1 # recursive_factorial(1)
return 2 * 1 # recursive_factorial(2)
return 3 * 2 # recursive_factorial(3)
return 4 * 6 # recursive_factorial(4)
return 5 * 24 # recursive_factorial(5)

Là Ruby developer, chúng ta chọn giải pháp lặp hầu hết thời gian, và tuyệt vời, nhưng nghĩ vẫn đáng biết đệ quy hoạt động ra sao.

Bây giờ xem ví dụ kinh điển khác: dãy Fibonacci.

Dãy Fibonacci

Leonardo Fibonacci khám phá dãy này khi điều tra mô hình tăng dân số thỏ điều kiện lý tưởng.

Dãy tính bằng cách cộng hai số trước số hiện tại.

Ví dụ:

1, 1, 2, 3, 5, 8, 13, 21

Tính trong Ruby dùng hàm đệ quy:

def fib(n)
  return n if n < 2
  fib(n-1) + fib(n-2)
end

Dùng hàm này và range dễ dàng tính 20 số Fibonacci đầu.

(1..20).each { |n| puts fib(n) }

Tuy nhiên, có vấn đề:

Hàm làm nhiều việc thừa không cần. Để minh họa, xem hình sau.

Trong hình thấy fib(3) tính năm lần. Làm hàm thật chậm nếu tính dãy Fibonacci dài.

Giải pháp? Memoization.

Memoization: Tái Sử Dụng Công Việc Đã Làm

Tuyệt vời nếu tái sử dụng công việc đã làm ở bước trước?

Làm được nhờ memoization.

Lưu kết quả tính toán tốn kém dùng cache. Trường hợp này, mảng đủ.

Ví dụ:

@cache = [0,1]
def fib(n)
  return @cache[n] if @cache[n]
  @cache[n] = fib(n-1) + fib(n-2)
end

Trước kiểm tra kết quả đã có trong cache, nếu có trả về, không thì tính và lưu.

Chạy nhanh hơn nhiều và tính được số Fibonacci lớn hơn.

Giới Hạn Của Đệ Quy

Như độc giả chỉ ra, giải pháp đệ quy thất bại SystemStackError: stack level too deep với số đầu vào lớn (khoảng 7500, số chính xác phụ thuộc hệ thống).

Cần tính số lớn hơn phải dùng giải pháp lặp.

Ví dụ:

memo = []
(0..n).each do |i|
  memo[i] = i < 2 ? i : memo[i-1] + memo[i-2]
end

Kết Luận

Đệ quy tuyệt vời nhưng đôi khi khó nắm. Bây giờ đến lượt bạn, thực hành tạo nên sự thành thạo!

Chia sẻ bài viết nếu thích & đăng ký bản tin 🙂