Hàm đệ quy trong C#

Trang chủ C# cơ bản Hàm đệ quy trong C#

Hàm đệ quy trong C#

Nguyễn Dương 07-06-2024

Trong bài vòng lặp for, mình có nhắc đến một vòng lặp đặc biệt đó là đệ quy. Vậy đệ quy là gì, nó tạo ra vòng lặp bằng cách nào, chúng ta cùng tìm hiểu trong bài này nhé.

1. HÀM ĐỆ QUY LÀ GÌ?

Một hàm mà nó gọi lại chính nó thì gọi là hàm đệ quy.

HamDeQuy()
{    
      HamDeQuy();
}

Chúng ta cùng xét ví dụ sau:
Viết chương trình tính giai thừa của n, với n được nhập từ bàn phím.
Biết rằng:

- 0! = 1
- n! = 1 * 2 * 3 * 4 * 5 * ..........* n
- Không có giai thừa của số âm

Theo cách bình thường, chúng ta sẽ dùng vòng lặp for là dễ dàng tính nhất.

for (int i = 1; i <= n; i++)
{
     GiaiThua = GiaiThua * i;
}

Giờ bạn thử viết chương trình bằng cách dùng hàm đệ quy xem sao nhé

namespace ham_de_quy
{
    class Program
    {
        static int GiaiThua(int n)
        {
            if (n == 0)
            {
                return 1;
            }
            else
            {
                return n * GiaiThua(n - 1);
            }
        }
        static void Main(string[] args)
        {
            Console.OutputEncoding = Encoding.UTF8;

            int n;

            Console.WriteLine("Chương trình tính giai thừa");
            Console.WriteLine("***************************");
            Console.WriteLine();
            Console.Write("Mời nhập n: ");
            n = int.Parse(Console.ReadLine());

            if (n < 0)
            {
                Console.Write("Không có giai thừa của số âm");
            }
            else
            {
                Console.Write("{0} giai thừa bằng {1}", n, GiaiThua(n));
            }

            Console.ReadLine();
        }
    }
}

Giả sử n = 3
Vậy GiaiThua sẽ bằng n * GiaiThua(n - 1) = 3 * GiaiThua(2) = 3 * 2 * GiaiThua(1)
Cứ như vậy với bất kỳ số n nào lớn hơn 0, ta đều tính được bằng cách hàm gọi chính nó.

Vậy là trong chương trình trên, hàm GiaiThua đã gọi lại chính nó trong thân hàm của nó, nên nó được gọi là hàm đệ quy.

2. TẠO VÒNG LẶP ĐỆ QUY

Bản chất trong ví dụ trên là chúng ta đã tạo ra 1 vòng lặp cho hàm GiaiThua với n lần rồi đó. Vì hàm gọi lại chính nó nên khối lệnh trong hàm đã được lặp đi lặp lại.
Lưu ý: Nếu không có điều kiện nào để dừng đệ quy thì sẽ tạo thành vòng lặp vô hạn.

Ví dụ:

static void HamDeQuy()
{
      Console.WriteLine("Chào mừng đến với Quản trị máy tính");
      HamDeQuy();
}

Kết quả:

Vì vậy, nếu muốn giải quyết một bài toán bằng hàm đệ quy mà các bạn không tìm ra được điều kiện dừng thì tốt nhất các bạn đừng sử dụng hàm đệ quy nhé.

3. ĐỆ QUY TRỰC TIẾP VÀ GIÁN TIẾP

Đệ quy trực tiếp: Khi một hàm gọi lại chính nó thì được gọi là đệ quy trực tiếp. Trong ví dụ tính giai thừa ở đầu bài viết thì đó là đệ quy trực tiếp.
Đệ quy gián tiếp: Khi hàm A gọi hàm B và trong hàm B lại gọi lại hàm A thì đó gọi là đệ quy gián tiếp.
Ví dụ: Ta thử dùng đệ quy gián tiếp để tính giai thừa nhé.

static int GiaiThua(int n)
{
       if (n == 0)
       {
           return 1;
       }
       else
       {
           return n * GiaiThua2(n - 1);
       }
}

static int GiaiThua2(int m)
{
       return GiaiThua(m);
}

Kết quả vẫn tương tự cách làm theo đệ quy trực tiếp.

Lời kết:
Khi sử dụng hàm đệ quy thì chắc chắn rằng hàm đệ quy đó phải có ít nhất một điều kiện dừng nhé.
Bản thân mình không khuyến khích các bạn dùng đệ quy vì nếu bạn chưa thực sự thành thục về nó thì chỉ làm cho chương trình của bạn thêm rối rắm, phức tạp.

Donate Fanpage Group Youtube

Danh mục