C++ Recursion

C++ Recursion: Functions Calling Themselves

Recursion is a powerful programming technique where a function calls itself to solve a smaller instance of the same problem.

It can be a bit tricky to wrap your head around at first, but recursion is fantastic for breaking down complex mathematical problems, navigating tree structures, and sorting data.

1. How Recursion Works

Think of recursion like looking into two mirrors facing each other—the reflection goes on infinitely. However, in programming, if a function calls itself infinitely, your program will crash with a "Stack Overflow" error!

To prevent this, every recursive function must have two critical parts:

1. The Base Case: A condition that stops the recursion.
2. The Recursive Call: The part where the function calls itself with a modified parameter, moving closer to the base case.

2. Example: Calculating the Sum of Numbers

Let's write a function that calculates the sum of all numbers from 1 to k. For example, if k = 5, the sum is 5 + 4 + 3 + 2 + 1 = 15.

#include <iostream>
using namespace std;

int sum(int k) {
  // Base Case: Stop when k is 0
  if (k > 0) {
    // Recursive Call: k + sum of everything below k
    return k + sum(k - 1); 
  } else {
    return 0;
  }
}
int main() {
  int result = sum(5);
  cout << "The sum is: " << result << "\n";
  return 0;
}

Breaking Down the Execution:

When you call sum(5), here is what happens behind the scenes:

• sum(5) returns 5 + sum(4)
• sum(4) returns 4 + sum(3)
• sum(3) returns 3 + sum(2)
• sum(2) returns 2 + sum(1)
• sum(1) returns 1 + sum(0)
• sum(0) hits the base case and returns 0.

Then, it collapses back up: 1 + 0 = 1, 2 + 1 = 3, 3 + 3 = 6, 4 + 6 = 10, 5 + 10 = 15!

3. When to Use Recursion

• Pros: Makes code look clean, elegant, and shorter, especially for problems like traversing a file system or calculating factorials.
• Cons: Can be slow and use a lot of memory. If the base case is not defined correctly, it causes infinite loops.

If a problem can be solved easily with a standard for or while loop, it is generally better to use a loop instead of recursion to save memory.