Wednesday 28 August 2013

Art of Recursion


Introduction & Description: Coming shorty..

For a deeper understanding on all that has been mentioned above, please check out the 7 video links where I go through the demo in full detail.


C# Experiments: Art of Recursion (Part 1)



C# Experiments: Art of Recursion (Part 2)



C# Experiments: Art of Recursion (Part 3)



C# Experiments: Art of Recursion (Part 4)



C# Experiments: Art of Recursion (Part 5)



C# Experiments: Art of Recursion (Part 6)



C# Experiments: Art of Recursion (Part 7)




The code typed-in during the tutorial-session is as follows:-


    private void button1_Click(object sender, EventArgs e)
    {
        //Simple Recursion:-
        //MessageBox.Show(Fact(5).ToString());

        //Reusing a function's stack frame is called Tail Recursion.
        //Tail recurive functions are iterative processes (equivalent to loops).
        //Certain compilers can convert normal recursion to tail recursion.

        //OutOfMemory Exception & StackOverflowException are different.

        //AlternateSign: 6 => 6 - 5 + 4 - 3 + 2 - 1 = 3
        //AlternateSign: 7 => -7 + 6 - 5 + 4 - 3 + 2 - 1 = -4

        //Non-Tail Recursion:-
        MessageBox.Show(AlternateSign(150).ToString());

        //Tail Recursion:-
        //TailedAlternateSign(150);
        TailedAlternateSign(25000);
        MessageBox.Show(altAccum.ToString());

        //Get all the combinations of any given word.
        var word = "hello"; // 5! / 2! = 60 combinations

        var wordBreakUp = new Dictionary<int, char>();

        for (int i = 0; i < word.Length; i++)
            wordBreakUp.Add(i, word[i]);

        GetAllCombos(wordBreakUp.Count, wordBreakUp, new Dictionary<int, char>());
        MessageBox.Show("Done");


    }

    public int Fact(int num)
    {
        if (num == 0)
            return 1;
        else
            return num * Fact(num - 1);
    }

    public int AlternateSign(int num)
    {
        if (num == 0)
            return 0;

        else if (num % 2 == 0)
            return AlternateSign(num - 1) + num;
        else
            return AlternateSign(num - 1) - num;

    }

    int altAccum = 0;
    bool firstTime = true;

    public void TailedAlternateSign(int num)
    {
        if (num == 0)
            return;

        else if (num % 2 == 0)
            altAccum += num;
        else
            altAccum -= num;

        if (!firstTime)
            return;
        else
            firstTime = false;

        while (num != 0)
            TailedAlternateSign(--num);

    }

    private HashSet<string> allCombos = new HashSet<string>();
    StringBuilder wordBuilder = new StringBuilder();

    //To do a Tailed recursion without having an explicit 'return;' statement, ensure that the function reached the end of the function without recursing itself.
    private void GetAllCombos(int lettersLeft, Dictionary<int, char> wordBreakUp, Dictionary<int, char> word)
    {
        if (lettersLeft == 0)
        {
            foreach (var value in word.Values)
                wordBuilder.Append(value);

            allCombos.Add(wordBuilder.ToString());
            wordBuilder.Clear();

        }
        else
        {
            foreach (var pair in wordBreakUp)
            {
                if (!word.ContainsKey(pair.Key))
                {
                    word.Add(pair.Key, pair.Value);
                    GetAllCombos(lettersLeft - 1, wordBreakUp, word);
                    word.Remove(pair.Key);
                }
            }
        }
    }


Thank you for reading this post and watching the videos. Please Subscribe, Comment, and Rate the channel of you liked the videos.

Goto C# Experiments to access more of such content! Thanks again!

No comments:

Post a Comment