Skip to main content

Recursion Basics

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

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.

Sample Input

5

Sample Output

5 4 3 2 1

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.

Implementation 
void printNosReverse(int N)
{
    if(N == 0)
        return;
    cout << N << " ";
    printNosReverse(N - 1);
}
Time & Space Complexity

Time: O(N)
Space: O(N)

If you're wondering how, you've 2 options:
1. Think on your own.
2. Read the next article & then think on your own xD

Print 1 to N without loops

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.

Sample Input

5

Sample Output

1 2 3 4 5

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.

Implementation 
void printNos(int N)
{
    if(N == 0)
        return;
    printNos(N - 1);
    cout << N << " ";
}
Time & Space Complexity

Time: O(N) Space: O(N)

If you're wondering how, you've 2 options:

  1. Think on your own.
  2. Read the next article & then think on your own xD

Fibonacci Number

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 Nth fibonacci number.

Now, what is fibonacci series and what is a fibonacci number?

Fibonacci series is an infinite series that goes like 0, 1, 1, 2, 3, 5, 8, 13, 21 and so on...

The 0th term is 0, the 1st term is 1, and the terms after that are equal to the sum of the previous 2 terms i.e.

F(N) = F(N - 1) + F(N - 2)

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).
Implementation 
int fib(int n) {
    if(n <= 1)
        return n; 
    return fib(n - 1) + fib(n - 2);
}
Time & Space Complexity

Okay, so in the above case, calculating the exact time complexity is not a piece of cake.

In fact, if I were to take a guess, I'd say may be more than 20% of the MAANG engineers may not be able to do it.

But still: Time: O(2N) [Approximate] Space: O(N)

You can refer to this external article to dive deep into the time complexity, if interested. [Do it at your own risk xD]

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.