DILI #5

RECURSION

Have you ever gone into a mirror maze and got absolutely flabbergasted by an infinte amount of you getting smaller and smaller. That's my friend is Recursion ... or at least how I visualize it after some productive time in a cafe with a friend.

Similar to what you see in the mirror maze, smaller yous that keep going as far as the eyes can see, in coding in general, Recursion or recursive functions divide a big problem to smaller sub-problems that can be easily sovled. For example, problems like Tower of Hanoi or more mathematical like calculating Factorials or The Fibbonacci sequence.

But how is it different from Iterations like for loops or while loops? Well in a sense, I feel like whatever can be done via Recursion can be using Iterations and vice versa (I'm not copying geeksorgeeks.com, I have paraphrased it). It just that you have to evaluate which method is better given certain scenarios. For example, Recursion make your code looks simpler but simplicity is hard to achieve as it is quite a handful to wrap your head around. Problems like I mentioned above if dissect carefully with the use of Recursion, the problem becomes quite neat and can be hard to use Iterations. So, I would recommend using Iterations for small works like calculations and Recursion for more abstract works. Like calculating a factorial:

Using Iterations:

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int ans = 1;
    for (int i = 2; i <=n; i++){
        ans = ans * i;
    }
    cout << ans;
    return 0;
}

Or if you are a pro with using Recursion (like ... ahem ...me):

#include <iostream>

using namespace std;

int factorial (int n)
{
    if (n == 1) return 1;
    return n * factorial(n-1);
}

int main()
{
    int n;
    cin >> n;
    cout << factorial(n);
    return 0;
}

And for the Finale, as I'm a Vietnamese, it would be a shame not to try to code Tower of Hanoi:

#include <iostream>

using namespace std;

void towerOfHanoi(int n, int& cnt, char a, char b, char c)
{
    if (n == 1) {
        cout << a << " --> " << c <<endl;
        cnt++;
    }
    else {
        towerOfHanoi (n-1,cnt,a,c,b);
        towerOfHanoi (1,cnt,a,b,c); 
        towerOfHanoi (n-1,cnt,b,a,c);
    }
}

int main()
{
    int n;
    cin >> n;
    char a = 'A';
    char b = 'B';
    char c = 'C';
    int cnt = 0;
    towerOfHanoi(n,cnt,a,b,c);
    cout << "It is done in " << cnt << " steps";
    return 0;
}

You can try the code and have this on your side when your friends challenge you to play Tower of Hanoi. To briefly explain how the code works, I did the Tower of Hanoi backwards and changed the Start (char a), Middle (char b), and Goal (char c) for everytime the biggest piece at the time is move to the intial Goal. This is a picture that helped me and hopefully you as well.

As always, any advices on coding, blog-writing and recommendations on what to learn are all much appreciated by me. Hope y'all have a nice day!

REFERENCE:
GeeksforGeeks
Alex