Understanding the Components of Single-Branch Recursion in C++

Welcome. This is the first lesson in a short, exam-focused recursion course. Since you already write ordinary C++ functions and can trace loops, the central new idea is that a function may solve a problem by calling itself on a smaller instance of the same problem.

In this module, you will first learn to recognize the structure of a recursive function; the next lesson will focus on tracing its calls and returned values. By the end of this lesson, you should be able to inspect a simple C++ function and identify its purpose, base case, recursive case, and the argument change that makes termination inevitable.

---

The essential shape of recursion

A recursive function is a function that invokes itself. That fact alone does not make a function correct. For a recursive function to work safely, it needs a complete plan:

1. A meaningful task for the function to perform.
2. A smallest version of that task that can be solved directly.
3. A recursive call that handles a smaller version of the task.
4. A change that reliably brings the input to the smallest version.

The Neso Academy video introduces this vocabulary and then applies it to factorial, the standard first recursion example.

A concise rule from the resource is that every sound recursive algorithm has three requirements: a base case, a change of state toward that base case, and a recursive call.

A common misconception is: “Recursion means a function keeps calling itself.” More precisely:

Recursion means a function calls itself on a version of the problem that is closer to a directly solvable case.

The phrase closer to is the part that prevents infinite recursion.

---

A four-part reading method for exam code

When an exam gives you a recursive function, do not begin by trying to trace every call. First label these four elements.

Element	What to identify
Purpose	What does one call of the function promise to return or print?
Base case	Which condition solves the smallest valid problem without another self-call?
Recursive case	Which branch calls the function again to solve the same kind of problem?
Argument change	What differs in that self-call, and why does it move toward the base case?

Consider factorial:

int factorial(int n) {
    if (n == 0) {
        return 1;
    }

    return n * factorial(n - 1);
}

Assume the function’s valid input is $n\ge 0$.

1. Purpose

The purpose is not simply “to call itself.” It is:

factorial(n) returns $n!$, the product of the integers from $1$ through $n$.

For this definition, $0!=1$. For positive values of $n$,

$$n!=n\cdot (n-1)!$$

That equation explains the recursive return statement. The function needs the factorial of a smaller number, then multiplies by the current $n$.

2. Base case

if (n == 0) {
    return 1;
}

This is the base case because:

• it handles the smallest intended input, $0$;
• it returns an answer immediately;
• it does not call factorial again.

A base case is not defined by the keyword if. It is defined by the absence of a further recursive call and by directly solving a valid smallest case.

3. Recursive case

return n * factorial(n - 1);

This is the recursive case because it invokes factorial from inside factorial.

It also preserves the function’s purpose. factorial(n - 1) is still asking for a factorial; it is just asking for one with a smaller argument. The current call can finish once that smaller result is available.

4. Argument change and termination

The argument changes from $n$ to $n-1$.

For the allowed inputs $n\ge 0$, every recursive call is made only when $n>0$. Therefore the argument stays nonnegative and becomes smaller each time:

$$n,n-1,n-2,\dots ,0$$

Eventually it must reach $0$, where the base case stops the recursion.

This is a small but powerful proof of termination:

• Base case reachable? Yes, $n=0$.
• Recursive argument changes? Yes, it becomes $n-1$.
• Does the change reduce the distance to the base case? Yes, by exactly one.
• Does the input remain valid before the base case? Yes, because the recursive branch begins only when $n>0$.

---

Seeing the smaller-problem idea

The following factorial diagram uses a slightly different but equally valid convention: it stops at $n=1$, assuming that the input begins at $1$ or greater. Notice the two phases: calls continue until the base case, then values return back through the waiting calls.

Both of these factorial base cases can work:

if (n == 0) return 1;

if (n == 1) return 1;

But the valid-input assumption must match the choice:

• With base case n == 0, allow $n\ge 0$.
• With base case n == 1, require $n\ge 1$.

This matters in exam questions. A base case is useful only if the recursive calls can actually reach it for every input the problem allows.

For example, this version is unsafe if 0 is allowed:

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

    return n * factorial(n - 1);
}

If called with factorial(0), it continues with $-1$, then $-2$, and so on. Although a base case exists in the code, it is never reached for that input.

---

Recursive functions that print rather than return

Not every recursive function calculates a numerical value. Some perform an action, such as printing.

void countdown(int n) {
    if (n == 0) {
        cout << "Blastoff!\n";
        return;
    }

    cout << n << '\n';
    countdown(n - 1);
}

Apply the same four-part method:

Element	Identification
Purpose	Print the numbers from n down to 1, then print Blastoff!
Base case	n == 0; it prints the final message and makes no recursive call
Recursive case	The statements after the base-case block, especially countdown(n - 1)
Argument change	n becomes n - 1
Termination condition	For a starting value $n\ge 0$, repeated subtraction reaches $0$

The return; is optional here because the else is not written explicitly; without it, return; prevents execution from falling through into the recursive call after Blastoff! has printed.

This is still single-branch recursion: every non-base call makes at most one recursive call. The function may have an if and an else, but there is only one continuing branch of recursion.

---

The termination test: follow the distance, not just the change

An argument changing is not enough. It has to change in the correct direction for the allowed inputs.

This function has a base case and a recursive call:

int badCount(int n) {
    if (n == 0) {
        return 0;
    }

    return 1 + badCount(n);
}

But it does not terminate when called with a nonzero value. The recursive call uses badCount(n), so the argument does not change at all. It remains the same forever.

Here is another faulty version:

int alsoBad(int n) {
    if (n == 0) {
        return 0;
    }

    return 1 + alsoBad(n + 1);
}

For a positive starting value, n + 1 moves farther away from the base case at $0$. The function will keep creating new calls until the program exhausts its call stack, typically causing a stack overflow and program crash.

The general exam rule is:

Do not merely check whether the argument changes. Check whether every recursive call reduces a well-defined distance to a reachable base case.

Often the distance is simply the number itself:

• Base case: n == 0
• Recursive call: f(n - 1)
• Valid domain: $n\ge 0$

But it does not always have to be decreasing numerically. Suppose a function’s base case is n == 5 and its valid inputs are $n\le 5$. A recursive call using n + 1 can be correct, because it reduces the distance from n to $5$. The direction only makes sense relative to the base case and the allowed inputs.

---

An exam-speed recursion audit

When you see a simple recursive function, use this short routine before writing or tracing code:

1. State the contract.
   Write one sentence: “This function returns…” or “This function prints…”

2. Circle the self-call.
   A function is recursive only where it invokes its own name.

3. Mark the stopping branch.
   Find the branch with no self-call. State its condition and direct result.

4. Compare the arguments.
   Write the original parameter and the recursive-call parameter side by side, such as n and n - 1.

5. Check the input domain.
   Ask whether the stated or implied inputs will reach the base condition.

For factorial, your complete identification could be written compactly as:

Purpose: return $n!$ for $n\ge 0$.
Base case: when n == 0, return 1.
Recursive case: return n * factorial(n - 1).
Progress: n decreases by one on every recursive call, so it eventually reaches zero.

That is exactly the type of explanation that supports correct recursive code later in the course.

---

Key takeaways

A correct simple recursive C++ function needs more than a self-call:

• The purpose states what one function call is meant to accomplish.
• The base case directly handles a smallest valid input and makes no recursive call.
• The recursive case calls the same function for a smaller or otherwise closer version of the same problem.
• The argument change must guarantee that the base case is eventually reached for every allowed input.
• A base case that cannot be reached is effectively no base case at all.

Next, you will hand-trace recursive execution: the order in which calls are made, the moment the base case activates, and the reverse order in which return values are completed.