Recursion

Prerequisites:

Basic knowledge about recursion: If you do not have this knowledge, then I recommend that you go through my previous blog, where I’ve covered all the concepts required for this blog.

Level I:

This blog tries to understand how to write recursive functions more effectively by solving a few basic questions. In upcoming blogs, we will try to solve some algorithms and do some advanced stuff.

Question 1:

W.A.P. to the factorial of a number.

Whenever you get a question, think about how to solve it. Now, don’t go directly to the recursion; just think about the logic of solving it using any easy method that you know.

Now, try to optimize that into a recursive function. In general, we solve it using loops, right?

In loops, we set the condition, increment one by one, and multiply the variable’s default value (which is one) with the value of the initialized variable in the loop.

Now, the approach for solving this using a recursive function would be to pass the number into a function, which should multiply with its decremented value.

This is going to happen until the base condition occurs, i.e., until we reach zero.

After reaching zero, all the answers stored by the individual recursion calls stored in stacks are called back and combined to give the final answer.

After passing the answer generated by the individual recursion call, the function will be removed from the stack.

static int factRec(int num){
        if (num<=1){
            return num; //base condition
        }
        return num * factRec(num-1); //calling the function itself
    }

An illustrative explanation for the factorization of numbers using recursion

Question 2:

W.A.P. to print the sum of N to 1.

Now, take a break for two minutes and try to solve it on your own. I’ll provide the solution for this at the end of this blog.

Question 3:

W.A.P. to print the sum of digits

In the iterative method, we are used to declaring a few variables, storing them temporarily, and doing a lot of stuff with that, right?

But, when it comes to recursion, it’s very simple.

Let us try to generalize things here.

The % operator gets the number’s last digit, and the / operator multiplied by 10 gives the number removed from the last number.

And by applying the base condition and recurrence relation, we can easily solve this question.

static int fun(int num){
        if (num==0){
            return 0; //Base condition
        }
        return (num%10) + fun(num/10);//Recurrence relation
    }

A sum of digits using recursion

Question 4:

W.A.P. to print the product of digits

The same approach would be followed for this. I just need to change a few things here. That is, change the operator from addition to multiplication.

static int fun(int num){
    if (num==1){
        return 1;
    }
    return (num%10) * fun(num/10);
}

Question 5:

W.A.P. to reverse the number

Here, instead of changing the whole number and printing the number, here we just use the % operator to print the last number and then remove the last digit from the number. We repeat this until the last number exists, this becomes the base condition now.

public class Reverse {
        static int sum = 0;
        static void rev1(int n) {
            if (n == 0) {
                return;
            }
            System.out.print(n%10);
            rev1(n/10);
        }

        public static void main(String[] args) {
            rev1(12543);
        }
}

Question 6:

W.A.P. to count the number of zeros

public class CountZeros {
    public static void main(String[] args) {
        System.out.println(count(30210004));
    }

    static int count(int n) {
        return helper(n, 0);
    }

    static int helper(int n, int c) {
        if (n == 0) {
            return c;
        }

        int rem = n % 10;
        if (rem == 0) {
            return helper(n/10, c+1);
        }
        return helper(n/10, c);
    }
}

In upcoming recursion blogs, we are going to solve a few complicated algorithms and solve leet code questions to better understand recursion and get familiar with it.

If you have learned anything new from my blog, please like this article and share it on your social networks. Don’t forget to tag me as @yoursmanjunadh.