How to Think Recursively?

How to Think Recursively?

Recursion is a widely used technique in which a function calls itself again and again. It is used in almost every part of Data Structures and Algorithms. From programs like factorial to sorting techniques(Merge Sort, Quick Sort) to tree traversals. In this blog, I am going to explain recursion in few points that will clear for you how to think while using recursion on a problem.

What is Recursion?:

A function which calls itself again and again until terminated. While calling itself again and again, it creates a copy of a smaller problem of itself to work on it. Such functions are known as recursive functions.

2 Cases:

Recursion there are 2 types of cases to determine whether the function has to call itself again or terminate itself.

  1. Base Case - The role of a base case is to determine at what stage the program is going to terminate. It can be one or more in number, depending on the problem.
  2. Recursive Case - The role of a recursive case is to call the function again into a smaller problem of itself.

Format of how recursion works:

//base case(s)
if(base case 1){
    return (value for base case 1);
}

else if (base case 2){
    return (value for base case 2);
}

//recursive case
else{
    //make the problem smaller
    return (recursive call);
}

Note: Design the solution in such a way that the recursive case eventually converges to base case.

  • How to think for a Base case?: So, base case is going to terminate your call or we can also say, it will be the last case to be checked. So, the base case will be the least/smallest valid value for the program.

Let us take an example: Finding the factorial of a number.

Factorial is only for positive numbers and factorial of 0 and 1 is 1.

So our base case will go like:

int factorial(int n){
    //base cases
    if(n == 0 || n == 1){
        return 1;
    }
}

And as our recursive case should converge towards the base case, we will be doing n-1 at every call. After adding the recursive call the above program will be:

int factorial(int n){
    //base cases
    if(n == 0 || n == 1){
        return 1;
    }
    //recursive case
    else{
        return n * factorial(n-1);
    }
}

There are many more examples where recursion is used like Fibonacci series, tower of hanoi and many more.

Recursion && Memory:

As we are making a copy of variables/methods every time the function is calling itself again and again, it takes up space in the memory. For example: If the above program is running for n = 5.

/******************************************************************************

factorial(5) => 5*4*3*2*1 = 120
    ->factorial(4) => 4*3*2*1
        ->factorial(3) => 3*2*1
            ->factorial(2) => 2*1
                ->factorial(1) => returns 1

*******************************************************************************/

Once base case is reached it returns data (in above case it returns 1) or function gets terminated, memory gets freed with each return.

Points to remember

  1. Recursion is a process of function calling itself again and again.
  2. It has 2 cases to check for : base case(s) and recursive case.
  3. Base case is for terminating the function.
  4. Recursive case is for the copying itself into smaller problems.
  5. Recursive case should converge itself to base case.
  6. Recursive case makes a copy of itself in the memory and once that copy returns or terminate, the memory gets freed for that method.