खोज…


टिप्पणियों

ध्यान दें कि पुनरावृत्ति का उपयोग करने से आपके कोड पर गंभीर प्रभाव पड़ सकता है, क्योंकि प्रत्येक पुनरावर्ती फ़ंक्शन कॉल को स्टैक में जोड़ा जाएगा। यदि बहुत अधिक कॉल हैं तो इससे StackOverflow Exception हो सकता है। अधिकांश "प्राकृतिक पुनरावर्ती कार्य" एक for रूप में लिखे जा सकते हैं, while या foreach लूप का निर्माण किया जा सकता है, और यह देखते हुए कि पॉश या चतुर नहीं है और अधिक कुशल होगा।

हमेशा दो बार सोचें और ध्यान से पुनरावृत्ति का उपयोग करें - पता है कि आप इसका उपयोग क्यों करते हैं:

  • पुनरावर्तन का उपयोग तब किया जाना चाहिए जब आपको पता हो कि पुनरावर्ती कॉल की संख्या अत्यधिक नहीं है
    • अत्यधिक साधन, यह इस बात पर निर्भर करता है कि स्मृति कितनी उपलब्ध है
  • पुनरावृत्ति का उपयोग किया जाता है क्योंकि यह स्पष्ट और क्लीनर कोड संस्करण है, यह पुनरावृत्त या लूप-आधारित फ़ंक्शन की तुलना में अधिक पठनीय है। अक्सर यह मामला होता है क्योंकि यह क्लीनर और अधिक कॉम्पैक्ट कोड (कोड की उर्फ कम लाइनें) देता है।
    • लेकिन जागरूक रहें, यह कम कुशल हो सकता है! उदाहरण के लिए, फिबोनाची पुनरावृत्ति, क्रम में nth संख्या की गणना करने के लिए, गणना का समय तेजी से बढ़ेगा!

यदि आप अधिक सिद्धांत चाहते हैं, तो कृपया पढ़ें:

किसी ऑब्जेक्ट संरचना का पुनरावर्ती वर्णन करें

पुनरावृत्ति तब होती है जब कोई विधि स्वयं कॉल करती है। अधिमानतः ऐसा तब तक किया जाएगा जब तक कि एक विशिष्ट स्थिति पूरी नहीं हो जाती है और फिर यह उस विधि से सामान्य रूप से बाहर निकल जाएगा, जिस बिंदु से विधि को बुलाया गया था। यदि नहीं, तो बहुत अधिक पुनरावर्ती कॉल के कारण स्टैक ओवरफ़्लो अपवाद हो सकता है।

/// <summary>
/// Create an object structure the code can recursively describe
/// </summary>
public class Root
{
    public string Name { get; set; }
    public ChildOne Child { get; set; }
}
public class ChildOne
{
    public string ChildOneName { get; set; }
    public ChildTwo Child { get; set; }
}
public class ChildTwo
{
    public string ChildTwoName { get; set; }
}
/// <summary>
/// The console application with the recursive function DescribeTypeOfObject
/// </summary>
public class Program
{
    static void Main(string[] args)
    {
        // point A, we call the function with type 'Root'
        DescribeTypeOfObject(typeof(Root));
        Console.WriteLine("Press a key to exit");
        Console.ReadKey();
    }

    static void DescribeTypeOfObject(Type type)
    {
        // get all properties of this type
        Console.WriteLine($"Describing type {type.Name}");
        PropertyInfo[] propertyInfos = type.GetProperties();
        foreach (PropertyInfo pi in propertyInfos)
        {
            Console.WriteLine($"Has property {pi.Name} of type {pi.PropertyType.Name}");
            // is a custom class type? describe it too
            if (pi.PropertyType.IsClass && !pi.PropertyType.FullName.StartsWith("System."))
            {
                // point B, we call the function type this property
                DescribeTypeOfObject(pi.PropertyType);
            }
        }
        // done with all properties
        // we return to the point where we were called
        // point A for the first call
        // point B for all properties of type custom class
    }
}

सादे अंग्रेजी में पुनरावृत्ति

पुनरावर्तन को इस प्रकार परिभाषित किया जा सकता है:

