Hey Coders! today, we are going to dive deeper into the concept of recursion. We'll explore how recursion works, its fundamental principles, and see some practical examples in action.

List of content:

• Definition.
• Need of Recursion.
• Types of Recursion.
• Examples with Outputs.
• Advantages and disadvantages over iteration.

Let's start.....

Definition:

Recursion is a programming technique where a function calls itself in order to solve a problem. The idea is to break down a complex problem into smaller, more manageable sub-problems, solving each one recursively until reaching a base case that can be solved directly.

where,

• Base case: This is the condition that stops the recursion. When the function reaches this point, it returns a direct result without making further recursive calls.
• Recursive case: This is where the function calls itself with a smaller or simpler version of the original problem.

Consider an example of factorial number-

function factorial(n):
    if n == 0 or n == 1:           // Base Case
        return 1
        
    else:                          // Recursive Case
        return n * factorial(n - 1)

Need of Recursion:

• Recursion can simplify the solution of complex problems by breaking them down into smaller, more manageable sub-problems.
• Recursive functions can be more readable and easier to understand than their iterative counterparts.
• In many cases, recursion can lead to more efficient use of memory through techniques like tail recursion.
• Recursion is crucial for algorithms that involve backtracking, such as solving puzzles (e.g., Sudoku),etc.
• Many fundamental algorithms, such as QuickSort, MergeSort, and binary search, rely on recursion.
• Recursion is used in mathematical and theoretical computations, such as calculating factorials, generating Fibonacci sequences, and solving differential equations.

Types of Recursion:

• Direct Recursion: This occurs when a function directly calls itself.

    function recursiveFunction(parameters):
    if base_condition:
        return base_value
    else:
        return recursiveFunction(modified_parameters)
  
  

  Example of Direct recursion:

  • Tail Recursion
  • Tree Recursion
  • Nested Recursion

• Indirect Recursion: A function calls another function, which in turn calls the first function.

      function functionA(parameters):
    if base_conditionA:
        return base_valueA
    else:
        return functionB(modified_parameters)
  
    function functionB(parameters):
    if base_conditionB:
        return base_valueB
    else:
        return functionA(modified_parameters)
  
  

Some common Examples:

1. Sum of Natural Numbers:

In this problem we have to find the sum of N Natural numbers..

Approach 1 - Adding elements one by one..

F(n) = 0 + 1 + 2 + 3 +……..+ n

but we have another approach to solve this

Approach 2 - Recursively Adding..

f(n) = 0 ,n=0
f(n) = n + f(n-1) ,n>=1

Code in C:

#include<stdio.h>

int SumOfNatural(int n){
    if(n==0) return 0;        // base case
    
    return (n + SumOfNatural(n-1));    //  recursive case
}


void main(){
    int n = 4;
    printf("%d",SumOfNatural(n));
}

Code in Java:

class solution{
    public int SumOFNatural(int n){
        if(n==0) return 0;  // Base case
    
        return (n + SumOfNatural(n-1)); // recursive case
    }

    public static void main(String[] args){
        int n = 4;
        System.out.println(SumOfNatural(n));
    }
}

Code in C++:

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

int SumOfNatural(int n){
    if(n==0) return 0;        // base case
    
    return (n + SumOfNatural(n-1));    //  recursive case
}


int main(){
    int n = 4;
    cout<<SumOfNatural(n);
    return 0;
}

Output:

Output: 10

2. Factorial Number:

The factorial of a number 𝑛(denoted as 𝑛!) is the product of all positive integers less than or equal to 𝑛.

Approach 1 - By Multiply one by one..

F(n) = 1* 2* 3* 4*....*n

but we have another approach to solve this

Approach 2 - Recursive approach..

F(n) = 1 ,n=0
F(n) = n*F(n-1) ,n>=1

Code in C:

#include<stdio.h>

int factorial(int n){
    if(n==0) return 1;  // Base case
    
    return (n*factorial(n-1));  // recursive case
} 


void main(){
    int n = 4;
    printf("%d",factorial(n));
}

Code in Java:

class solution{
    public int factorial(int n){
        if(n==0) return 1;  // Base case
    
        return (n*factorial(n-1)); // recursive case
    }

    public static void main(String[] args){
        int n = 4;
        System.out.println(factorial(n));
    }
}

Code in C++:

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

int factorial(int n){
    if(n==0) return 1;  // Base case
    
    return (n*factorial(n-1));  // recursive case
} 


int main(){
    int n = 4;
    cout<<factorial(n);
    return 0;
}

Output:

Output: 24

3. Fibonacci series:

The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.

Approach 1 - Mathematically approach..

F(n) = 0+1+1+2+...nth

but we have another approach to solve this

Approach 2 - Recursive approach..

F(n) = 0 1 , n=0 , n=1
F(n) = F(n-1) + F(n-2) ,otherwise

Code in C:

#include<stdio.h>

int fib(int n){
    if (n == 0) return 0;                // Base Case
    
    if (n == 1 || n == 2) return 1;      // Base case

    // Recursion function
    return (fib(n - 1) + fib(n - 2));
}

void main(){
    int n = 5;
    printf("Fibonacci series of %d numbers is: ",n);
    
    for (int i = 0; i < n; i++) {
        printf("%d ", fib(i));
    }
}

Code in Java:

class solution{
    public int fib(int n){
        if(n==0) return 0;  // Base case
        if (n == 1 || n == 2) return 1;      // Base case
        
        return (fib(n - 1) + fib(n - 2)); // recursive case
    }

    public static void main(String[] args){
        int n = 5;
        System.out.println("Fibonacci series of "+ n + "is: ");
        for (int i = 0; i < n; i++) {
            System.out.println(fib(i));
        }
    }
}

Code in C++:

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

int fib(int n){
    if (n == 0) return 0;                // Base Case
    
    if (n == 1 || n == 2) return 1;      // Base case

    // Recursion function
    return (fib(n - 1) + fib(n - 2));
}

int main(){
    int n = 5;
    cout<<"Fibonacci series of "<<n<<" numbers is: ";
    
    for (int i = 0; i < n; i++) {
        cout<<fib(i);
    }
    return 0;
}

Output:

Output: Fibonacci sereis of 5 is: 0 1 1 2 3

Advantages and disadvantages over iteration:

For more topics click here.

Happy Coding!