Đệ quy trong lập trình (Script Recursion)

Đệ quy trong lập trình là một kỹ thuật – chủ yếu được sử dụng trong các ngôn ngữ lập trình hàm – để chia một vấn đề lớn thành các vấn đề con nhỏ hơn, giống hệt nhau. Đệ quy giúp đơn giản hóa quá trình giải quyết vấn đề bằng cách cho phép biểu diễn lời giải dưới dạng một phiên bản nhỏ hơn của chính vấn đề đó.

• Giải quyết vấn đề phức tạp: Khi chia một bài toán phức tạp thành các bài toán nhỏ hơn và dễ quản lý hơn, giải pháp trở nên rõ ràng và dễ hiểu hơn.

• Thuật toán chia để trị (divide and conquer): Những thuật toán này thường sử dụng cấu trúc đệ quy, chia nhỏ bài toán, giải quyết từng phần và sau đó kết hợp lại để ra kết quả cuối cùng.

• Fractal (hình học phân dạng): Đệ quy thường được dùng để tạo ra các mẫu hình fractal, nơi một hình học được lặp lại ở các tỷ lệ khác nhau trong cùng một cấu trúc. Điều này là do fractal thường vẽ lặp đi lặp lại một hoặc nhiều phiên bản biến đổi của cùng một hình.

• Đơn giản: Các lời giải đệ quy có thể đơn giản và dễ hiểu hơn, đặc biệt với một số loại bài toán.

• Tự nhiên với một số vấn đề: Đệ quy phù hợp với các bài toán mà tự nhiên chia nhỏ thành những bài toán con tương tự.

• Tái sử dụng mã: Hàm đệ quy có thể tái sử dụng trong nhiều ngữ cảnh, giúp giữ cho mã gọn và có tính mô-đun.

• Tràn ngăn xếp (Stack Overflow): Đệ quy quá sâu có thể dẫn đến lỗi “tràn ngăn xếp”.

• Hiệu năng: Đệ quy không phải lúc nào cũng tối ưu nhất về tốc độ. Giải pháp lặp (iterative) đôi khi nhanh hơn.

• Khó debug: Việc gỡ lỗi code đệ quy có thể phức tạp, đặc biệt khi mức độ đệ quy quá sâu.

1. Ví dụ đầu tiên là hàm đệ quy tính số Fibonacci:

function fibRecursion(n)
    if n < 0 then 
        error("Invalid number.")
        return 0
    end
 
    if n <= 1 then
        return n
    else
        return fibRecursion(n-1) + fibRecursion(n-2)
    end
end

• Nếu số nhỏ hơn 0, sẽ báo lỗi.
• Nếu số nhỏ hơn hoặc bằng 1, trả lại chính nó.
• Nếu lớn hơn 1, trả về tổng của (n-1) và (n-2).
  Chúng ta có thể gọi hàm này để lấy số Fibonacci ở vị trí n.

2. Thêm vòng lặp for để in ra dãy số từ vị trí 1 đến 12:

function fibRecursion(n)
    if n < 0 then 
        error("Invalid number.")
        return 0
    end
 
    if n <= 1 then
        return n
    else
        return fibRecursion(n-1) + fibRecursion(n-2)
    end
end
 
for i=1, 12 do
    print("Số Fibonacci ở vị trí ".. i.. ": ".. fibRecursion(i))
end

Kết quả in ra: “0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144”
Khi chạy chương trình, ta sẽ thấy kết quả đúng như trên.

Chú thích thêm:

1. Tràn ngăn xếp là gì? Hãy tưởng tượng bạn đang xây một tòa tháp bằng gạch. Mỗi lần gọi một hàm là thêm một viên gạch. Nếu xếp quá nhiều, tháp sẽ đổ – đó chính là stack overflow. Máy tính sẽ nói kiểu: “Ôi không, nhiều quá! Tao xử lý không nổi!”
2. Xem thêm: Wikipedia - Stack Overflow
3. Dãy số Fibonacci là dãy số mà mỗi số là tổng của hai số trước nó, bắt đầu từ 0 và 1. Ví dụ: 0, 1, 1, 2, 3, 5, 8, 13, v.v.
4. Xem thêm: Wikipedia - Fibonacci sequence