एक विधि जो विशिष्ट स्थिति पूरी होने तक खुद को कॉल करती है।

पुनरावृत्ति का एक उत्कृष्ट और सरल उदाहरण एक ऐसी विधि है जो किसी दिए गए नंबर का भाज्य प्राप्त करेगी:

public int Factorial(int number)
{
    return number == 0 ? 1 : n * Factorial(number - 1);
}

इस पद्धति में, हम देख सकते हैं कि विधि एक तर्क, number लेगी।

क्रमशः:

उदाहरण को देखते हुए, Factorial(4) को निष्पादित करना Factorial(4)

  1. number (4) == 1 ?
  2. नहीं? वापसी 4 * Factorial(number-1) (3)
  3. क्योंकि विधि को एक बार फिर से कहा जाता है, यह अब नए तर्क के रूप में Factorial(3) का उपयोग करते हुए पहला कदम दोहराता है।
  4. यह तब तक जारी रहता है जब तक कि Factorial(1) निष्पादित नहीं हो जाता है और number (1) == 1 रिटर्न 1 हो जाता है।
  5. कुल मिलाकर, गणना " 4 * 3 * 2 * 1 " 4 * 3 * 2 * 1 बनाता है और अंत में 24 रिटर्न करता है।

पुनरावृत्ति को समझने की कुंजी यह है कि विधि स्वयं का एक नया उदाहरण कहती है। लौटने के बाद, कॉलिंग इंस्टेंस का निष्पादन जारी रहता है।

निर्देशिका ट्री प्राप्त करने के लिए पुनरावर्तन का उपयोग करना

पुनरावृत्ति के उपयोगों में से एक एक फ़ाइल सिस्टम डायरेक्टरी ट्री की तरह एक पदानुक्रमित डेटा संरचना के माध्यम से नेविगेट करना है, यह जानने के बिना कि प्रत्येक स्तर पर पेड़ कितने स्तरों या वस्तुओं की संख्या है। इस उदाहरण में, आप देखेंगे कि किसी निर्दिष्ट निर्देशिका की सभी उप-निर्देशिकाओं को खोजने के लिए किसी निर्देशिका ट्री पर पुनरावर्तन का उपयोग कैसे करें और पूरे ट्री को कंसोल पर प्रिंट करें।

internal class Program
{
    internal const int RootLevel = 0;
    internal const char Tab = '\t';

    internal static void Main()
    {
        Console.WriteLine("Enter the path of the root directory:");
        var rootDirectorypath = Console.ReadLine();

        Console.WriteLine(
            $"Getting directory tree of '{rootDirectorypath}'");

        PrintDirectoryTree(rootDirectorypath);
        Console.WriteLine("Press 'Enter' to quit...");
        Console.ReadLine();
    }

    internal static void PrintDirectoryTree(string rootDirectoryPath)
    {
        try
        {
            if (!Directory.Exists(rootDirectoryPath))
            {
                throw new DirectoryNotFoundException(
                    $"Directory '{rootDirectoryPath}' not found.");
            }

            var rootDirectory = new DirectoryInfo(rootDirectoryPath);
            PrintDirectoryTree(rootDirectory, RootLevel);
        }
        catch (DirectoryNotFoundException e)
        {
            Console.WriteLine(e.Message);
        }
    }

    private static void PrintDirectoryTree(
        DirectoryInfo directory, int currentLevel)
    {
        var indentation = string.Empty;
        for (var i = RootLevel; i < currentLevel; i++)
        {
            indentation += Tab;
        }

        Console.WriteLine($"{indentation}-{directory.Name}");
        var nextLevel = currentLevel + 1;
        try
        {
            foreach (var subDirectory in directory.GetDirectories())
            {
                PrintDirectoryTree(subDirectory, nextLevel);
            }
        }
        catch (UnauthorizedAccessException e)
        {
            Console.WriteLine($"{indentation}-{e.Message}");
        }
    }
}

यह कोड इस कार्य को पूरा करने के लिए नंगे न्यूनतम की तुलना में कुछ अधिक जटिल है, क्योंकि इसमें निर्देशिकाओं के साथ किसी भी मुद्दे को संभालने के लिए अपवाद जाँच शामिल है। नीचे आपको प्रत्येक के स्पष्टीकरण के साथ छोटे खंडों में कोड का ब्रेक-डाउन मिलेगा।

