Giải mã đệ quy: Hiểu rõ sự kỳ diệu đằng sau nó

Mục lục

Đệ quy là gì?

Đệ quy là một kỹ thuật lập trình trong đó một hàm gọi chính nó để giải quyết vấn đề. Nó hữu ích cho các tác vụ có thể được chia nhỏ thành các vấn đề con tương tự nhau.

Ưu điểm

• Giải pháp tinh tế cho một số vấn đề. Ví dụ: Bài toán Tháp Hà Nội: Di chuyển một chồng đĩa từ cọc này sang cọc khác, tuân theo các quy tắc cụ thể.
• Đơn giản hóa các thuật toán phức tạp. Ví dụ: Sắp xếp trộn: Chia một mảng thành các phần nhỏ hơn, sắp xếp chúng, sau đó kết hợp lại.
• Hữu ích cho các cấu trúc dạng cây. Ví dụ: Khám phá cây gia phả: Bắt đầu với một người, sau đó đệ quy khám phá cha mẹ, ông bà của họ, v.v.

Nhược điểm

• Có thể tốn nhiều bộ nhớ. Ví dụ: Tính toán số Fibonacci bằng đệ quy: Mỗi lần gọi tạo ra các phân bổ bộ nhớ mới, có khả năng dẫn đến tràn ngăn xếp cho các đầu vào lớn.
• Đôi khi chậm hơn giải pháp lặp. Ví dụ: Đếm ngược từ 100 đến 1: Đệ quy sẽ thực hiện 100 lần gọi hàm, trong khi một vòng lặp đơn giản hiệu quả hơn.
• Có thể gây khó hiểu cho người mới bắt đầu

Ví dụ: Tính giai thừa

Cách tiếp cận đệ quy

def factorial(n)
  return 1 if n <= 1
  n * factorial(n - 1)
end

Các bước:

1. factorial(5) được gọi
   • 5 > 1, nên nó trả về 5 * factorial(4)
2. factorial(4) được gọi
   • 4 > 1, nên nó trả về 4 * factorial(3)
3. factorial(3) được gọi
   • 3 > 1, nên nó trả về 3 * factorial(2)
4. factorial(2) được gọi
   • 2 > 1, nên nó trả về 2 * factorial(1)
5. factorial(1) được gọi
   • 1 <= 1, nên nó trả về 1
6. Bây giờ chúng ta tính ngược lại:
   • 2 * 1 = 2
   • 3 * 2 = 6
   • 4 * 6 = 24
   • 5 * 24 = 120

Mỗi bước chờ bước tiếp theo hoàn thành trước khi nó có thể kết thúc tính toán của mình.

Chuyển sang cách lặp

def factorial_iterative(n)
  result = 1
  (1..n).each { |i| result *= i }
  result
end

Các bước:

1. result bắt đầu từ 1
2. Vòng lặp bắt đầu:
   • i = 1: result = 1 * 1 = 1
   • i = 2: result = 1 * 2 = 2
   • i = 3: result = 2 * 3 = 6
   • i = 4: result = 6 * 4 = 24
   • i = 5: result = 24 * 5 = 120
3. Vòng lặp kết thúc, trả về 120

Mỗi bước ngay lập tức tính toán và cập nhật kết quả.

Ví dụ: Dãy Fibonacci

Cách tiếp cận đệ quy

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

Các bước:

1. fibonacci(5) được gọi
   • Nó gọi fibonacci(4) + fibonacci(3)
2. fibonacci(4) được gọi
   • Nó gọi fibonacci(3) + fibonacci(2)
3. fibonacci(3) được gọi (lần đầu tiên)
   • Nó gọi fibonacci(2) + fibonacci(1)
4. fibonacci(2) được gọi (lần đầu tiên)
   • Nó gọi fibonacci(1) + fibonacci(0)
5. fibonacci(1) trả về 1
6. fibonacci(0) trả về 0
7. fibonacci(2) hoàn thành: 1 + 0 = 1
8. fibonacci(1) trả về 1
9. fibonacci(3) hoàn thành: 1 + 1 = 2
10. fibonacci(2) được gọi lại (lần thứ hai)
    • Nó gọi fibonacci(1) + fibonacci(0)
11. fibonacci(1) trả về 1
12. fibonacci(0) trả về 0
13. fibonacci(2) hoàn thành: 1 + 0 = 1
14. fibonacci(4) hoàn thành: 2 + 1 = 3
15. fibonacci(3) được gọi lại (lần thứ hai)
    • Nó gọi fibonacci(2) + fibonacci(1)
