Some simple problems using Recursion

In this article, let's solve a few beginner level problems. The hope is to make recursion steal your heart xD

Print N to 1 without loops Solve

The problem is as simple as it gets. Given a value of N, the target is to simply print the values from N to 1. The catch is, that we've to do it without using loops.

No points for guessing that recursion is gonna come to our rescue.

As taught in the previous article, think what can be a smaller version of the actual problem that can be delegated to our helper i.e. recursion.

So, what we can do is, just print the value of N, because that's what needs to be done first. Now, once done, we can simply make a recursive call, by passing N - 1 to the parameters, and recursion will take care of the rest.

Do think of the base case, and try to implement yourself before looking at the implementation below.

void printNosReverse(int N)
{
    if(N == 0)
        return;
    cout << N << " ";
    printNosReverse(N - 1);
}

Print 1 to N without loops Solve

The problem is very similar to the last one. Given a value of N, the target is to print the values from 1 to N. The catch, again, is that we've to do it without using loops.

I, not only urge you, but instruct you as your teacher, to try this one before looking at the solution. Remember the gym analogy from here?

I hope you've tried your best to solve it, and only then you're reading this.

So, the solution is very similar to the last one. There, we first printed N and then made a recursive call for printNosReverse(N-1), why? Because N was required to be printed first, and then the other numbers.

In this problem, we'll simply do the reverse, we'll make the recursive call printNos(N-1) first, and assume that recursion will take care of that, and after it's done, we'll do our small job, which is to print N.

void printNos(int N)
{
    if(N == 0)
        return;
    printNos(N - 1);
    cout << N << " ";
}

Fibonacci Number Solve

I know this article has become a bit longer than normal, but let's do one last. It's an interesting one, as long as you don't get into the math of the time complexity xD

Okay, so the problem says that given a number N, find the N^th fibonacci number.

How to solve?

The definition in itself gives the solution:

1. When N <= 1, our answer is equal to N only. (i.e. if N = 0, then F(0) = 0 and if N = 1, then F(1) = 1)
2. Otherwise, our answer is equal to F(N - 1) + F(N - 2).

int fib(int n) {
    if(n <= 1)
        return n; 
    return fib(n - 1) + fib(n - 2);
}

I hope at least the solutions and way to think about recursion have started making some sense now, if not the time & space complexity analysis. We'll cover it in the coming articles.