Main :

मुख्य विधि एक उपयोगकर्ता से एक स्ट्रिंग के रूप में एक इनपुट लेती है, जिसे रूट निर्देशिका के पथ के रूप में उपयोग किया जाना है। यह तब पैरामीटर के रूप में इस स्ट्रिंग के साथ PrintDirectoryTree विधि को कॉल करता है।

PrintDirectoryTree(string) :

यह दो तरीकों में से पहला है जो वास्तविक निर्देशिका ट्री प्रिंटिंग को संभालता है। यह विधि एक पैरामीटर के रूप में रूट डायरेक्टरी के लिए मार्ग का प्रतिनिधित्व करने वाली स्ट्रिंग लेती है। यह जाँचता है कि क्या पथ एक वास्तविक निर्देशिका है, और यदि नहीं, तो एक DirectoryNotFoundException फेंकता है जिसे तब पकड़ ब्लॉक में संभाला जाता है। पथ कोई वास्तविक निर्देशिका है, तो एक DirectoryInfo वस्तु rootDirectory पथ से बनाई गई है, और दूसरा PrintDirectoryTree विधि के साथ कहा जाता है rootDirectory वस्तु और RootLevel , जो शून्य का एक मूल्य के साथ एक पूर्णांक स्थिरांक है।

PrintDirectoryTree(DirectoryInfo, int) :

यह दूसरी विधि काम का खामियाजा उठाती है। यह एक DirectoryInfo और मापदंडों के रूप में एक पूर्णांक लेता है। DirectoryInfo वर्तमान निर्देशिका है, और पूर्णांक रूट के सापेक्ष निर्देशिका की गहराई है। पढ़ने में आसानी के लिए, आउटपुट प्रत्येक स्तर के लिए प्रेरित होता है जो वर्तमान निर्देशिका को गहरा करता है, ताकि आउटपुट इस तरह दिखे:

-Root
    -Child 1
    -Child 2
        -Grandchild 2.1
    -Child 3

एक बार वर्तमान निर्देशिका मुद्रित होने के बाद, इसकी उप-निर्देशिकाओं को पुनर्प्राप्त किया जाता है, और फिर इस पद्धति को उनमें से प्रत्येक पर वर्तमान से एक से अधिक गहराई के स्तर के साथ बुलाया जाता है। वह हिस्सा पुनरावृत्ति है: स्वयं को कॉल करने की विधि। यह कार्यक्रम इस तरह से चलेगा जब तक कि यह पेड़ की हर निर्देशिका का दौरा न कर ले। जब यह बिना उप निर्देशिकाओं के किसी निर्देशिका में पहुंच जाता है, तो विधि अपने आप वापस आ जाएगी।

यह विधि एक UnauthorizedAccessException भी पकड़ती है, जिसे वर्तमान निर्देशिका के किसी भी उप निर्देशिका द्वारा सिस्टम द्वारा संरक्षित किए जाने पर फेंक दिया जाता है। त्रुटि संदेश निरंतरता के लिए वर्तमान इंडेंटेशन स्तर पर मुद्रित किया जाता है।

नीचे दी गई विधि इस समस्या के लिए अधिक बुनियादी दृष्टिकोण प्रदान करती है:

internal static void PrintDirectoryTree(string directoryName)
{
    try
    {
        if (!Directory.Exists(directoryName)) return;
        Console.WriteLine(directoryName);
        foreach (var d in Directory.GetDirectories(directoryName))
        {
            PrintDirectoryTree(d);
        }
    }
    catch (Exception e)
    {
        Console.WriteLine(e.Message);
    }
}

इसमें पहले दृष्टिकोण की विशिष्ट त्रुटि जाँच या आउटपुट स्वरूपण शामिल नहीं है, लेकिन यह प्रभावी रूप से एक ही काम करता है। चूंकि यह केवल DirectoryInfo विपरीत स्ट्रिंग्स का उपयोग करता है, इसलिए यह अनुमति जैसे अन्य निर्देशिका गुणों तक पहुंच प्रदान नहीं कर सकता है।

फिबोनाची अनुक्रम

