C++ Recursion

Welcome to The Coding College! In this tutorial, we’ll discuss recursion in C++, a fundamental programming concept where a function calls itself to solve a problem.

What is Recursion?

Recursion is a technique where a function solves a problem by calling itself repeatedly until a base condition is met. Each recursive call simplifies the problem into smaller sub-problems.

Types of Recursion

1. Direct Recursion: A function calls itself directly.
2. Indirect Recursion: A function calls another function that eventually calls the original function.

Anatomy of a Recursive Function

A recursive function generally consists of two parts:

1. Base Case: The condition under which the recursion ends.
2. Recursive Case: The part where the function calls itself to solve a smaller version of the problem.

Example: Factorial of a Number

Code Example

#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  

How Recursion Works

1. Function Call Stack:
   Each recursive call is added to the stack and remains there until the base case is reached.
2. Backtracking:
   Once the base case is reached, the functions return their results one by one in reverse order.

Example: Fibonacci Sequence

Code Example

#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 n = 7;
    cout << "Fibonacci number at position " << n << " is " << fibonacci(n) << endl;
    return 0;
}

Output

Fibonacci number at position 7 is 13  

Indirect Recursion

In indirect recursion, two or more functions call each other in a cycle.

Example

#include <iostream>
using namespace std;

void functionA(int n);
void functionB(int n);

void functionA(int n) {
    if (n > 0) {
        cout << "A: " << n << endl;
        functionB(n - 1);
    }
}

void functionB(int n) {
    if (n > 0) {
        cout << "B: " << n << endl;
        functionA(n / 2);
    }
}

int main() {
    functionA(10);
    return 0;
}

Output

A: 10  
B: 9  
A: 4  
B: 3  
A: 1  

Advantages of Recursion

1. Simpler Code: Recursion often makes the code easier to understand for problems like tree traversal or divide-and-conquer algorithms.
2. Effective for Problems with Repetitive Sub-Problems: Recursion simplifies problems like factorial, Fibonacci, and graph traversal.

Disadvantages of Recursion

1. Performance: Recursive functions can be slower due to the overhead of repeated function calls.
2. Risk of Stack Overflow: Too many recursive calls can exhaust the call stack.

Tail Recursion

Tail recursion is a form of recursion where the recursive call is the last operation in the function. Tail-recursive functions are optimized by compilers to avoid creating new stack frames for each call.

Example

#include <iostream>
using namespace std;

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

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

Common Uses of Recursion

1. Mathematical Computations: Factorials, Fibonacci numbers, etc.
2. Tree and Graph Traversal: Depth-first search (DFS), binary tree traversal.
3. Divide and Conquer Algorithms: Merge sort, quick sort, etc.
4. Dynamic Programming: Solving problems by breaking them into sub-problems.

Practical Example: Recursive Sum of an Array

#include <iostream>
using namespace std;

int sumArray(int arr[], int n) {
    if (n == 0) { // Base case
        return 0;
    } else {
        return arr[n - 1] + sumArray(arr, n - 1); // Recursive case
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Sum of array elements: " << sumArray(arr, size) << endl;
    return 0;
}

Output

Sum of array elements: 15  

Tips for Using Recursion

1. Always define a clear base case to prevent infinite recursion.
2. Be mindful of the call stack size for large input values.
3. Consider using iterative solutions or tail recursion for better performance.

Explore More at The Coding College

Dive deeper into recursion and its applications in data structures and algorithms on The Coding College.