Basics Of recursion||recursion||recursion in C++||recursion explained||checking prime numbers using recursion||factorial using recursion||fibonacci series using recursion||GCD using recursion||LCM using recursion||Star pyramid pattern||Star pattern using recursion||String concatenation in C++||Advantages of recursion||Disadvantages of recursion||

-

👉 Basics Of Recursion 👈

                   -by Aaditya Nayak

In this blog I am going to explain about basics of recursion. I will be covering meaning of recursion, some basic programs using recursion, advantages of recursion. This blog will be very useful for beginners since recursion is a topic that is considered to be confusing and tricky at the beginners stage and for experienced its always good to brush up your concepts.


What is Recursion?


  • Recursion is defined as repeated application of procedure or definition.

  • In programming, as you know that functions are the set of instructions which can be defined once and can be called anywhere needed. 

  • While the recursion is the condition when a function calls itself inside the its own function definition.

  • In short you can remember that, in function definition if we are returning a function call of that function itself, this condition is known as recursion.

  • Or you can say when a function calls itself repeatedly the condition is called recursion.


Note : 

A general mistake people do at beginner stage that they try to do recursion in a function which don’t have return type, so always remember if you are a beginner that the recursion can only be done in a function which is returning something.


Basic Programs Using Recursion


Now let us see some basic programs using recursion:


Ex 1: To check whether the number is prime or not.


Code:


// 1. To check whether the number is prime or not

#include <iostream>
using namespace std;

// Here recursion is used in prime function

int prime(int n, int m)
{
    if (n > 2 && m < n)
    {

        if (n % m == 0)
        {
            return 1;
        }
        else
        {
            return prime(n, m + 1); // Recursive call
        }
    }
    else if (n == 2 && m <= n)
    {
        return 0;
    }
    else
    {
        return 2;
    }
}

int main()
{
    int x;
    string s;
    cout << "Enter the number you want to check for prime : ";
    cin >> x;

    if (prime(x, 2) == 0)
    {
        s = " is prime";
    }
    else if (prime(x, 2) == 1)
    {
        s = " is not prime";
    }

    if (s == " prime" || s == " not prime")
    {

        cout << "The number " << x << s;
    }
    else
    {
        cout << "Invalid input, Enter a positive number greater than or equal to 2";
    }

    return 0;
}


Output:





Ex 2: To find factorial of a given number.


Code:


// 2. To find factorial of given number

#include <iostream>
using namespace std;

int factorial = 1; // global variable fact

// Here recursion is used in find_factorial function

int find_factorial(int n)
{
    if (n >= 0)
    {
        if (n == 0 || n == 1)
        {
            factorial = factorial * 1; // value of fact updated

            return factorial; // returning the value of fact
        }
        else
        {
            factorial = factorial * (n); // value of fact updated

            return find_factorial(n - 1); // Recursive Call
        }
    }
    else
    {
        cout << "Wrong input, please give a positive number or ";
        return 0;
    }
}

int main()
{
    int x;

    cout << "Enter the number you want to find factorial of : ";
    cin >> x;

    cout << "The factorial of " << x << " is = " << find_factorial(x);

    return 0;
}


Output:





Ex 3: To find the number at nth place of fibonacci series.


Code:


// 3. To find the number at nth place of fibonacci series.

#include <iostream>
using namespace std;

// Here recursion is used in fib_n function

int fib_n(int n)
{
    if (n < 0)
    {
        cout << endl
             << "Wrong input, please enter a positive number or ";
        return 0;
    }
    else if (n == 1)
    {
        return 0;
    }
    else if (n == 2)
    {
        return 1;
    }
    else
    {
        return fib_n(n - 1) + fib_n(n - 2); // Recursive Call
    }
}

int main()
{
    int x;

    cout << "Enter the nth term you want to find in fibonacci series : ";
    cin >> x;

    cout << "The term number " << x << "of fibonacci series is = " << fib_n(x);
}


Output:




Ex 4: Finding GCD or HCF of given two numbers.


Code:


// 4. Finding GCD or HCF of given two numbers.

#include <iostream>
using namespace std;

// Here recursion is used in GCD function

int GCD(int x, int y)
{
    int temp;

    if (x < y)
    {
        temp = x;
        x = y;
        y = temp;
    }
    if ((x % y) == 0)
    {
        return y;
    }
    else
    {
        return GCD(x, x % y); // Recursive Call
    }
}

int main()
{
    int x, y;

    cout << "Enter two numbers you want to find GCD of" << endl;

    cout << "Enter the first number : ";
    cin >> x;

    cout << "Enter the second number : ";
    cin >> y;

    if(x>=0 && y>=0){

    cout << "The GCD of " << x << " and " << y << " is = " << GCD(x, y);

    return 0;
    }

    else{
        cout<<"Wrong input, please enter both numbers as positive or 0";
        return 0;
    }

}


Output:



Ex 5: LCM of two given numbers (LCM = Product of numbers / GCD )

Code:


// 5. LCM of two given numbers (LCM = Product of numbers / GCD )

#include <iostream>
using namespace std;