16. Quá trình lặp lại...
17. Cuối cùng, fibonacci(5) hoàn thành: 3 + 2 = 5

Chú ý cách fibonacci(3) và fibonacci(2) được tính toán nhiều lần.

Chuyển sang cách lặp

def fibonacci_iterative(n)
  a, b = 0, 1
  n.times { a, b = b, a + b }
  a
end

Các bước:

1. a = 0, b = 1
2. Lặp 5 lần:
   • Lần lặp thứ 1: a = 1, b = 0 + 1 = 1
   • Lần lặp thứ 2: a = 1, b = 1 + 1 = 2
   • Lần lặp thứ 3: a = 2, b = 1 + 2 = 3
   • Lần lặp thứ 4: a = 3, b = 2 + 3 = 5
   • Lần lặp thứ 5: a = 5, b = 3 + 5 = 8
3. Trả về a, là 5

Mỗi bước xây dựng trên kết quả trước đó mà không lặp lại các tính toán.

Điểm chính

• Gọi hàm: Mỗi lần một hàm gọi chính nó, nó giống như bắt đầu một nhiệm vụ mới trước khi hoàn thành nhiệm vụ hiện tại. Điều này tiêu tốn bộ nhớ và thời gian.
• Lặp lại: Các hàm đệ quy thường lặp lại các tính toán giống nhau, trong khi các hàm lặp thường không.
• Sử dụng bộ nhớ: Các hàm đệ quy giữ thông tin cho mỗi lần gọi trong bộ nhớ. Các hàm lặp thường sử dụng một lượng bộ nhớ cố định bất kể kích thước đầu vào.
• Khả năng dự đoán: Các hàm lặp dễ dự đoán hơn về thời gian thực hiện và lượng bộ nhớ sử dụng.
• Khả năng đọc hiểu: Đôi khi các hàm đệ quy dễ hiểu hơn, nhưng hiệu suất của chúng có thể kém hơn.
• Phiên bản lặp nhanh hơn nhiều, đặc biệt là với các số lớn, vì nó không lặp lại các tính toán.
• Cách tiếp cận đệ quy liên tục tính toán lại các giá trị giống nhau, dẫn đến nhiều lần gọi hàm và lặp lại công việc.
• Cách tiếp cận lặp tính toán mỗi giá trị một lần, xây dựng trên các kết quả trước đó, hiệu quả hơn.

Đệ quy đuôi (đệ quy được tối ưu hóa)

def fibonacci_tail(n, a = 0, b = 1)
  return a if n == 0
  fibonacci_tail(n - 1, b, a + b)
end

Đây là một loại đệ quy đặc biệt mà một số máy tính có thể tự động chuyển đổi thành lặp. Nó giống như việc để lại một ghi chú cho bản thân trước khi leo mỗi bậc thang, để bạn không phải leo xuống. Tuy nhiên, không phải tất cả các ngôn ngữ lập trình hoặc máy tính có thể làm điều này tự động, vì vậy lặp vẫn thường được ưa chuộng hơn.

Nói chung, lặp thường tốt hơn về hiệu suất vì:

• Nó sử dụng ít bộ nhớ hơn - bạn không chồng chất các lần gọi hàm.
• Nó thường nhanh hơn - bạn không lặp lại công việc bạn đã làm.
• Nó dễ dự đoán hơn - bạn sẽ không đột ngột hết bộ nhớ cho các đầu vào lớn.

Hãy nhớ rằng, đối với các đầu vào nhỏ, bạn có thể không nhận thấy sự khác biệt. Nhưng khi đầu vào trở nên lớn hơn, những cải tiến về hiệu suất này trở nên quan trọng hơn.

Điểm chính khi chuyển đổi đệ quy sang lặp

• Sử dụng vòng lặp (while, for, v.v.) thay vì gọi đệ quy
• Triển khai ngăn xếp hoặc biến trạng thái để theo dõi tiến trình
• Xác định trường hợp cơ sở và sử dụng nó làm điều kiện kết thúc vòng lặp

Khi nào nên sử dụng đệ quy

• Duyệt cây
• Thuật toán chia để trị
• Các vấn đề có cấu trúc đệ quy tự nhiên

Khi nào nên tránh đệ quy

• Mã quan trọng về hiệu suất
• Các vấn đề có giải pháp lặp đơn giản
• Khi có lo ngại về tràn ngăn xếp