Did you mean: Recursion

Why this is one of the most exciting topics in Computer Science

Did you mean: Recursion

I love recursion , but do you know why? here the answer. If you don't understand the reason, just search on Google recursion and be careful how do you write it (see the suggested text) 😍

Since last week, I have been solving problems in Leetcode platform and then I found 3 problems related to recursion/trees/backtracking which, for me, are the best! My favorite data structure: Trees (I love trees, the natural and the created using pointers – and using arrays too). Since I learned that topic at the University, I have been fascinated by how recursion works.

Mostly, the first class about recursion at school/university explain something like the base case and the recursive case. Moreover, functions to explain that include Factorial, Fibonacci, or any other mathematical approach like sum two numbers (code below, in C#)

using System;

class Program {
    static int add(int iA, int iB)
    {
        if(iA == 0)
            return iB;
        return add(iB, iA-1) + 1;
    }
    static void Main(string[] args) {
        Console.WriteLine(add(0, 4));
        Console.WriteLine(add(4, 0));
        Console.WriteLine(add(0, 0));
        Console.WriteLine(add(432, 234));
        Console.WriteLine(add(-20, -10));  // error with this
    }
}

To sum 2 numbers using recursion? Really? I am not saying that is a bad way to introduce a topic, is about the functionality of it. We are clear that when we talked about recursion there is not over the table the work efficiency (disclaimer: of course, that recursion can reduce time complexity). However, come to my head some words like clarity or more commonly know in algorithmic terms as elegant, or even mathematical way.

For instance, there are several ways to write a code that converts a decimal number to binary. Also, there are several language integrated functions that already did that (e.g. using the print function, string formatting options, etc.), but I think that could be a good way inside the Computer Science field to understand that 🤯

void toBinary(int iN){
    if (iN >= 2){
        toBinary(iN/2);
        cout << iN%2;
    }
    else
        cout << iN;
}
// just invoke as toBinary(<your number here>)

The HTML tag-structure is another example of how recursion could be used as the 101 example to try to understand. The idea of how to work the recursion comes from how you think, a way in how to embrace a possible solution for a problem. Is there good news here? Sure! Once, you see clearly how this helps you to attack a problem, then at that point you will love it! ❤️ If you are a visual learner, the states generated the initial invocation to a recursion function is your thing, just try it.

A fractal image

Here comes in another interesting point: recursive data structures. There are native recursive data structures that also could be viewed as directed graphs. My favorite as I mentioned before: trees (from the basic right-left tree, heaps, space-partitioning to other more complex as SPQR tree). Then, the application of recursive algorithms to this kind of data structure is the way, not the only one, but is the easier to understand and also to code.

Do you want to see something fun? check Myopia. To conclude, of course, the classical and repetitive phrase to understand recursion: practice 🤓

From a geek to geeks


Share Tweet Send
0 Comments
Loading...
You've successfully subscribed to The ecode.DEV repository
Great! Next, complete checkout for full access to The ecode.DEV repository
Welcome back! You've successfully signed in
Success! Your account is fully activated, you now have access to all content.