Recursion in C++

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. In C++, recursion is used to break down complex problems into smaller, more manageable "sub-problems." Every recursive function must have a Base Case (to stop the execution) and a Recursive Case (to continue the process).

1. C++ Example: Factorial Calculation

A classic example of recursion is calculating the factorial of a number ($n!$). The logic is $n! = n \times (n-1)!$, with the base case being $0! = 1$.

2. How Recursion Works (The Stack)

When a function calls itself, the current execution state is pushed onto the System Stack. If a base case is never reached, the stack grows until it runs out of memory, resulting in a Stack Overflow error.

  • Activation Record: Each call creates a new record in memory containing local variables and the return address.
  • Winding: The process of calling the function repeatedly.
  • Unwinding: The process of returning results back through the chain once the base case is met.

3. Complexity Breakdown

Metric Factorial Case Note
Time Complexity$O(n)$$n$ calls are made for input $n$.
Space Complexity$O(n)$Due to the function call stack depth.

Knowledge Check

1. What happens if a recursive function lacks a base case?
A) Infinite Loop | B) Stack Overflow | C) It returns 0

2. Which of these is a recursive data structure?
A) Array | B) Linked List / Tree | C) Integer

3. Recursion is generally ____ than iteration in terms of memory.
A) More Efficient | B) Less Efficient | C) Equal