Recursion in C++ Explained: Base Cases, Call Stack and Recursive Functions

Recursion Foundation and Call Flow

Recursion is a problem-solving technique in which a function calls itself with a smaller version of the original problem. Each call handles one part of the work and delegates the remaining part to another call of the same function.

A recursive solution usually has two complementary ideas:

• A condition that identifies the smallest problem and stops further calls.

• A recursive step that reduces the current problem toward that stopping condition.

Understanding recursion requires more than reading the final code. It is important to follow how calls are created, how each call pauses, what information is preserved, and how execution resumes when the deepest call returns.

What Is a Recursive Function?

A recursive function is a function that directly or indirectly calls itself. The following function calls itself directly:

This function has no stopping condition. Every call creates another call, which creates another call, and the process continues until the program exhausts the available call-stack memory.

The statement after repeat() is never reached under normal execution because the recursive call never finishes.

Every Call Has Its Own Local State

Each invocation of a function receives its own local variables, parameters, and execution position. If a recursive function declares int value = 2;, every active invocation has a separate value.

Changing a local variable in one invocation does not automatically change the corresponding local variable in another invocation. The calls execute the same function definition, but they occupy separate call frames.

The Call Stack

Function calls are managed using the call stack. Whenever a function is called, a new stack frame is created. A frame contains the information required to continue that particular call later.

A recursive call frame generally preserves:

• The function's parameter values.

• Its local variables.

• The position from which the next function was called.

• The location where execution must resume after that call returns.

• Other implementation-specific bookkeeping information.

If main() calls a recursive function, and that function calls itself repeatedly, the stack grows conceptually as follows:

• main() calls function invocation 1.

• Invocation 1 pauses and calls invocation 2.

• Invocation 2 pauses and calls invocation 3.

• Invocation 3 pauses and calls invocation 4.

• The process continues until a call returns or the stack runs out of space.

Infinite Recursion and Stack Overflow

The call stack has limited memory. If recursion continues without reaching a stopping condition, stack frames accumulate until no more frames can be created. This generally results in a stack overflow and abnormal program termination.

The exact number of calls that fit on the stack is not fixed. It depends on the system, compiler, program configuration, and amount of information stored in each frame.

Infinite recursion is therefore not an endless process in practice. It eventually fails because the program has finite memory.

The Base Case

The base case is the condition under which a recursive function stops calling itself. It represents a problem small enough to solve directly.

Without a reachable base case, a recursive function is unsafe. A base case alone is also insufficient if recursive calls do not move toward it.

Example: Print a Name Five Times

To print Raj five times recursively, the function can receive the number of repetitions still required.

• When n is positive, print the name once.

• Call the function with n - 1.

• When n reaches zero, stop.

Call Flow

The calls move downward as follows:

• printName(5) prints Raj and calls printName(4).

• printName(4) prints Raj and calls printName(3).

• printName(3) prints Raj and calls printName(2).

• printName(2) prints Raj and calls printName(1).

• printName(1) prints Raj and calls printName(0).

• printName(0) reaches the base case and returns immediately.

After the base case returns, the suspended calls finish in reverse order:

• The invocation with n = 1 completes.

• The invocation with n = 2 completes.

• The invocation with n = 3 completes.

• The invocation with n = 4 completes.

• The invocation with n = 5 completes.

• Execution returns to main(), which prints Done.

This illustrates the two-directional nature of recursion: calls first move toward the base case, and then control returns through the suspended calls.

Three Requirements of Safe Recursion

A well-designed recursive solution needs three elements.

1. Base Case

The base case stops further recursion. In the name-printing example, n == 0 is the base case.

2. Recursive Case

The recursive case calls the same function on a related subproblem. The recursive call is printName(n - 1).

3. Progress Toward the Base Case

Every recursive call must make measurable progress toward termination. Reducing n by one ensures that a non-negative starting value eventually reaches zero.

If the function called printName(n) instead of printName(n - 1), the base case would never be reached for a positive starting value.

Work Before and After a Recursive Call

Statements before the recursive call execute while the call stack is growing. Statements after the recursive call execute while the stack is unwinding.

