Đệ quy - Recursion.

Đệ quy tên tiếng anh là Recursion là một phương pháp được dùng trong các chương trình máy tính, mà trong đó có một hàm tự gọi chính bản thân nó.

Khái miện hình thức về đệ quy:

Trong toán học và khoa học máy tính, các tính chất hoặc cấu trúc được gọi là đệ quy, nếu trong đó có một lớp các đối tượng hoặc phương pháp được định nghĩa hay xác định bởi một số rất ít các đối tượng hoặc phương pháp đơn giản(thông thường chỉ một) và sau đó xác định quy tắc đưa các trường hợp phức tạp về các trường hợp đơn giản.

Như vậy để một lớp đối tượng hoặc một phương thức có đệ quy thì phải hội đủ 2 định nghĩa sau:

• Một Trường hợp cơ sở cơ bản.(Trường hợp đơn giản - Basic case) - [Một lớp các đối tượng hoặc phương pháp được định nghĩa hay xác định bởi một số rất ít các đối tượng hoặc phương pháp đơn giản.]
• Một tập hợp các quy tắc làm đơn giản hóa các trường hợp khác dựa trên trường hợp cơ sở cơ bản.(Đệ quy - Recursion) - [Xác định quy tắc đưa các trường hợp phức tạp về các trường hợp đơn giản.]

Hơi khó hiểu phải không bạn có thể tạm thời hiểu đơn giản trước  là các tính chất hoặc cấu trúc được gọi là đệ quy khi các tính chất hoặc cấu trúc đó được định nghĩa trên chính bản thân của nó.


Phân tích đệ quy:

Để hiểu rõ hơn ta sẽ phân tích một vài định định nghĩa, bạn hiểu như thế nào về định nghĩa của từ tổ tiên? Theo định nghĩa thông thường sẽ là:

• Bố mẹ của một người là tổ tiên của người ấy.(Trường hợp cơ bản)
• Bố mẹ của tổ tiên một người là tổ tiên của người ấy.(Trường hợp đệ quy)
• Bố mẹ của tổ tiên của tổ tiên của một người là tổ tiên của người ấy.(Trường hợp đệ quy)

Như định nghĩa trên là định nghĩa về mặt lý thuyết trên văn nói thì ta khó hình dung được cách áp dụng đệ quy được áp dụng như thế nào, nên ta sẽ dùng một ví dụ toán học là dãy Fibonacci(dãy vô hạn của các số tự nhiên) bạn có thể tìm hiểu định nghĩa tại Wikipedia, đây là một ví dụ cổ điển về tính đệ quy.

Ta sẽ phân tích các thành phần cơ bản trong dãy Fibonacci trước.

• Ta có định nghĩa Fib(0) là bằng 0.(Trường hợp cơ bản - Base case)
• Ta có định nghĩa Fib(1) là bằng 1.(Trường hợp cơ bản - Base case)

Theo dãy Fibonacci thì khi tính số vô hạn n - Fib(n) thì sẽ được định nghĩa như sau:

• Fib(n) = Fib(n-1) + Fib(n-2).(Trường hợp đệ quy)

Như ta thấy định nghĩa một số Fib cấu thình từ 2 phần như trong định nghĩa về đệ quy, vì vậy ta có thể khảnh định dãy số vô hạn Fibonacci có tính đệ quy.


Đệ quy trong lập trình Java:

Tôi xin trình bây thêm về tính đệ quy trong ngôn ngữ lập trình Java, ở đây tôi sẽ lấy ví dụ dãy số vô hạn Fibonacci để viết một chương trình tính số Fibonacci.

Trước tiên ta xem qua công thức Fibonocacci rùi mới tiến hành chuyển sang code.

Dưới đây là toàn bộ mã của ví dụ, bạn tham khảo trước khi đi vào phân tích cụ thể.

 /**
 * @(#)Fibonacy.java
 *
 * Fibonacy application
 *
 * @author VNLIVES.NET
 * @version 1.00 2013/9/22
 */

public class Fibonacy {

    public static void main(String[] args) {
        System.out.println("Finbonacy: 3 - " + Fibo(3));
                                  
    }

    public static int Fibo(int n) {

        if(n == 0) {
            return 0;
        }
       
        if(n == 1) {
            return 1;
        }

        return (Fibo(n-1) + Fibo(n-2));

    } 

}

Kết quả sau khi thực thi là:

 2

Bây giờ ta sẽ phân tích cách hoạt động của đoạn mã trên. Khi ta truyền tham số 3 vào hàm int Fibo(int n) thì tiến trình chạy có thể được phân tích như sau:

Fibo(3)
= Fibo(3 - 1) + Fibo(3 - 2)
= Fibo(2) + Fibo(1)
= Fibo(2-1) + Fibo(2-2) + Fibo(1)
= Fibo(1) + Fibo(0) + Fibo(1)
= 1 + 0 + 1
= 2

Phù.... Cuối cùng cũng viết xong, ngồi suy nghĩ văn phong để giải thích muốn đuối luôn, nếu có gì thiếu sót các bạn thông cảm lần đầu tiên viết mấy cái dạng bài phân tích toán học kiểu này.

Có viết mới biết hiểu là một chuyện, trình bày lại là một truyện khác, trình bày cho người khác hiểu thì lại là một chuyện khác nữa,...bị nhiễm đệ quy luôn rù ^^! Nói thật lúc học mấy bài toán tin thì chả hiểu cái gì hết, toàn học thuộc lòng để thi hem à.

Nếu bài viết còn chỗ nào khó hiểu, chưa rõ nghĩa, hoặc có sai xót gì, thì mong được sự đóng góp của các bạn để mình kịp thời chỉnh sửa cho hợp lý. Rất mong được sự đóng góp của các bạn gần xa.



Write: +Bui Ngoc Son