C++ Recursive Functions

Introduction

A recursive function is a function that calls itself to solve a problem. Recursive functions simplify the code for problems that can be broken down into smaller, similar subproblems. Recursion is used, but it should be used carefully to avoid issues like infinite recursion and stack overflow.

How Recursive Functions Work

Recursive functions have two main components:

1. Base Case: The condition under which the recursion stops. This prevents infinite recursion.
2. Recursive Case: The part of the function that calls itself with modified arguments, gradually approaching the base case.

Example: Factorial Calculation

The factorial of a non-negative integer ( n ) is the product of all positive integers less than or equal to ( n ). It is denoted as ( n! ) and can be defined recursively as:

• ( 0! = 1 ) (base case)
• ( n! = n \times (n-1)! ) (recursive case)

Factorial Function

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0) { // Base case
        return 1;
    } else {
        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 factorial function calls itself with ( n-1 ) until ( n ) is 0.
• When ( n ) is 0, the function returns 1, ending the recursion.
• The results are multiplied together as the recursion unwinds.

Example: Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. It can be defined recursively as:

• ( F(0) = 0 ) (base case)
• ( F(1) = 1 ) (base case)
• ( F(n) = F(n-1) + F(n-2) ) (recursive case)

Fibonacci Function

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n == 0) { // Base case
        return 0;
    } else if (n == 1) { // Base case
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
    }
}

int main() {
    int num = 10;
    cout << "Fibonacci of " << num << " is " << fibonacci(num) << endl;
    return 0;
}

Output

Fibonacci of 10 is 55

Explanation

• The fibonacci function calls itself with ( n-1 ) and ( n-2 ) until ( n ) is 0 or 1.
• When ( n ) is 0 or 1, the function returns 0 or 1, ending the recursion.
• The results are added together as the recursion unwinds.

Example Programs

Example 1: Sum of Natural Numbers

The sum of the first ( n ) natural numbers can be defined recursively as:

• Sum(0) = 0 (base case)
• Sum(n) = n + Sum(n-1) (recursive case)

#include <iostream>
using namespace std;

int sum(int n) {
    if (n == 0) { // Base case
        return 0;
    } else {
        return n + sum(n - 1); // Recursive case
    }
}

int main() {
    int num = 10;
    cout << "Sum of first " << num << " natural numbers is " << sum(num) << endl;
    return 0;
}

Output

Sum of first 10 natural numbers is 55

Explanation

• The sum function calls itself with ( n-1 ) until ( n ) is 0.
• When ( n ) is 0, the function returns 0, ending the recursion.
• The results are added together as the recursion unwinds.

Example 2: Power Calculation

The power of a number ( x ) raised to the power ( n ) can be defined recursively as:

• Power(x, 0) = 1 (base case)
• Power(x, n) = x \times Power(x, n-1) (recursive case)

#include <iostream>
using namespace std;

int power(int x, int n) {
    if (n == 0) { // Base case
        return 1;
    } else {
        return x * power(x, n - 1); // Recursive case
    }
}

int main() {
    int base = 2, exponent = 5;
    cout << base << " raised to the power " << exponent << " is " << power(base, exponent) << endl;
    return 0;
}

Output

2 raised to the power 5 is 32

Explanation

• The power function calls itself with ( n-1 ) until ( n ) is 0.
• When ( n ) is 0, the function returns 1, ending the recursion.
• The results are multiplied together as the recursion unwinds.

Tail Recursion

Tail recursion is a special case of recursion where the recursive call is the last statement in the function. Tail-recursive functions can be optimized by the compiler to avoid using additional stack space for each call, making them as efficient as iterative functions.

Example: Tail Recursion

#include <iostream>
using namespace std;

int factorialTail(int n, int accumulator = 1) {
    if (n == 0) { // Base case
        return accumulator;
    } else {
        return factorialTail(n - 1, n * accumulator); // Tail-recursive case
    }
}

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorialTail(num) << endl;
    return 0;
}

Output

Factorial of 5 is 120

Explanation

• The factorialTail function calls itself with ( n-1 ) and updates the accumulator until ( n ) is 0.
• When ( n ) is 0, the function returns the accumulator, ending the recursion.
• The results are accumulated without additional stack space, making it efficient.

Conclusion

Recursive functions in C++ provide a powerful way to solve problems that can be broken down into smaller, similar subproblems. This chapter covered the basics of recursive functions, including factorial calculation, Fibonacci sequence, sum of natural numbers, and power calculation. It also introduced tail recursion, which can be optimized by the compiler for efficiency. Understanding how to use recursive functions effectively is essential for solving complex problems in a simplified manner.