int GCD(int x, int y)
{
    int temp;

    if (x < y)
    {
        temp = x;
        x = y;
        y = temp;
    }
    if ((x % y) == 0)
    {
        return y;
    }
    else
    {
        return GCD(x, x % y);
    }
}

int main()
{
    int x, y;

    cout << "Enter two numbers you want to find LCM of" << endl;

    cout << "Enter the first number : ";
    cin >> x;

    cout << "Enter the second number : ";
    cin >> y;

    if (x >= 0 && y >= 0)
    {

        cout << "The LCM of " << x << " and " << y << " is = " << x * y / GCD(x, y);

        return 0;
    }

    else
    {
        cout << "Wrong input, please enter both numbers as positive or 0";
        return 0;
    }
}


Output:




Ex 6: Displaying n story pyramid where n is input


Code:


// 6. Displaying n story pyramid where n is input

#include <iostream>
#include <string>
using namespace std;

int fact = 1; //global variable fact

string concatenate1(string s1, int n) // To concatenate string
{
    string s = s1;

    for (int i = 0; i < n; i++)
    {
        s1 += s;
    }
    return s1;
}

string concatenate2(string s1, int n) // To concatenate string
{
    string s = s1;

    for (int i = 0; i < n - 1; i++)
    {
        s1 += s;
    }
    return s1;
}

// Here recursion is used in pyramid function

int pyramid(int n)
{
    string s = " ";
    string s1 = "*";

    if (n == 0)
    {
        return 0;
    }
    else
    {
        cout << concatenate1(s, n - 1) << concatenate2(s1, fact) << endl;
        fact = fact + 2;

        return pyramid(n - 1); // Recursive call
    }
}

int main()
{

    int x;

    if (x >= 0)
    {

        cout << "Enter how many stories pyramid you want : ";
        cin >> x;

        cout << "Your " << x << " story pyramid is as : " << endl;

        pyramid(x);
    }
    else
    {
        cout << "Wrong input, please enter a positive number ";
    }

    return 0;
}


Output:





Advantages And Disadvantages Of Recursion


Advantages: 


  • Recursion comes in handy in tree transversal (it’s a DSA concept no need to worry about it at beginner stage).

  • Recursion in some cases can reduce time complexity.

  • Recursion can be useful while you are writing a complex program and using loops becomes difficult.

  • There are more advantages of recursion as well, that you will come to know as you advance more in programming.


Disadvantages: 


  • Recursion in some case can complicate things as you have seen in Ex 6 😅.

  • Recursion in some case can be slow.

  • There are also more disadvantages of recursion as well, that you will come to know when you will know DSA concepts.


Now you are all done with basics of recursion. Now you can try recursion in different programs, you can try displaying inverse pyramid, try using recursion in place of loops, try searching for DSA concepts based upon recursion on internet.


THANKS FOR READING THE BLOG 

I Hope This was helpful 😊

Location: India

Comments

Post a Comment

Popular posts from this blog

What Is Functions In C++ ? || Explained By Examples || Function Types

-
Image
  👉 WHAT IS FUNCTION 👈 By - Dhruv Arne   Function – Function is a block of a code that is executed only when it is called in the code. In C++ if you want to make a function then the syntax is   Return_type   function_name ( parameter_datatype   parameters ( if  it have)) { Code Return  something; }   Here return type is the type of data which function is going to be returned. It is not mandatory that the function should have return something always, it is optional. But now you have a question in your mind that if we don’t return something then what we will write in the place of return_type when declaring a function?. I will tell you the answer you have to write void which means nothing. Void is a datatype in c++ that means nothing, so there is no example of a void data type because void means nothing. Now here in the syntax, I wrote a word parameter, so what does parameter mean?. Basically, parameters are a need of that functio...
Read more

Basics Of Operators||Basics of operators in C++||Basics of operators in cpp||Types of operators in C++||Arithmetic Operators||Comparision Operators||Binary Operators||Logical Operators||Bitwise Operators||Assignment Operators||Miscellaneous Operators||Bitwise Explained||Operators Precedence||

-
Image
👉  Basics Of OPERATORS IN C++  👈 -by Aaditya Nayak In this blog I am going to describe operators in C++ from scratch, their use ,applications, examples etc. This blog will be very useful for beginners and for experienced its always good to brush up your concepts. What is an operator?  • An Operator gives the instruction perform particular operation. Ex: A person which is operating a machine, keyboard of computer, mouse of computer etc.   • Mathematically operators are symbols which denotes particular operation to be performed on a expression or on some numbers. Ex: +, -, /, *, d/dx, ∑, ∏ etc.   • In programming an operator is a symbol that tells the compiler to perform specific mathematical or logical functions. C++ language is rich in built-in operators and provides the following types of operators − Arithmetic Operators. Relational Operators. Logical Operators. Ex: &&, ||, &, | etc. Operators in C++ Basic meaning of operators in C++ are sam...
Read more

Reference and Pointers in C++

-
Image
  by - Yash Ukalkar |  Introduction -  Pointers and reference variables are often used when one needs to write programs that control and manage the memory available in the machine. Pointers work close to memory and allow us to implement data storage and processing in an efficient manner. For example, a linked list is a data structure that uses pointers and allows us to store and delete data, in a sequential manner, but faster than many other methods.
Read more