Recursion

A recursive function is a function that invokes itself during its execution. This powerful programming technique allows complex problems to be broken down into simpler, similar subproblems.

Understanding Recursion Through Examples

Let's start with a simple example that demonstrates how recursion works:

#include <iostream>

void displayStars(int count)
{
    std::cout << '*';
    displayStars(count - 1); // function calls itself
}

int main()
{
    displayStars(5);

    return 0;
}

When displayStars(5) is called, it prints a star and then calls displayStars(4). This process continues indefinitely because there's no condition to stop the recursion. Eventually, the program will crash due to stack overflow when the call stack runs out of memory.

The Critical Element: Termination Conditions

Every recursive function must include a termination condition (also called a base case) - a condition that stops the function from calling itself. Without this, the function recurses infinitely until the program crashes.

Here's the corrected version:

#include <iostream>

void displayStars(int count)
{
    if (count <= 0) // termination condition
        return;

    std::cout << '*';
    displayStars(count - 1);
}

int main()
{
    displayStars(5);
    std::cout << '\n';

    return 0;
}

Output:

*****

Now when count reaches 0, the function returns instead of recursing further, preventing the infinite loop.

Visualizing the Call Stack

Let's examine a function that shows both the "winding" and "unwinding" of the call stack:

#include <iostream>

void traverse(int depth)
{
    std::cout << "Going down: " << depth << '\n';

    if (depth > 1)
        traverse(depth - 1);

    std::cout << "Coming back up: " << depth << '\n';
}

int main()
{
    traverse(4);
    return 0;
}

Output:

Going down: 4
Going down: 3
Going down: 2
Going down: 1
Coming back up: 1
Coming back up: 2
Coming back up: 3
Coming back up: 4

The output before the recursive call happens in forward order (as we descend into each recursive call). The output after the recursive call happens in reverse order (as each function returns and is popped off the stack).

Computing Values Recursively

Recursive functions become more useful when they compute and return values. Here's a function that calculates the product of all integers from 1 to a given number:

#include <iostream>

// Calculate the product of integers from 1 to n
int product(int n)
{
    if (n <= 0)
        return 0; // handle invalid input
    if (n == 1)
        return 1; // base case

    return n * product(n - 1); // recursive case
}

int main()
{
    std::cout << "Product of 1 to 5: " << product(5) << '\n';
    return 0;
}

Output:

Product of 1 to 5: 120

Let's trace through product(5):

  • product(5) returns 5 * product(4)
  • product(4) returns 4 * product(3)
  • product(3) returns 3 * product(2)
  • product(2) returns 2 * product(1)
  • product(1) returns 1 (base case)

Now unwinding:

  • product(2) returns 2 * 1 = 2
  • product(3) returns 3 * 2 = 6
  • product(4) returns 4 * 6 = 24
  • product(5) returns 5 * 24 = 120

The Power Series Example

Here's a more practical example calculating power series:

#include <iostream>

// Calculate x raised to the power of n
int power(int base, int exponent)
{
    if (exponent == 0)
        return 1; // anything to power 0 is 1
    if (exponent == 1)
        return base; // base case

    return base * power(base, exponent - 1);
}

int main()
{
    std::cout << "2^8 = " << power(2, 8) << '\n';
    std::cout << "3^4 = " << power(3, 4) << '\n';

    return 0;
}

Output:

2^8 = 256
3^4 = 81

Triangle Numbers

Triangle numbers form a sequence where each number equals the sum of all positive integers up to that position: 1, 3, 6, 10, 15, 21, ...

The mathematical definition:

  • T(1) = 1
  • T(n) = n + T(n-1) for n > 1
#include <iostream>

int triangleNumber(int n)
{
    if (n <= 0)
        return 0;
    if (n == 1)
        return 1; // base case

    return n + triangleNumber(n - 1);
}

int main()
{
    for (int i{1}; i <= 7; ++i)
        std::cout << triangleNumber(i) << ' ';
    std::cout << '\n';

    return 0;
}

Output:

1 3 6 10 15 21 28

Memoization for Efficiency

Some recursive functions make redundant calculations. Consider calculating triangle numbers - without optimization, triangleNumber(5) recalculates triangleNumber(4), triangleNumber(3), etc., every time it's called.

Memoization caches previously calculated results:

#include <iostream>
#include <vector>

int triangleNumber(int n)
{
    static std::vector<int> cache{0, 1}; // start with T(0)=0, T(1)=1

    if (n < static_cast<int>(cache.size()))
        return cache[n]; // return cached value

    // Calculate and cache new value
    int result{n + triangleNumber(n - 1)};
    cache.push_back(result);
    return result;
}