आप पुनरावर्तन का उपयोग करके फिबोनाची अनुक्रम में एक संख्या की गणना कर सकते हैं।

गणित सिद्धांत के बाद एफ (एन) = एफ (एन -2) + एफ (एन -1), किसी भी i> 0 के लिए,

// Returns the i'th Fibonacci number
public int fib(int i) {
    if(i <= 2) {
        // Base case of the recursive function.
        // i is either 1 or 2, whose associated Fibonacci sequence numbers are 1 and 1.
        return 1;
    }
    // Recursive case. Return the sum of the two previous Fibonacci numbers.
    // This works because the definition of the Fibonacci sequence specifies
    // that the sum of two adjacent elements equals the next element.
    return  fib(i - 2) + fib(i - 1);
    
}

fib(10); // Returns 55

तथ्य की गणना

किसी संख्या का भाज्य (उदाहरण के लिए! 9, उदाहरण के लिए!) उस संख्या का गुणन एक निम्न का गुणन है। तो, उदाहरण के लिए, 9! = ९ x x! = ९ x 8 x 7! = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1।

तो कोड में जो पुनरावृत्ति का उपयोग कर बन जाता है:

long Factorial(long x)
{
    if (x < 1)
    {
        throw new OutOfRangeException("Factorial can only be used with positive numbers.");
    }

    if (x == 1)
    {
        return 1;
    } else {
        return x * Factorial(x - 1);
    }
}

पॉवरऑफ गणना

किसी दिए गए नंबर की शक्ति की गणना पुनरावर्ती रूप से भी की जा सकती है। एक आधार संख्या को देखते हुए n और प्रतिपादक e , हम प्रतिपादक कम करके मात्रा में समस्या विभाजित करने के लिए सुनिश्चित करने की आवश्यकता e

सैद्धांतिक उदाहरण:

  • 2 = 2x2
  • 2 = 2x2x2 या, 2³ = 2 2 x 2
    इसमें हमारे पुनरावर्ती एल्गोरिथ्म का रहस्य निहित है (नीचे कोड देखें)। यह समस्या को लेने और इसे छोटे और सरल में विखंडू को हल करने के लिए अलग करने के बारे में है।
  • टिप्पणियाँ
    • जब आधार संख्या 0 होती है, तो हमें 0 को 0 0 = 0 x 0 x 0 के रूप में वापस करने के लिए जागरूक होना होगा
    • जब प्रतिपादक 0 होता है, तो हमें हमेशा 1 लौटाने के लिए जागरूक होना होगा, क्योंकि यह एक गणितीय नियम है।

कोड उदाहरण:

public int CalcPowerOf(int b, int e) {
    if (b == 0) { return 0; } // when base is 0, it doesn't matter, it will always return 0
    if (e == 0) { return 1; } // math rule, exponent 0 always returns 1
    return b * CalcPowerOf(b, e - 1); // actual recursive logic, where we split the problem, aka: 2³ = 2 * 2² etc..
}

XUnit में तर्क को सत्यापित करने के लिए टेस्ट:
हालांकि यह आवश्यक नहीं है, अपने तर्क को सत्यापित करने के लिए परीक्षण लिखना हमेशा अच्छा होता है। मैं यहां उन लोगों को शामिल करता हूं जो xUnit ढांचे में लिखे गए हैं।

    [Theory]
    [MemberData(nameof(PowerOfTestData))]
    public void PowerOfTest(int @base, int exponent, int expected) {
        Assert.Equal(expected, CalcPowerOf(@base, exponent));
    }

    public static IEnumerable<object[]> PowerOfTestData() {
        yield return new object[] { 0, 0, 0 };
        yield return new object[] { 0, 1, 0 };
        yield return new object[] { 2, 0, 1 };
        yield return new object[] { 2, 1, 2 };
        yield return new object[] { 2, 2, 4 };
        yield return new object[] { 5, 2, 25 };
        yield return new object[] { 5, 3, 125 };
        yield return new object[] { 5, 4, 625 };
}


Modified text is an extract of the original Stack Overflow Documentation
के तहत लाइसेंस प्राप्त है CC BY-SA 3.0
से संबद्ध नहीं है Stack Overflow