Đệ quy trong ngôn ngữ lập trình C#


        Đệ quy (Recursion) là một phương pháp, một kỹ thuật dùng để giải các bài toán, vấn đề (problem) trong khoa học máy tính nói chung (computer science) dành cho việc giải các nhóm bài toán có thể chia để trị trên cơ sở bài toán lớn có thể chia được thành bài toán nhỏ hơn nhưng phải có sự tương đồng về cấu trúc (solution depends on solutions to smaller instances of the same problem). Phương pháp hay kỹ thuật đệ quy hiện nay các bạn có thể thấy nó được thể hiện trên tất cả các ngôn ngữ lập trình khác nhau như C, C++, Java, C#, Visual Basic, Python,…và nó là một trong những kỹ thuật cơ bản nhất của khoa học máy tính (computer science). Đệ quy được ứng dụng trong rất nhiều bài toán thực tế và bài viết này sẽ trình bày một số bài toán ứng dụng phương pháp Đệ quy trong ngôn ngữ lập trình C#.

Recursion with C#


       Điểm khó khăn nhất của phương pháp Đệ quy (Recursion) chính là việc nhận diện ra bài toán cơ sở, để từ đó thực hiện việc áp dụng phương pháp đệ quy để giải triệt để bài toán. Trong mỗi bài toán cơ sở của đệ quy phải có một điểm dừng nếu không có điểm dừng này bài toán đệ quy sẽ rơi vào vòng lặp vô hạn. Dưới đây hãy xem xét bài toán tính giai thừa sử dụng phương pháp đệ quy trong C#.

1.  Ví dụ sử dụng đệ quy trong ngôn ngữ lập trình C#

Việc đầu tiên của mỗi bài toán đệ quy chính là việc xác định bài toán cơ sở và điểm dừng bên trong bài toán này, để xác định được chúng ta phải phân tích dữ liệu đầu bài để tìm ra các đặc điểm của việc tính giai thừa. Ta thấy :

Giai thừa của n! = n x (n-1) x (n-2)x … x1

Giai thừa của (n-1) = (n-1)x(n-2)x…x1

Giai thừa của 1! = 1

Giai thừa của 0! = 1

         Như vậy ta thấy rằng bản chất của n! chính là n! = n x (n-1)!

         Từ đó ta suy ra bài toán cơ sở, và điểm dừng của bài toán tính giai thừa này như sau

– Nếu n <=1 trả về 1, đây chính là điểm dừng của bài toán này

– Nếu n > 1 . GiaiThua(n) = n*GiaiThua(n-1)

       Từ đó ta triển khai bài toán trên ngôn ngữ lập trình C# trên một Project loại Console Application như sau :





Sau khi viết xong hàm chính, ta có thể test việc chạy hàm trong hàm main như sau:

     Chạy chương trình, và nhập đầu vào ta sẽ được kết quả :

Result of Recursion with C#

       Việc sử dụng đệ quy thông thường sẽ làm rất tốn tài nguyên, cũng như thời gian chạy vì phải khởi tạo hàm quá nhiều lần trong chương trình chạy của mình. Ví dụ như bài toán tính giai thừa ở phía trên, nêu tính 10! thì ta phải thực hiện lệnh gọi hàm GiaiThua 10 lần. Đây cũng là một trong những nhược điểm lớn của kỹ thuật đệ quy, và trong lập trình người ta sẽ thường cố gắng tìm cách để khử đệ quy trong việc xử lý bài toán của mình. Dưới đây là ví dụ khử đệ quy của bạn toán tính giai thừa ở trên như sau :

2.  Một số bài toán thường dùng áp dụng phương pháp, kỹ thuật đệ quy

+ Duyệt các thư mục bằng C# (Recursively searching directories in C#)

+ Duyệt các thư mục và file trong C# (Recursively searching directories, files in C#)

Các bạn có thể tải mã nguồn (Download Source) : Tại đây

      Trong quá trình viết bài có thể không tránh khỏi những sơ xuất hoặc có những gì cần góp ý các bạn vui lòng để comment bên dưới hoặc gửi tới email [email protected].




[Ngôn ngữ lập trình C#]


Related Post

Phản hồi

Phản hồi