This placement determines the order in which results are produced and leads to the distinction between tail-style and head-style recursive patterns.

Tail Recursion

A function follows a tail-recursive form when the recursive call is its final operation. There is no remaining work after that call returns.

The name-printing function is tail recursive because printName(n - 1) is the final operation in the function.

C++ does not guarantee that tail-recursive calls will be optimized into constant-stack loops. Even tail-recursive C++ code should therefore be treated as potentially consuming one stack frame per call.

Problem: Print Integers from 1 to N

The first approach carries both the current number current and the final number n.

• Begin with current = 1.

• Print the current number.

• Call the function with current + 1.

• Stop when current becomes greater than n.

Dry Run for N = 3

• printIncreasing(1, 3) prints 1 and calls printIncreasing(2, 3).

• printIncreasing(2, 3) prints 2 and calls printIncreasing(3, 3).

• printIncreasing(3, 3) prints 3 and calls printIncreasing(4, 3).

• printIncreasing(4, 3) reaches the base case because 4 > 3.

The output is:

1 2 3

All printing occurs before the recursive calls. The recursive call is the final operation, so this follows a tail-recursive pattern.

Head Recursion

In a head-recursive pattern, the function makes the recursive call before performing its main work. The work is delayed until deeper calls return.

This delay makes it possible to produce values in the reverse order of the calls.

Printing 1 to N Without an Extra Current Parameter

If the function receives only n, it can first solve the smaller problem of printing 1 through n - 1. It then prints n while the call stack unwinds.

Call Phase

• printIncreasing(3) calls printIncreasing(2).

• printIncreasing(2) calls printIncreasing(1).

• printIncreasing(1) calls printIncreasing(0).

• printIncreasing(0) reaches the base case and returns.

Return Phase

• The call with n = 1 resumes and prints 1.

• The call with n = 2 resumes and prints 2.

• The call with n = 3 resumes and prints 3.

The stack preserves a different n value in each frame. That is why every resumed call prints its own value.

Problem: Print Integers from N to 1

To print in decreasing order, perform the printing before the recursive call:

For n = 3, the output is:

3 2 1

This is a tail-recursive form because no work remains after printDecreasing(n - 1) returns.

Parameterized Recursion

Parameterized recursion carries the developing answer as one of the function parameters. The parameter acts as an accumulator and is updated before each recursive call.

Problem: Sum from 1 to N Using an Accumulator

For n = 3, the required sum is:

3 + 2 + 1 = 6

The accumulator evolves as follows:

• Start with sum = 0.

• Add 3, making the sum 3.

• Add 2, making the sum 5.

• Add 1, making the sum 6.

• When n reaches zero, print the accumulated answer.

Call Flow

• printSum(3, 0) calls printSum(2, 3).

• printSum(2, 3) calls printSum(1, 5).

• printSum(1, 5) calls printSum(0, 6).

• printSum(0, 6) prints 6 and returns.

The updated sum is passed into the next frame. Each frame still has its own parameter values, but the next call receives the newly calculated accumulator.

Functional Recursion

In functional recursion, the function returns a value. A call depends on the answer returned by a smaller recursive call and combines that answer with its own contribution.

For the sum from 1 to n, define:

sum(n) = n + sum(n - 1)

The smallest problem is:

sum(0) = 0

Problem: Return the Sum from 1 to N

Breaking the Problem Down

For n = 4, the calls expand as follows:

• recursiveSum(4) = 4 + recursiveSum(3)

• recursiveSum(3) = 3 + recursiveSum(2)

• recursiveSum(2) = 2 + recursiveSum(1)

• recursiveSum(1) = 1 + recursiveSum(0)

• recursiveSum(0) = 0

Returning the Answers

Once the base case returns, the results move back through the pending expressions:

• recursiveSum(0) returns 0.

• recursiveSum(1) returns 1 + 0 = 1.

• recursiveSum(2) returns 2 + 1 = 3.

• recursiveSum(3) returns 3 + 3 = 6.

• recursiveSum(4) returns 4 + 6 = 10.

The value 10 finally reaches main().

