RECURSIVE FUNCTION

·       A function that calls itself.

·       Solving problemsà is broken down into smaller subproblems of the same type.

·       Depends on solutions to smaller instances of the same problem.

·       Widely used inà like calculating factorials, traversing trees, or solving problems like the Fibonacci sequence.

 

 Key Elements of a Recursive Function

1. Base Case: A condition that stops the recursion.
2. Recursive Case: A condition where the function calls itself.

 

  Syntax

return_type function_name(parameters) {

    // Base case

    if (condition) {

        return value; // Stop recursion

    }

    // Recursive case

    return function_name(modified_parameters); // Call itself

}

 

Example: Factorial Using Recursion

The factorial of a number n (denoted as n!) is calculated as:

n!=n×(n−1)×(n−2)×⋯×1

 

Using recursion:

#include <iostream>

using namespace std;

 

int factorial(int n) {

    if (n == 0 || n == 1)  // Base case

        return 1;

    else

        return n * factorial(n - 1);  // Recursive call

}

 

int main() {

    int num = 5;

    cout << "Factorial of " << num << " is " << factorial(num) << endl;

    return 0;

}

 

Explanations:-

1. factorial(5)= 5*4*3*2*1.
2. base case factorial(1) is reached, recursion stops.
3. Recursive Caseà 5.

 

Example: Fibonacci Series Using Recursion

The Fibonacci sequence is defined as:

F(n)=F(n−1)+F(n−2)

Where:

• F(0)=0
• F(1)=1

 

Implementation:

#include <iostream>

using namespace std;

 

int fibonacci(int n) {

    if (n == 0)  // Base case

        return 0;

    else if (n == 1)

        return 1;

    else

        return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive case

}

 

int main() {

    int num = 6;

    cout << "Fibonacci(" << num << ") = " << fibonacci(num) << endl;

    return 0;

}

 

Output:-

Fibonacci number at position 6 is 8

 

Sequence

 0, 1, 1, 2, 3, 5, 8,   (position 6 is 8)

===========================================

 

Advantages of Recursion

- Simplicity: divided into subproblems (e.g., tree traversal, divide-and-conquer algorithms).

- Readability: Reflects mathematical definitions directly (e.g., factorial, Fibonacci).

Modularity: Breaks down problems into smaller sub-problems.

 

 Disadvantages of Recursion

Performance: call adds a layer to the call stackà high memory usage and stack overflow for large inputs.

Speed: slower than iterative àdue to function call overhead.

Memory Usage: Uses more memory.

Complexity: harder to debug and understand, especially for deep recursion.

==========================