C++ Recursion Function

A programming method called recursion that uses a function to call itself to address lesser problems. The Fibonacci sequence, factorial computation, and tree traversal are just a few of the many C++ problems that may be broken down into related sub-problems and are usually resolved using recursion.

Working of Recursive Function:

A recursive function is made up of two main parts:

• Base Case: The situation that prevents an infinite loop from occurring by stopping the recursion.
• Recursive Case: By invoking itself with a changed parameter, the function progressively gets closer to the basic case.

Key Features of the Recursive Function:

Several key features of the recursive function in C++ are as follows:

1. Base Case and Recursive Case:

• There must be a base case for each recursive function to halt the recursion.
• The function itself is called in the recursive scenario with altered parameters.

2. Function Call Stack Usage:

• The call stack retains each recursive call until the base case is reached.
• The stack unwinds and all outstanding calls are resolved after the base case returns.

3. Memory and  performance Considerations:

• Stack frames cause recursive functions to consume more memory.
• If deep recursion is not managed appropriately, stack overflow may result.

4. Simplicity and Readability:

• Factorial, tree traversal, and Fibonacci are some examples of simplifications provided by recursion.
• It lends itself toward simpler and more logical thinking in problem solving.

5. Direct and Indirect Recursion:

• When a function calls itself directly, such as factorial(n), this is known as direct recursion.
• When one function calls another, which in turn calls the original function, this is known as an indirect recursion.

Algorithm:

Step 1: Start 

Step 2: Define a function FACTORIAL(n) 

        - If n == 0, return 1 (Base case) 

        - Else, return n * FACTORIAL(n - 1) (Recursive case) 

Step 3: In the main function, take an integer input n 

Step 4: Call FACTORIAL(n) and store the result 

Step 5: Print the result 

Step 6: End 

Pseudo code:

FUNCTION FACTORIAL(n):

    IF n == 0 THEN

        RETURN 1

    ELSE

        RETURN n * FACTORIAL(n - 1)

    ENDIF

END FUNCTION

BEGIN MAIN

    DECLARE num AS INTEGER

    SET num = 5  // Example value

    DECLARE result AS INTEGER

    SET result = FACTORIAL(num)

    PRINT "Factorial of ", num, " is ", result

END MAIN

Example code for Recursive Function:

Example 1: Factorial Function

#include <iostream>

using namespace std;

int factorial(int n) {

    if (n == 0)  // Base case

        return 1;

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

}

int main() {

    int num = 5;

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

    return 0;

}

Output:

Factorial of 5 is 120

Explanation:

• The function returns 1 in the base situation when n == 0.
• If not, it keeps calling itself with n - 1 until it hits 0.

Example 2: Fibonacci Series using Recursion

The Fibonacci sequence starts with 0 and 1 and includes digits that are equal to the sum of two digits before them.

#include <iostream>

using namespace std;


int fibonacci(int n) {

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

        return 0;

    if (n == 1)  // Base case 2

        return 1;

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

}


int main() {

    int terms = 10; // Example: Print first 10 Fibonacci numbers

    cout << "Fibonacci Series: ";

    for (int i = 0; i < terms; i++) {

        cout << fibonacci(i) << " ";

    }

    cout << endl;

    return 0;

}

Output:

Fibonacci Series: 0 1 1 2 3 5 8 13 21 34

Explanation:

A. Base Cases:

If n == 0, return 0.

If n == 1, return 1.

B. Recursive Case:

Calls fibonacci(n-1) + fibonacci(n-2).

C. Loop in main() prints the first 10 Fibonacci numbers.

Advantages:

Several advantages of the recursion function in C++ are as follows:

• It addresses problems like tree traversal and backtracking by simplifying code.
• It breaks complex problems down into smaller, more manageable ones.

Disadvantages:

Several disadvantages of the recursion function in C++ are as follows:

• It invokes more routines, which results in a higher memory usage (stack use).
• It can cause stack overflow in the event that the depth of recursion is set excessively.

When to use Recursion:

• When dividing a problem into smaller ones are simple.
• When implementing an iterative solution is challenging or complex.

Conclusion:

In conclusion, recursion is a basic principle of C++, which breaks down complex problems into simpler, smaller sub-problems. It calls itself with a well-defined base case to avoid over-recursion. Despite recursion simplifying most programming cases like tree traversal, the Fibonacci series, and factorial computation, it requires careful management of memory due to the limitations of the function call stack. Recursion is neat and intuitive too, but elegance does not always come with power; sometimes, the overuse of recursion can lead to performance issues in particular cases. Iterative or optimized approaches could be better in those cases. Memoization is one possible example. Recursion is a concept that we need to master when trying to achieve clear problem-solving code through algorithms.