Visualizing a Recursion Tree

For simple functions, a complete line-by-line dry run is manageable. For larger functions, a recursion tree or call diagram provides a more compact view.

The sum example can be represented as a chain:

• sum(4) = 4 + sum(3)

• sum(3) = 3 + sum(2)

• sum(2) = 2 + sum(1)

• sum(1) = 1 + sum(0)

• sum(0) = 0

The downward path represents recursive calls. The upward path represents returned answers. More advanced recursive functions may create multiple calls per invocation, producing an actual branching tree.

Choosing the Correct Base-Case Value

A base case must return a value that works correctly with the operation used while unwinding.

• For addition, zero is the identity value because x + 0 = x.

• For multiplication, one is the identity value because x * 1 = x.

Returning the wrong identity can invalidate every result built above it.

Problem: Calculate N Factorial

The factorial of a non-negative integer is the product of all positive integers from that number down to one:

n! = n * (n - 1) * (n - 2) * ... * 1

For example:

• 4! = 4 * 3 * 2 * 1 = 24

• 3! = 3 * 2 * 1 = 6

• 0! = 1

The recursive relationship is:

factorial(n) = n * factorial(n - 1)

The base case must return 1. Returning zero would make every multiplication above it equal zero.

Call Expansion for 4 Factorial

• factorial(4) = 4 * factorial(3)

• factorial(3) = 3 * factorial(2)

• factorial(2) = 2 * factorial(1)

• factorial(1) = 1 * factorial(0)

• factorial(0) = 1

Return Flow

• factorial(0) returns 1.

• factorial(1) returns 1 * 1 = 1.

• factorial(2) returns 2 * 1 = 2.

• factorial(3) returns 3 * 2 = 6.

• factorial(4) returns 4 * 6 = 24.

Time and Space Complexity

Printing Problems

Printing a name n times or printing the integers from 1 to n performs one useful operation per recursive call.

• Time complexity: O(n).

• Call-stack space: O(n).

Recursive Sum

The recursive sum makes one call for every value from n to zero.

• Time complexity: O(n).

• Call-stack space: O(n).

Factorial

The factorial function also makes one recursive call for each value from n to zero.

• Time complexity: O(n).

• Call-stack space: O(n).

The call-stack space is not constant because every unfinished invocation remains active until the deeper call returns.

Common Recursion Mistakes

• Writing no base case.

• Writing a base case that can never be reached.

• Calling the function with an unchanged or larger problem when reduction is required.

• Performing work on the wrong side of the recursive call and producing reversed output.

• Returning zero as the base value of a multiplication recurrence.

• Forgetting to return the value produced by a recursive call.

• Assuming that all recursive calls share the same local variables.

• Ignoring call-stack limits for very large inputs.

• Using recursion where a simple loop would be clearer and safer without any structural benefit.

How to Design a Recursive Solution

• Define exactly what the function is responsible for solving.

• Express the original problem in terms of a smaller instance of the same problem.

• Identify the smallest directly solvable input.

• Write the base case for that input.

• Ensure every recursive call moves toward the base case.

• Decide whether work belongs before the call, after the call, or in both places.

• Determine whether the answer should be accumulated through parameters or returned through calls.

• Choose a base-case return value compatible with the combining operation.

• Dry-run both the downward call phase and the upward return phase.

Key Takeaways

• Recursion solves a problem by calling the same function on a smaller version of that problem.

• Each invocation has its own parameters, local variables, and execution position.

• The call stack preserves unfinished function calls until deeper calls return.

• Unbounded recursion eventually causes stack overflow.

• A safe recursive function needs a reachable base case and consistent progress toward it.

• Work before a recursive call happens while the stack grows.

• Work after a recursive call happens while the stack unwinds.

• Tail recursion places the recursive call at the end of the function.

• Head-style recursion performs important work after the recursive call returns.

• Parameterized recursion carries the answer through function parameters.

• Functional recursion constructs the answer from values returned by smaller calls.

• For addition, the natural identity is zero; for multiplication, it is one.

• A recursion tree or call chain helps visualize complex call and return flow.