Recursion : Introduction to Data Structures and Algorithms

This is the start of a new Data Structure series where I will be focusing on introducing you to crucial data structures which will help you in competitive coding and development. Follow along on this beautiful journey and you will not be disappointed!

Prerequisites: Basic understanding of mathematics and any programming language

What is Recursion?

"To understand recursion, you must first understand recursion."

Recursion simply means calling a function again and again. It takes a big problem and minimizes it into a smaller problem.

Why Recursion?

It reduces the amount of code we need to write as well as it is intuitive. It is a very important data structure to learn to combat future concepts like dynamic programming, Trees, Graph, Backtracking and a whole lot more!

Methodology

A recursion function is divided into three phases

Base case
Recursive call
Return Statements

A base case means a condition where you want your code to stop working

A recursive call is the body of the recursive function. Whatever operations you want to perform are written here.

A return statement returns the output in the form of an integer, float value, char or sometimes void.

Example ...

Let us take an example of a factorial program. As we all know

1! = 1

2! = 2 * 1!

3! = 3 * 2! and so on...

So if we want to calculate the value of 4! we multiply 4 by 3!

Now to calculate the value of 3! we multiply 3 by 2!

We see a pattern

Factorial(n) = n * Factorial(n-1)

The pattern will be repeated till n = 1. Once n = 1, we know our answer is 1.

Finally, we return the answer.

Code for factorial in C++

#include<bits/stdc++.h>
using namespace std;

int factorial(int n)
{

    int ans;
    //Base Case 
    if(n<=1)
        ans = 1;

    else
    {
        //Recursive call for factorial of n-1
        ans =  n*factorial(n-1);
    }

    //return statement
    return ans;

}

int main()
{
    int n;
    cout<<"Enter the number : " ;
    cin>>n;

    cout<<"The factorial of "<<n<<" is :"<<factorial(n)<<endl;
}

Practice Problems:

To introduce yourself to the concept of recursion, you can practice Fibonacci, Tower of Hanoi, and Printing permutations of an array.

Recursion : Introduction to Data Structures and Algorithms | Topic - 1

Table of contents