Mastering Recursion

Welcome to the session on mastering recursion in C++! Understanding recursion is crucial in programming. It’s a technique where a function calls itself, breaking down a complex problem into manageable subproblems. Our goal today is to grasp tail recursion and use it effectively in C++.

Let's once again take a look at a familiar recursion example:

#include <iostream>

int factorial(int n) {
    if (n <= 1) return 1; // Base case
    return n * factorial(n - 1); // Recursive case
}

int main() {
    int number = 5;
    std::cout << "Factorial of " << number << " is " << factorial(number) << '\n'; // Output: Factorial of 5 is 120
    return 0;
}

Tail recursion is a form of recursion where the recursive call is the last operation in the function. This allows compilers to optimize the calls, turning them into iterative loops to prevent stack overflow.

Why is tail recursion important? It enhances performance and avoids stack overflows, which is especially useful for deeply recursive functions.

Let's dive into an example to understand tail recursion better:

#include <iostream>

// Tail Recursion Example
int tailFactorial(int n, int a = 1) {
    if (n == 0) return a;
    return tailFactorial(n - 1, n * a);
}

This function is a tail-recursive function, where the recursive call is the last operation in the function. It uses an additional parameter (a) to accumulate the multiplication result as the recursion progresses.

In summary, while both factorial and tailFactorial functions have the recursive call as the last syntactic operation, factorial performs an operation (n * ...) after the call returns, while tailFactorial carries the accumulator forward and makes the recursive call the absolute last operation, enabling tail call optimization.

Let's take another example of a regular recursive function and transform it into a tail-recursive function.

Here’s a classic example of a regular recursive function to calculate the nth Fibonacci number:

#include <iostream>

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

int main() {
    int number = 5;
    std::cout << "Fibonacci of " << number << " is " << fibonacci(number) << '\n'; // Output: Fibonacci of 5 is 5
    return 0;
}

To transform this function into a tail-recursive function, we use additional parameters to carry forward the state of the computation. Here’s how the tail-recursive version looks:

#include <iostream>

int tailFibonacci(int n, int a = 0, int b = 1) {
    if (n == 0) return a; // Base case
    if (n == 1) return b; // Base case
    return tailFibonacci(n - 1, b, a + b); // Tail recursive call
}

int main() {
    int number = 5;
    std::cout << "Fibonacci of " << number << " is " << tailFibonacci(number) << '\n'; // Output: Fibonacci of 5 is 5
    return 0;
}

In the tail-recursive tailFibonacci function, the recursive call tailFibonacci(n - 1, b, a + b) is the last operation executed, using the additional parameters a and b to carry forward the state of the computation. This transformation enables tail call optimization.