Đệ quy trong Ruby là gì?
Hàm đệ quy là những hàm tiếp tục tự gọi cho đến khi chúng đạt được mục tiêu cuối cùng (còn được gọi là trường hợp cơ sở ). Sau mỗi lần gọi hàm, bạn thực hiện được tiến bộ đối với trường hợp cơ sở này, giảm số lượng công việc còn lại phải thực hiện.
Khi đạt đến trường hợp cơ sở, đệ quy kết thúc và các hàm bắt đầu trả về.
Đệ quy Ruby
Một ví dụ cổ điển để bắt đầu tìm hiểu về đệ quy là tính một số giai thừa.
Hãy xem cách chúng ta có thể thực hiện điều này trong Ruby bằng cách sử dụng cả lặp và đệ quy!
Để tính giai thừa của một số, chúng ta phải nhân tất cả các số từ 1 với số đích của chúng ta. Ví dụ:giai thừa của 5 là:1 * 2 * 3 * 4 * 5 = 120 .
Hãy xem cách chúng ta có thể làm điều này bằng cách sử dụng Ruby và đệ quy.
Ví dụ :
def iterative_factorial (n) (1..n) .inject (:*) enddef recursive_factorial (n) # Trường hợp cơ sở trả về 1 nếu n <=1 # Lời gọi đệ quy n * recursive_factorial (n-1) end
Trong ví dụ này, tôi chỉ cho bạn hai cách để tính một số giai thừa. Giải pháp lặp và giải pháp đệ quy.
Trong giải pháp đệ quy, chúng tôi đạt được tiến bộ bằng cách giảm số chúng tôi đang làm việc với (n-1). Sau khi (n <=1) không có lệnh gọi đệ quy nào nữa và đây là những gì sẽ 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)
Với tư cách là các nhà phát triển Ruby, chúng tôi hầu hết sử dụng giải pháp lặp đi lặp lại và điều đó thật tuyệt, nhưng tôi nghĩ vẫn đáng để biết cách hoạt động của đệ quy.
Bây giờ chúng ta hãy xem một ví dụ cổ điển khác:Số Fibonacci.
Chuỗi Fibonacci
Leonardo Fibonacci đã phát hiện ra chuỗi này khi nghiên cứu cách lập mô hình sự tăng trưởng của quần thể thỏ trong điều kiện lý tưởng.
Dãy số được tính bằng cách cộng hai số đứng trước số hiện tại.
Ví dụ :
1, 1, 2, 3, 5, 8, 13, 21
Để tính toán điều này trong Ruby, bạn có thể sử dụng một hàm đệ quy:
def fib (n) trả về n nếu n <2 fib (n-1) + fib (n-2) end
Sử dụng hàm này và một phạm vi, bạn có thể dễ dàng tính toán 20 số Fibonacci đầu tiên.
(1..20) .each {| n | đặt fib (n)} Tuy nhiên, có một vấn đề :
Chức năng của bạn đang thực hiện rất nhiều công việc bổ sung mà nó không cần thiết. Để minh họa điều này, hãy xem hình ảnh sau đây.
Trong hình ảnh, chúng ta có thể thấy cách fib (3) được tính năm lần. Điều này làm cho hàm của bạn thực sự chậm nếu bạn cố gắng tính toán các chuỗi Fibonacci dài hơn.
Giải pháp? Ghi nhớ.
Ghi nhớ:Sử dụng lại công việc chúng tôi đã làm
Sẽ thật tuyệt nếu bạn chỉ có thể sử dụng lại công việc bạn đã làm ở các bước trước phải không?
Chúng tôi có thể làm điều đó bằng cách sử dụng ghi nhớ .
Để lưu kết quả tính toán đắt tiền của chúng tôi, chúng tôi sử dụng bộ nhớ cache. Trong trường hợp này, một mảng sẽ thực hiện.
Ví dụ :
@cache =[0,1] def fib (n) return @cache [n] if @cache [n] @cache [n] =fib (n-1) + fib (n-2) endĐầu tiên, chúng tôi kiểm tra xem kết quả đã có trong bộ nhớ đệm chưa, nếu có thì trả về, nếu không chúng tôi thực hiện phép tính và lưu kết quả.
Điều này sẽ chạy nhanh hơn rất nhiều và nó sẽ có thể tính toán các số Fibonacci lớn hơn nhiều.
Giới hạn của đệ quy
Như một độc giả vui lòng chỉ ra, giải pháp đệ quy có thể không thành công với
SystemStackError: stack level too deepvới các số đầu vào lớn (khoảng 7500, con số chính xác tùy thuộc vào hệ thống của bạn).Nếu bạn cần tính một số lớn hơn, bạn sẽ phải sử dụng giải pháp lặp lại.
Ví dụ :
memo =[] (0..n) .each do | i | memo [i] =i <2? i:memo [i-1] + memo [i-2] endKết luận
Đệ quy rất tốt nhưng đôi khi khó nắm bắt được. Bây giờ đến lượt bạn, hãy luyện tập để làm chủ!
Hãy chia sẻ bài đăng này nếu bạn thích nó và đăng ký nhận bản tin của tôi 🙂