🍿 CornPop

A Deep Dive into Recursion in CSharp

8 min read

إحنا اتكلمنا عن الـ Recursion قبل كده، وعرفنا إن أكتر حاجة محتاجين نفكر فيها هي إمتى نوقف الـ function عشان متدخلش في infinite loop.

الـ Recursion مش سحر، هو عبارة عن Stack (رصة فوق بعض). تخيلها زي “رصة أطباق”. كل ما تنادي Function، بتحط طبق جديد فوق الرصة. وعمرك ما هتعرف تشيل الطبق اللي تحت غير لما تخلص الطبق اللي فوق الأول.

الـ Recursion ببساطة هو إن الـ function بتنادي على نفسها بشكل متكرر لحد ما شرط معين يتحقق، وساعتها بتقف. الموضوع ده شبه الـ loop، طول ما الشرط متحقق، الـ loop بتكمل، وبنفس الطريقة، الـ function بتفضل تنادي على نفسها.

عشان نحل مشكلة باستخدام الـ Recursion، لازم شرطين يتحققوا:

  1. الـ Recursive Form: المشكلة لازم تكون مكتوبة بصيغة تسمح للـ function إنها تنادي على نفسها.
  2. الـ Stopping Condition: لازم يكون فيه شرط وقوف (بيسموه Base Case) عشان نضمن إن الـ function هتقف في وقت معين ومتكملش للأبد.

How does Recursion Work?

عشان نفهم الـ Recursion بيشتغل إزاي، لازم نفهم الأول إزاي الـ functions بتنادي على بعضها في البرمجة العادية (Synchronous programming).

لما function معينة (هنسميها F1) بتنادي على function تانية (هنسميها F2)، تنفيذ F1 بيقف مؤقتًا لحد ما F2 تخلص شغلها بالكامل وترجع. بعدها بس F1 بتقدر تكمل تنفيذ.

خلينا نشوف المثال ده عشان الصورة توضح:

using System;
namespace RecursionDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Main Method Started");
            fun1(4);
            Console.WriteLine("Main Method Ended"); // This will be the last line to execute
            Console.ReadKey();
        }
        static void fun1(int n)
        {
            Console.WriteLine("Fun1 Started");
            fun2(3);
            Console.WriteLine("Fun1 Ended");
        }
        static void fun2(int n)
        {
            Console.WriteLine("Fun2 Started");
            fun3(2);
            Console.WriteLine("Fun2 Ended");
        }
        static void fun3(int n)
        {
            Console.WriteLine("Fun3 Started");
            fun4(1);
            Console.WriteLine("Fun3 Ended");
        }
        static void fun4(int n)
        {
            Console.WriteLine("Fun4 Started");
            Console.WriteLine("Fun4 Ended");
        }
    }
}

الـ Output بتاع الكود ده هيكون كالآتي:

Main Method Started
Fun1 Started
Fun2 Started
Fun3 Started
Fun4 Started
Fun4 Ended
Fun3 Ended
Fun2 Ended
Fun1 Ended
Main Method Ended

زي ما إنت شايف، الـ functions بتتنفذ بالترتيب (Main → fun1 → fun2 → fun3 → fun4)، لكن بتنتهي بالعكس. الـ fun4 بتخلص الأول، وبعدها fun3، وهكذا لحد ما الـ Main تخلص في الآخر خالص.

النقطة المهمة هنا هي إن الـ function اللي بتنادي (caller) مش بتخلص إلا لما الـ function اللي تم استدعاؤها (called) تخلص تنفيذها الأول.

Tracing a Recursive Function

دلوقتي خلينا نشوف مثال على Recursive Function ونتبع خطوات تنفيذها. الـ function دي بتطبع أرقام بترتيب تنازلي.

using System;
namespace RecursionDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            int x = 3;
            fun1(x);
            Console.ReadKey();
        }
        static void fun1(int n)
        {
            // Base case: Stop when n is not greater than 0
            if (n > 0)
            {
                Console.Write($"{n} "); // Execute action first
                fun1(n - 1);           // Then make the recursive call
            }
        }
    }
}

