Know about me
Hey, Welcome to my blog on Recursion !!!
This recursion blog is totally for beginners if you are very new to recursion then it is very helpful for you to get into recursion and you have already started recursion then it will be very helpful for you to revise the basics and clear your concepts. Your suggestions will be appreciated in the comment box, so don't forget to write your feedback.
Now Enjoy the Blog !!!

Prerequisite:
You must have a good understanding of the functions, function calls, and basic syntax of classes and objects (as the answer contains classes).
Assumed that you are already familiar with the basics of C++.

Recursion is a way of solving a problem where a function calls itself until the base condition is matched. The base condition is the stopping point of the recursive function. In other words, Recursion is a way of solving a problem by breaking it down into smaller and smaller subproblems.

Two parts of recursion:
a. Base Case:
The stopping condition of the recursive function is Base Case. It is also known as a Specified Condition. And in a single recursive function, there can be multiple base conditions and at least one.

b. Recursive Case:
This case deals with breaking the given problem into multiple sub-problems.

How recursive function works:
when a function is called, at first the base condition is checked if it gets matched then the function will get stopped returning the base condition value.
Otherwise, the function calls itself with some modified parameters each time (as input) and the function continues calling itself until the base condition is reached and recursion stops.
Recursion without base condition is infinite recursion that can cause StackOverflow or even can crash the program. So, the base condition is compulsory in every recursive function.

Understand Recursion from 5 Basics Programs

Recursive function to Print numbers from 1 to N

#include <iostream>
using namespace std;
void printNumbers(int n) {    // recursive Function
  if (n == 0) {    // Base condition
    return;
  }
  printNumbers(n - 1);    // Callback Function
  cout << n << " ";
}

int main() {
  int n = 4;
  printNumbers(n);
  return 0;
}

Explanation:
The function printNumbers takes an integer argument n.

The base case of the recursion is when n equals 0. In this case, the function simply returns without printing anything.
For other values n, the function first calls itself with n-1 as the argument. This ensures that the function will keep calling itself until n equals 0, and the base case is reached.
After the recursive call, the function prints the value of n followed by a space.
In the main function, the value of n is set to 5 and the printNumbers the function is called with n as the argument

.
The output of the program will be: "1 2 3 4".

Understand the approach and steps with a recursive diagram:

Recursive function to find the Factorial of a Number

A recursive function to find the factorial of a number is a function that calls itself repeatedly until a defined base case is reached. The base case is typically when the number being factored is 0 or 1 (it is 1 in the given program), and the result is 1. For other numbers, the function calculates the factorial by multiplying the current number by the result of calling itself with the next number down.

Here is the code

#include<iostream>
using namespace std;
int Nfactorial(int n){    // Recursive function
    int factorial = 1;
    if(n==1){    // Base Condition
        return 1;
    }
    else{
    // Recursive Case (Function calling itself)
        return n*Nfactorial(n-1);
    }
}
int main(){
    int n = 5;
// prints the factorial of n
    cout<<"The factorial of "<<<n<" is: "<<Nfactorial(n)<<endl;    

}

Output:
The factorial of 5 is: 120

Diagram:
The perfect way to understand recursion effectively is to give some time to the given picture, just do some heat and trial surgery with pen and paper. Use your number (random number by yourself) and check the output yourself.

For the factorial of "N"
Your Output Should be = N*(N-1)*(N-2)*(N-3)*........*3*2*1

Diagram:

Recursive function to find the greatest common divisor (GCD) of two numbers.

The greatest common divisor (GCD) of two numbers is the largest positive integer that divides both numbers without a remainder. The Euclidean algorithm is a common method for finding the GCD of two numbers. The algorithm works by dividing the larger number by the smaller number and taking the GCD of the smaller number and the remainder of the division. The process is repeated until the remainder is zero, at which point the smaller number is the GCD. This can be implemented recursively as follows:

Here is the code...

#include<iostream>
using namespace std;

int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}

int main() {
  int a, b;
  cin >> a >> b;
  cout << "The GCD of " << a << " and " << b << " is " << gcd(a, b) << endl;
  return 0;
}

Explanation:
In this code, the gcd the function takes two integer arguments a and b. The base case is when b is equal to zero, in which case a is returned as the GCD. In the recursive case, the function calls itself with b and the remainder of a divided by b as arguments, which ensures that the GCD is calculated by continuously reducing the larger number and dividing it by the smaller number until the remainder is zero.

Diagrams:

Recursive function to reverse a string.
The problem of reversing a string can be solved using recursion by breaking the string down into smaller sub-strings until the base case is reached. The base case is when the string has only one character, in which case it is already reversed.

In each recursive call, the first character of the string is added to the end of the reversed substring. This process continues until the original string is completely reversed.
Here is the code ...

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

// recursive function
void reverse_string(string &str, int start, int end) {
    if (start >= end)    // base conditon
        return;
    swap(str[start], str[end]);
    reverse_string(str, start + 1, end - 1); // function callback
}

int main() {
    string str = "Hello, World!";
    reverse_string(str, 0, str.length() - 1);
    cout << str << endl;
    return 0;
}

Explanation:
This code takes a string str and the indices start and end of the substring to be reversed. In each call, the first and last characters are swapped using swap and then the function is called with start and end indices incremented and decremented by 1 respectively. The process continues until start is greater than or equal to end, which is the base case and terminates the recursion.

Diagram:

Recursive Function to print the nth Fibonacci number
The Fibonacci sequence is a sequence of numbers in which each number is the sum of the two preceding ones, starting from 0 and 1. The formula for the nth Fibonacci number is:

Here is the code

#include <iostream>
using namespace std;

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

int main() {
    int n;
    cout<<"Enter a positive number : ";
    cin>>n;
    cout << "The " << n << "th Fibonacci number is: " << fib(n) << endl;
    return 0;
}

Explanation:
These are the step-by-step Explanations :

The fib the function takes an integer n as an argument and returns the nth Fibonacci number.
The function checks the base cases where n is 0 or 1 and returns n in these cases.
If n is greater than 1, the function returns the sum of the (n-1)th and (n-2)th Fibonacci numbers, which are calculated through a recursive call to the fib function.
In the main function, the user inputs a positive integer n and the nth Fibonacci number is computed using the fib function and displayed on the screen.

Diagram:

Function Overlapping in Fibonacci Recursive function
Function overlapping occurs when the same function is called multiple times with the same input. This can result in a large number of redundant calculations, especially in the case of a recursive function.

In the case of a recursive implementation of the Fibonacci sequence, function overlapping can occur as the function is called multiple times for the same n value. This can lead to a large amount of time and space being used, making the solution inefficient.

For example, if you were to calculate the fib(4) value using a recursive function, the same calculations would be performed multiple times:
For example:

Hope You liked this blog on recursion, next challenge is Dynamic Programming. So, go and Checkout here(will be available soon).

If you found this useful, Don't forget to like, comment, and leave your feedback below.
Also, subscribe newsletter and get a notification to read such blogs from your email.

Thank You !!!
Have a good day!!!

Follow me Twitter Linkedin Instagram

Recursion with 5 Basics Questions (C++)

Subscribe to my newsletter

Ankit Sharma

Ankit Sharma