C++ Recursive Functions

C++ Recursive Functions

A recursive function in C++ is a function that calls itself directly or indirectly to solve a problem. Recursion is often used for problems that can be divided into smaller, similar sub-problems, such as calculating factorials, Fibonacci numbers, or traversing data structures like trees.

Syntax

return_type function_name(parameters) {
    if(base_condition) {
        // stopping condition
        return value;
    } else {
        // recursive call
        return function_name(modified_parameters);
    }
}

Example Program: Factorial Using Recursion

#include <iostream>
using namespace std;

// Recursive function to calculate factorial
int factorial(int n) {
    if(n == 0 || n == 1) { // Base condition
        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;
}

Output

Factorial of 5 is 120

Example: Fibonacci Series Using Recursion

#include <iostream>
using namespace std;

// Recursive function to calculate Fibonacci number
int fibonacci(int n) {
    if(n == 0) return 0;          // Base condition
    if(n == 1) return 1;          // Base condition
    return fibonacci(n - 1) + fibonacci(n - 2); // Recursive call
}

int main() {

    int n = 7;
    cout << "Fibonacci series up to " << n << ": ";

    for(int i = 0; i < n; i++) {
        cout << fibonacci(i) << " ";
    }

    return 0;
}

Output

Fibonacci series up to 7: 0 1 1 2 3 5 8

Important Notes

• Recursive functions must have a base condition to stop the recursion; otherwise, it leads to infinite recursion.
• Each recursive call adds a new frame to the call stack. Excessive recursion may cause stack overflow.
• Recursion is useful for problems that can be divided into smaller similar sub-problems.

Next Topic

Next, learn about C++ Arrays.