تتبع تنفيذ الكود ده بيكون زي شجرة (بيسموها Tracing Tree):

  1. fun1(3):

    • الشرط 3 > 0 صحيح.
    • هيطبع 3.
    • هينادي على fun1(2). (الـ function دي لسه مخلصتش).

  2. fun1(2):

    • الشرط 2 > 0 صحيح.
    • هيطبع 2.
    • هينادي على fun1(1). (الـ function دي كمان لسه مخلصتش).

  3. fun1(1):

    • الشرط 1 > 0 صحيح.
    • هيطبع 1.
    • هينادي على fun1(0).

  4. fun1(0):

    • الشرط 0 > 0 غلط.
    • الـ function مش هتعمل أي حاجة وهتنتهي.

لما fun1(0) بتخلص، التحكم بيرجع للي قبلها (fun1(1)). ولأن fun1(1) كانت خلصت شغلها قبل ما تنادي على fun1(0)، هي كمان بتنتهي. وهكذا، بترجع لـ fun1(2) وبعدها fun1(3) لحد ما نرجع للـ Main method.

الـ Output النهائي هيكون: 3 2 1.

Calling Phase vs. Returning Phase

الـ Recursion ليه مرحلتين أساسيتين:

  • الـ Calling Phase: مرحلة الاستدعاء، وفيها الـ function بتفضل تنادي على نفسها.
  • الـ Returning Phase: مرحلة الرجوع، ودي بتبدأ لما نوصل للـ base case، وساعتها التنفيذ بيبدأ يرجع للخلف.

لو عكسنا ترتيب الأوامر في المثال اللي فات، وخلينا الطباعة تحصل بعد الاستدعاء، هنشوف إزاي مرحلة الرجوع بتشتغل.

static void fun2(int n)
{
    // Base case: Stop when n is not greater than 0
    if (n > 0)
    {
        fun2(n - 1);            // Make the recursive call first
        Console.Write($"{n} "); // Then execute action on return
    }
}

لو نادينا على fun2(3)، التتبع هيكون كالآتي:

  1. الـ fun2(3) بتنادي على fun2(2).
  2. الـ fun2(2) بتنادي على fun2(1).
  3. الـ fun2(1) بتنادي على fun2(0).
  4. الـ fun2(0) بتوصل للـ base case وتنتهي من غير ما تعمل حاجة.
  5. التحكم بيرجع لـ fun2(1)، اللي بتكمل شغلها وتطبع 1.
  6. التحكم بيرجع لـ fun2(2)، اللي بتكمل شغلها وتطبع 2.
  7. التحكم بيرجع لـ fun2(3)، اللي بتكمل شغلها وتطبع 3.

الـ Output هنا هيكون: 1 2 3. الطباعة حصلت في مرحلة الرجوع (Returning Phase).

Factorial Example

مثال مشهور جدًا على الـ Recursion هو حساب الـ Factorial بتاع رقم.

static int CalculateFactorial(int number)
{
    // Base case: Factorial of 1 or 0 is 1
    if (number <= 1)
        return 1;
    
    // Recursive step: number * factorial of (number - 1)
    return number * CalculateFactorial(number - 1);
 
	// The iterative alternative (using a loop)
    // var factorial = 1;
    // for (var i = 1; i <= number; i++)
    //    factorial *= i;
    // return factorial;
}

هنا الـ Base Case هو لما الرقم يوصل لـ 1. والعملية الحسابية (number * ...) بتحصل في مرحلة الرجوع (Returning Phase).

Hierarchical data

أكبر فايدة للـ Recursion بتظهر لما نتعامل مع بيانات متداخلة أو شجرية (hierarchical data).

زي مثلاً لما يكون عندك فولدر جوه فولدر جوه فولدر لعدد مستويات إنت مش عارفه مسبقًا. الـ Recursion هنا بيخليك تتعامل مع كل مستوى وتدخل للي بعده بشكل ديناميكي من غير ما تكون محدد العمق.

Ex 1: Print Directory Contents

المثال ده بيوضح إزاي نطبع كل الملفات والفولدرات اللي جوه path معين وكل الفولدرات الفرعية بتاعته.

static void PrintDirectoryContents(string dirPath, int level)
{
    // Print all files in the current directory
    foreach (var filePath in Directory.GetFiles(dirPath))
    {
        string fileName = new FileInfo(filePath).Name;
        Console.WriteLine($"{new string('-', level)} {fileName}");
    }
 
    // Print all subdirectories in the current directory
    foreach (var subDir in Directory.GetDirectories(dirPath))
    {
        string dirName = new DirectoryInfo(subDir).Name;
        Console.WriteLine($"{new string('-', level)} {dirName}");
 
        // Recursive call to process the subdirectory
        PrintDirectoryContents(subDir, level + 1);
    }
}

