Đệ quy là một khái niệm cực kỳ quan trọng trong lập trình và ngành khoa học máy tính nói chung. Việc sử dụng đệ quy giúp chúng ta giải quyết một loạt các bài toán thực tế trong lập trình, và vì vậy nó được áp dụng rất nhiều trong cấu trúc dữ liệu và giải thuật. Bài viết này sẽ giúp bạn hiểu rõ hơn về khái niệm đệ quy và các phương pháp để xây dựng đệ quy.
Đệ Quy Là Gì?
Trong toán học và khoa học máy tính, đệ quy (Recursion) là một phương pháp giải toán mà lời giải của bài toán phụ thuộc vào một trường hợp nhỏ hơn của cùng một bài toán đó. Trong lập trình, đệ quy được hiểu đơn giản là hàm thực thi chứa chính nó (hàm gọi chính nó) trong code.
Ví dụ đơn giản về đệ quy triển khai bằng ngôn ngữ lập trình JavaScript là hàm recursion. Hàm này có chứa đoạn gọi lại chính nó khi count thỏa mãn điều kiện nhất định.
function recursion(count) {
count++;
if (count <= 5) {
console.log("step at", count);
recursion(count);
}
}Một hàm đệ quy bao gồm hai thành phần:
- Phần cơ sở: Đây là trường hợp mà bài toán được giải quyết mà không cần phải gọi lại chính nó. Mục đích của phần cơ sở là để đảm bảo rằng vòng lặp gọi hàm sẽ dừng lại tại một điều kiện xác định, tránh việc gây ra vòng lặp vô hạn.
- Phần đệ quy: Đây là phần xử lý gọi lại hàm, các hành động này sẽ được thực hiện liên tiếp cho đến khi lời gọi đến phần cơ sở.
Đệ Quy Tuyến Tính Và Đệ Quy Nhị Phân
Trong lập trình, đệ quy có thể được chia thành 6 loại, bao gồm:
- Đệ quy tuyến tính (Linear Recursion)
- Đệ quy nhị phân (Binary Recursion)
- Đệ quy đuôi (Tail Recursive)
- Đệ quy đa tuyến (Exponential Recursive)
- Đệ quy lồng (Nested Recursion)
- Đệ quy tương hỗ (Mutual Recursion)
Các loại đệ quy này đều có cùng bản chất là đệ quy, tuy nhiên, chúng có sự khác nhau về số lượng lời gọi đệ quy trong hàm hoặc vị trí của lời gọi. 4 loại đệ quy cuối cùng ít khi được sử dụng trong lập trình, mà thường được nghiên cứu sâu hơn. Trong bài viết này, chúng ta sẽ tìm hiểu sâu hơn về đệ quy tuyến tính và đệ quy nhị phân.
Đệ Quy Tuyến Tính
Đệ quy tuyến tính là một loại đệ quy mà hàm chỉ gọi chính nó một lần trong thân hàm. Ví dụ cơ bản nhất của đệ quy tuyến tính là bài toán tính giai thừa n! trong toán học.
Đệ Quy Nhị Phân
Đệ quy nhị phân là một dạng đệ quy mà hàm gọi chính nó hai lần. Điều này có thể hiểu đơn giản là trong code triển khai, hàm sẽ được gọi đến chính nó hai lần. Một bài toán kinh điển của đệ quy nhị phân là dãy Fibonacci.
Chúng ta đã quen thuộc với công thức tạo ra dãy Fibonacci, đó là fib(n - 1) + fib(n - 2). Từ đó, dễ thấy cách triển khai đệ quy nhị phân khi cần gọi lại hàm tính fib hai lần. Câu hỏi đặt ra là có thể sử dụng đệ quy tuyến tính cho bài toán Fibonacci được không?
Câu trả lời là có, và thậm chí nó sẽ tốt hơn về tốc độ so với đệ quy nhị phân. Cách triển khai như sau:
function fib_linearR(a, b, n) {
if (n <= 2) return b;
else if (n > 2) return fib_linearR(b, a + b, n - 1);
}
//fib(10) = fib_linearR(1,1,10)Phương Pháp Xây Dựng Đệ Quy
Như đã đề cập ở trên, đệ quy bao gồm hai thành phần là phần cơ sở và phần đệ quy. Để xây dựng đệ quy, chúng ta cần xác định được logic xử lý và phạm vi của hai phần này.
Xác Định Base Case
Mục tiêu của Base Case là trả về một giá trị cụ thể để kết thúc vòng lặp đệ quy. Thông thường, Base Case sẽ được xác định với giá trị rõ ràng từ đầu. Ví dụ, trong bài toán Fibonacci, chúng ta có F(1) = 1 và F(2) = 1, hoặc trong bài toán tính giai thừa của một số, Factorial(1) = 1.
Base Case không làm thay đổi các biến hay tham số bên ngoài hàm, và luôn trả về cùng một kết quả với cùng một đầu vào. Base Case là một Pure Function, không có side effect bên ngoài phạm vi của nó.
Viết Logic Đệ Quy
Logic đệ quy là việc xác định khi nào (vị trí) gọi lại hàm đệ quy và mỗi lần gọi lại thì vấn đề được thu nhỏ hơn (bài toán con). Sau mỗi lần gọi lại hàm đệ quy, bài toán ban đầu trở nên dễ dàng tính toán hơn và đảm bảo rằng nó sẽ kết thúc vào một trong các Base Case đã xây dựng.
Ví dụ, để tính F(5) trong dãy Fibonacci, chúng ta sẽ gọi lại hàm tính F(4) và F(3) là các bài toán con nhỏ hơn, dễ tính hơn. Cuối cùng, chúng ta sẽ gọi lại F(2) và F(1) - đó là các Base Case.
Phần đệ quy là một Non-Pure Function, nó sử dụng các tham số bên ngoài hoặc ít nhất là đọc dữ liệu từ bên ngoài. Ngoài ra, một số bài toán có thể có nhiều lời giải cho cùng một đầu vào, ví dụ như bài toán tìm đường đi ngắn nhất.
Kết Bài
Đệ quy là một khái niệm cơ bản trong lập trình và giải quyết các bài toán thực tế. Nhờ sự linh hoạt và tiềm năng của nó, đệ quy được áp dụng rộng rãi trong cấu trúc dữ liệu và giải thuật. Hi vọng thông qua bài viết này, bạn đã hiểu rõ hơn về đệ quy, các loại đệ quy và phương pháp để xây dựng đệ quy trong lập trình. Tận dụng kiến thức này để áp dụng một cách hiệu quả nhất trong công việc lập trình của bạn. Hẹn gặp lại trong các bài viết tiếp theo của chúng tôi.
Tác giả: Phạm Minh Khoa
