YOUR C LEARNING COMPANION

Find your next idea.

Learning path
C foundationsChapter 14 of 73

Recursion: following separate calls

Understand stopping cases, progress, separate local state, returned results, and the limits of recursive designs.

5 min readDevelopingC17 baseline
Offline reading
In this chapter9 sections

A function can solve a problem by asking another call to solve a smaller part. If the new call uses the same function, we call the design recursion. The central idea is a sequence of separate calls, each with its own work still to finish.

1. Start with a smaller question

To add the integers from one through three, we can say: three plus the sum from one through two. That smaller sum is two plus the sum through one. Eventually we reach zero, where there is no work left to add. Each answer lets an earlier call finish.

The method needs two parts. The base case answers a question directly. The recursive case reduces the remaining problem. Here zero is the base case, and subtracting one makes progress toward it. Writing a self-call without that reasoning does not establish termination.

2. Keep the first example bounded

This complete C17 example deliberately accepts only values zero through ten. The largest sum is 55, so every intermediate addition fits even the minimum standard range of unsigned int. The assertions document and check that demonstration contract in this test build. They are not a replacement for validating untrusted input.

Complete C17 program
#include <assert.h>

/* Contract: n is at most 10. */
static unsigned triangle(unsigned n)
{
    assert(n <= 10U);
    if (n == 0U) return 0U;
    return n + triangle(n - 1U);
}

static unsigned triangle_loop(unsigned n)
{
    assert(n <= 10U);
    unsigned total = 0U;
    for (unsigned i = 1U; i <= n; ++i) total += i;
    return total;
}

int main(void)
{
    for (unsigned n = 0U; n <= 10U; ++n) {
        assert(triangle(n) == triangle_loop(n));
        assert(triangle(n) == n * (n + 1U) / 2U);
    }
    return 0;
}

3. Read calls downward and answers upward

CallCalculation waiting for a resultEventually returns
triangle(3)3 + triangle(2)6
triangle(2)2 + triangle(1)3
triangle(1)1 + triangle(0)1
triangle(0)—0

For triangle(3), the first call cannot finish its addition until triangle(2) returns. That call waits for triangle(1), which waits for triangle(0). Zero returns first. Then the pending additions finish with one, three, and six. Returning from one call resumes its caller; it does not restart the whole program.

Explore with a visual model

Follow recursive calls and returns

VISUAL MODEL

Choose a small input and follow triangle(n). See which call waits and which result lets its caller continue.

triangle adds the unsigned integers from 1 through n. Each invocation has its own n parameter.

  1. if (n == 0U) return 0U;
  2. return n + triangle(n - 1U);
Calls still in progress

No call is in progress.

Final resultNo result returned yet

Ready to call triangle(3). No call has started yet.

The input is limited to 0–5, and every sum fits unsigned int. This follows source-level calls; storage layout and call optimisation are implementation details.

Read the complete trace
  1. Ready to call triangle(3). No call has started yet.
  2. Enter triangle(3). This call has its own parameter value 3.
  3. Enter triangle(2). This call has its own parameter value 2.
  4. Enter triangle(1). This call has its own parameter value 1.
  5. Enter triangle(0). This call has its own parameter value 0.
  6. triangle(0) reaches the stopping case and returns 0. No smaller call is needed.
  7. triangle(0) returned 0. Its caller triangle(1) can now compute 1 + 0 and return 1.
  8. triangle(1) returned 1. Its caller triangle(2) can now compute 2 + 1 and return 3.
  9. triangle(2) returned 3. Its caller triangle(3) can now compute 3 + 3 and return 6.
  10. All calls have finished. triangle(3) returned 6 to the original caller.

4. Each call has separate ordinary local state

Every invocation receives its own parameter value. Deeper calls do not overwrite the caller’s n. Ordinary automatic local objects also have separate instances for recursive entries. A static local object would instead be shared across calls under its storage-duration rules. That difference matters when adding a counter or cached result.

A stack of unfinished worksheets is a useful mental model: finish the newest question, then use its answer in the previous one. Real implementations commonly use a call stack. C does not require this exact physical arrangement, a fixed size per call, or unlimited recursion depth.

5. Choose recursion when the structure helps

Recursion fits problems with smaller subproblems, such as walking a tree. A simple linear sum is often clearer as a loop; both forms appear above so their state can be compared. Recursive functions can also call one another indirectly. The same need for progress, valid inputs, and a depth policy remains.

A stopping case does not by itself prevent arithmetic overflow or excessive work. A recursive Fibonacci demonstration can repeat the same subproblems many times. A tail-position call is not a portable promise that a compiler will remove call storage. Explain correctness, resource use, and implementation observations separately.

Think it through

If a function calls itself with the same unchanged input, is a base-case branch enough to guarantee it finishes?

Read the explanation

No. The calls must reach the stopping case or another justified exit. With an unchanged non-base input, the same unfinished problem is repeated.

Primary references and further reading

Before you move on

  • A recursive design needs a stopping case and a justified reduction toward it.
  • Each invocation has separate parameters and ordinary automatic local instances.
  • Finite arithmetic, call depth, and repeated work still need explicit limits.
Keep these ideas separate
Calling downward / Returning upward
Smaller calls start before their waiting callers can use the returned results to finish.
Explain it in your own words

Why does triangle(3) need triangle(2), and which result allows the first waiting addition to finish?

Optional: say it aloud or keep a note. You can continue whenever you are ready.

Check your understanding

Optional. Answers are not saved or sent, and reading stays unrestricted.

Does merely writing a base-case branch guarantee recursive calls will finish?
Read the explanation for every choice
  1. Yes, the presence of the branch forces every call to reach it.

    A branch that is never reached cannot stop the recursion.

  2. Yes, C guarantees unlimited call depth.

    Resource use and call depth are not unlimited portable guarantees.

  3. No. The calls need justified progress toward a stopping condition and resource limits.

    ✓ Correct reasoning. A sound argument also considers valid inputs, arithmetic, depth, and repeated work.

C17

Ready for the next idea?

Mark this chapter as read whenever you feel ready.

CHAPTER 14 / 73

In this chapter

Recursion: following separate calls

Search all 73 chapters in both languages.EN + HG

Try “pointer”, “why int”, or “undefined behavior”.

Concepts connect. Follow your curiosity.↑ ↓ to explore · Enter to open
MAKE YOURSELF COMFORTABLE

Your reading space

Appearance

A clear canvas with balanced contrast.

Text size

100%
AA

Reading tools

Your data stays in this browser

Export a backup before changing browsers or replacing an older version of the reader.

YOUR PERSONAL MARGINS

My notebook

Saved on this device
A LITTLE CLARITY

The glossary

A starting meaning, then a chapter to go deeper.

A QUICK DEFINITION

A little clarity

Read the full explanation →

A thought worth keeping