الفائدة من Level إنها بتخليك تشوف المجلدات والملفات مترتبة وشكلها واضح زي الشجرة، فتعرف مين جوه مين ومين تبع مين بالظبط. من غير الـ level ده، كل حاجة هتطبع على سطر واحد وبنفس المسافة، ومش هتعرف مين أصل ومين فرع.

Ex 2: Calculate Directory Size

المثال ده بيحسب المساحة الإجمالية لفولدر معين، شاملة كل الملفات والفولدرات الفرعية اللي جواه.

static long CalculateDirectorySize(string dirPath)
{
    long size = 0;
 
    // Add the size of all files in the current directory
    foreach (var filePath in Directory.GetFiles(dirPath))
    {
        size += new FileInfo(filePath).Length;
    }
 
    // Recursively add the size of all subdirectories
    foreach (var subDir in Directory.GetDirectories(dirPath))
    {
        size += CalculateDirectorySize(subDir);
    }
 
    return size;
}

How Variables Work in Recursion

نقطة مهمة جدًا لازم نفهمها هي إن مع كل استدعاء لـ recursive function، بيتم إنشاء نسخة جديدة من كل الـ local variables بتاعتها. النسخ دي بتتحفظ في الـ Stack memory.

خلينا نشوف المثال ده عشان نفهم إزاي المتغيرات بتشتغل:

static int fun(int n)
{
    if(n > 0)
    {
        // '+' operation happens during the returning phase
        return fun(n - 1) + n;
    }
    return 0; // Base case
}
 
// In Main method:
// int result = fun(5);
// Console.WriteLine(result); // Output: 15

اللي بيحصل هنا هو تجميع للأرقام من 1 لـ 5. عملية الجمع (+ n) بتحصل في مرحلة الرجوع.

ده رسم توضيحي بيشرح اللي بيحصل في الـ Stack:

graph TD
    A["fun(5)"] --> B["fun(4)"];
    B --> C["fun(3)"];
    C --> D["fun(2)"];
    D --> E["fun(1)"];
    E --> F["fun(0)"];
    
    F -- "returns 0" --> E;
    E -- "returns 0 + 1 = 1" --> D;
    D -- "returns 1 + 2 = 3" --> C;
    C -- "returns 3 + 3 = 6" --> B;
    B -- "returns 6 + 4 = 10" --> A;
    A -- "returns 10 + 5 = 15" --> Result;

كل استدعاء (fun(5), fun(4), …) بيخلق activation record جديد في الـ stack مع نسخة خاصة بيه من المتغير n. عشان كده الـ Recursion بيستهلك ذاكرة أكتر من الـ loop العادية اللي بتستخدم متغير واحد بس.

Time Complexity of Recursive Functions

عشان نحسب الـ Time Complexity، بنفترض إن كل سطر كود بياخد وحدة زمنية واحدة (one unit of time).

لو بصينا على المثال بتاع fun1(n) اللي كان بيطبع الأرقام، هنلاقي إن جملة الطباعة Console.Write() بتتنفذ n مرة. يعني لو n=3، هتتنفذ 3 مرات. لو n=5، هتتنفذ 5 مرات.

ده معناه إن الوقت اللي الـ function بتاخده بيعتمد بشكل مباشر على قيمة n. عشان كده بنقول إن الـ Time Complexity بتاعتها هي O(n).

Advantages and Disadvantages

Advantages

  • بيساعد في التعامل مع المعلومات المتعلقة باستدعاءات الـ functions بشكل منظم.
  • بيُستخدم في تقييم الـ Stack والتعامل مع تعبيرات زي prefix, postfix, و infix.
  • بيخلي الكود أبسط وأوضح في الحالات المعقدة زي الـ hierarchical data.

Disadvantages

  • ممكن يكون بطيء بسبب كتر العمليات على الـ Stack.
  • ممكن يسبب Stack Overflow لو عمق الـ Recursion كبير جدًا والـ base case متأخر.
  • ممكن يدخل في infinite loop لو الـ base case مش مكتوب صح.

Graph View

Backlinks