Recursion: Why I keep Calling Myself

Hello Fellows, I am Domino. First of all, sorry for not being able to upload any article or share anything. Someone from our team (Mr. Guy), blows up our system.

For God's Sake, Mr. Guy… that wire doesn’t start your coffee machine. Please let me upload my article, don't mess with the internet…

Sorry Guys, Let's start today's confusing topic, “Recursion.” Recursion, in simpler words, can easily be understood by using this meme:

Yes, Just like the above image, recursion in simple terms is “Function calling itself”. I know you have heard this statement a lot but in today's article, we are going to explore its meaning, how to use it, time complexity finding, and types of recursion.

What is Recursion:

Mr. Guy, Recursion doesn't mean you keep repeating your name? Please be patience and listen me properly.

Recursion is the process in which the function calls itself directly or indirectly until it reaches its base condition.

Conditions for Recursion:

1. A recursive algorithm must have a base condition.
2. A recursive algorithm must change its state and move toward the base case.

Base Condition?

Base condition is the condition where the function came to know when to quit that loop.

When & Where To Use Recursion:

You have been in a situation where you call your function from the loop again and again until the loop ends. You can understand recursion as a function in a loop that keeps repeating itself until in a condition where the loop terminates.
Let's see it by an example in both function in a loop and recursion:

function mul(sum,n){
return sum*n
}
let sum = 1
for(i=1;i<=num;i++) {
 sum = mul(sum,n);
}

OR

function factorialRecursion(n) {
 if (n == 1) { 
 return 1; 
} 
return n * factorialRecursion(n — 1); 
}

Examples Of Recursion:

Recursion is made for solving problems that can be broken down into smaller, repetitive problems.
Using recursion, we can easily solve many complex problems very easily. Problems like
- Tower of Hanoi,
- Tree traversal,
- Factorial Number and many more.

Example-

You heard Mr. Guy, There should be a base condition… Find your base condition… and stop repeating your name.

Time Complexity:

The time complexity of recursion depends on two factors:
1) Total number of recursive calls and
2) Time complexity of additional operations for each recursive call

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

This function is being called recursively n times before reaching the base case so its O(n), often called linear.

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

This function is called n-5 for each time, so we deduct five from n before calling the function, but n-5 is also O(n). (Actually called order of n/5 times. And, O(n/5) = O(n) ).

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

This function is log(n) base 5, for every time we divide by 5 before calling the function so it O(log(n))(base 5), often called logarithmically and most often Big O notation and complexity analysis uses base 2.

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

Here, it’s O(2^n), or exponential, since each function call calls itself twice unless it has been recursed n times.

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

And here the for loop takes n/2 since we’re increasing by 2, and the recursion takes n/5 and since the for loop is called recursively, therefore, the time complexity is in

(n/5) * (n/2) = n²/10,

due to Asymptotic behavior and worst-case scenario considerations or the upper bound that big O is striving for, we are only interested in the largest term so O(n^2).

Special Thanks to Stackoverflow's answer for the above details.

Types of Recursion

Generally, there are four types of recursion, and are -

1. Direct Recursion

2. Indirect Recursion

3. Tail Recursion

4.Non-Tail Recursion / Head Recursion

1) Direct Recursion:-

A function is said to be a recursive function if it calls the same function.

2) Indirect Recursion:-

A function (let fun1) is said to be indirect recursive if it calls another function(fun2) and then fun2 calls fun1 directly or indirectly.

3) Tail Recursion:-

A function is said to be tail recursive if the recursive call is the last thing done by the function.

4) Non-Tail Recursion:-

A function is said to be Head Recursion if the recursive call is not the last thing done by the function. It means some statements are left out, that need to be executed.

Summary:

Okay We are done… now you can stop annoying me Mr. Guy. Let’s stable Panda HQ’s Internet.

ABOUT US

The Code Panda is a programming practice platform for every programmer out there. Upgrade your skills with catching coding problems and MCQs-based assignments to enhance your coding skill.

Follow us on medium to get a complete journey topic by topic or follow on Facebook, Quora, or LinkedIn or connect with the community on Facebook. Read our other blogs.

Read 25 Algorithm You Must Know: A Rubics Edition
Read: Do you want to feel Data Structures?: A Kinda Roadmap
Read: Searching & Sorting
Read: Let’s Draw a Roadmap for Competitive Coding
Read Time & Space Game: Let’s Find Complexity of My Code

If you are a beginner, you can start your coding journey with us our code lab.

Thank you for reading this article this far. Please share your viewpoints in the comments and topics on which you want an article.
Thank you. See you soon!