int main()
{
    for (int i{1}; i <= 7; ++i)
        std::cout << triangleNumber(i) << ' ';
    std::cout << '\n';

    return 0;
}

This version only calculates each triangle number once, dramatically improving performance for repeated calls.

Recursion vs Iteration

Any recursive algorithm can be written iteratively (using loops). Consider the triangle number calculation:

Recursive version:

int triangleNumber(int n)
{
    if (n <= 1)
        return n;
    return n + triangleNumber(n - 1);
}

Iterative version:

int triangleNumber(int n)
{
    int total{0};
    for (int i{1}; i <= n; ++i)
        total += i;
    return total;
}

The iterative version is more efficient (no function call overhead) and won't risk stack overflow. However, recursive solutions can be clearer and more intuitive for problems that naturally divide into similar subproblems.

When to Use Recursion

Recursion is a good choice when:

  • The problem naturally divides into similar subproblems
  • The recursive solution is significantly simpler and clearer
  • Recursion depth is limited and predictable
  • The code section is not performance-critical
  • The iterative solution would require manually managing a stack

Best practice

Generally favor iteration over recursion, except when recursion really makes sense.

Quiz

Question 1: Write a recursive function that calculates the factorial of a number (n! = n × (n-1) × (n-2) × ... × 1). Test with the first 8 factorials.

Show Solution 
#include <iostream>

int factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * factorial(n - 1);
}

int main()
{
    for (int i{0}; i < 8; ++i)
        std::cout << factorial(i) << '\n';

    return 0;
}

Question 2: Write a recursive function that calculates the sum of the digits in a positive integer (e.g., 8642 = 8 + 6 + 4 + 2 = 20). Print the result for input 74518 (which equals 25).

Show Solution 
#include <iostream>

int sumDigits(int value)
{
    if (value < 10)
        return value;

    return (value % 10) + sumDigits(value / 10);
}

int main()
{
    std::cout << sumDigits(74518) << '\n';
    return 0;
}

Question 3a: Write a program that asks the user for a positive integer, then uses recursion to print its binary representation using the division method.

Hint: The division method repeatedly divides by 2 and tracks remainders. Print after the recursive call to get correct order.

Show Solution 
#include <iostream>

void printBinary(int value)
{
    if (value == 0)
        return;

    printBinary(value / 2);
    std::cout << (value % 2);
}

int main()
{
    int num{};
    std::cout << "Enter a positive integer: ";
    std::cin >> num;

    printBinary(num);
    std::cout << '\n';

    return 0;
}

Question 3b: Update your code to handle negative numbers and zero.

Sample output for -15: 11111111111111111111111111110001

Hint: Convert the signed integer to unsigned to preserve the binary representation while treating it as positive.

Show Solution 
#include <iostream>

void printBinary(unsigned int value)
{
    if (value > 1)
        printBinary(value / 2);

    std::cout << (value % 2);
}

int main()
{
    int num{};
    std::cout << "Enter an integer: ";
    std::cin >> num;

    printBinary(static_cast<unsigned int>(num));
    std::cout << '\n';

    return 0;
}

Summary

Recursive functions: Functions that call themselves during execution. They break complex problems into simpler, similar subproblems.

Termination condition (base case): Essential condition that stops recursion. Without it, the function recurses infinitely until stack overflow crashes the program.

Call stack visualization: During recursion, each function call is "wound" onto the stack. After the base case is reached, calls "unwind" in reverse order as each function returns.

Computing with recursion: Recursive functions can calculate and return values by combining the current value with the result of the recursive call. Examples include factorial, power calculations, and triangle numbers.

Memoization: Optimization technique that caches previously calculated results to avoid redundant computations. Uses a static container to store results indexed by input values.

Recursion vs iteration: Any recursive algorithm can be written iteratively using loops. Iteration is generally more efficient (no function call overhead, no stack overflow risk) but recursion can be clearer for naturally recursive problems.

When to use recursion:

  • Problem naturally divides into similar subproblems
  • Recursive solution is significantly simpler and clearer
  • Recursion depth is limited and predictable
  • Not performance-critical code
  • Iterative solution would require manual stack management

Best practice: Generally favor iteration over recursion except when recursion provides clear advantages in readability or simplicity.

Recursion is a powerful technique for solving problems that have recursive structure, but should be used judiciously considering performance implications and stack depth limitations.