Recursion termination and base case design

Prove that every admitted input reaches a return

A base case is useful only if the recursive steps reach it. In this lesson, you will state the inputs a function accepts, choose a nonnegative whole-number measure of remaining work, and check that every recursive call reduces that measure. You will also check that the function returns before an unsafe expression can be evaluated.

Read Recursion: base case and call stack first. You should already be able to follow separate calls and their returning values. We now focus on choosing stopping conditions and justifying termination for direct recursion with one child call per recursive case. This lesson does not cover all recursive algorithms or establish complete recursion mastery.

Our C11 contract

All code uses C11 and ordinary int values. Each example states its admitted starting inputs. The ranges are deliberately small so all shown arithmetic and results are representable even on a C implementation with the minimum required int range. We assume enough execution resources for these short traces. No claim is made about a safe general recursion depth.

For nonnegative integers, n / 2 is integer division: it discards any fractional part. Thus 13 / 2 is 6, 3 / 2 is 1, and 1 / 2 and 0 / 2 are both 0. A mathematical fraction such as 0.5 never becomes the next int argument in these examples.

An input contract comes before the proof

An admitted input domain is the set of starting inputs for which the function promises the stated behavior. For halve_rounds, admit integers from 0 through 31. It must return the number of integer halvings needed to make the value at most 1; the answer is already 0 at inputs 0 and 1.

#include <stdio.h>

int halve_rounds(int n) {
    if (n <= 1) {
        return 0;
    }
    int rest = halve_rounds(n / 2);
    return 1 + rest;
}

int main(void) {
    printf("%d\n", halve_rounds(13));
    return 0;
}

An input contract is a statement about permitted calls; it is not automatically a run-time check. This function happens to return 0 for a negative input because of n <= 1, but our contract does not define a meaningful halving count for negative starts. Do not extend a promise just because one extra input appears to work.

Also distinguish starting inputs from states reached by recursive calls. A helper must behave correctly on its reachable child inputs, even if they were not listed as starting inputs. For halving, every child remains in 0 through 31. Later, a step of 2 will reach 11 even though starting positions are at most 10.

Worked trace from 13 to 1

The first recursive call gets 13 / 2, which is 6. Write the argument and the waiting operation for every call.

The program prints 3. There are three halving steps and four function invocations, including the initial and base-case calls. Those quantities differ by one for this chain; the returned count is not the number of invocations.

Boundary checks matter: halve_rounds(0) = 0, halve_rounds(1) = 0, halve_rounds(2) = 1, and halve_rounds(3) = 1. The input 31 follows 31 → 15 → 7 → 3 → 1, so its result is 4.

A decreasing nonnegative measure

A termination measure assigns a nonnegative integer to each reachable call state. It need not be a variable stored in the program. Here choose V(n) = n and check these facts:

1. The starting value is in 0 through 31, and each reached argument stays in that range.
2. A call with n <= 1 returns without making a child call.
3. Whenever a child is made, n >= 2, so 0 <= n / 2 < n. The child's measure is strictly smaller.
4. All remaining work in each call is finite and uses defined arithmetic. Here the return adds 1 to a small count.

A nonnegative integer cannot decrease strictly forever. Therefore a chain of recursive calls cannot continue forever; it reaches a returning case, and the finitely many waiting calls can return too. We did not need the measure to become exactly zero: this base case also stops at measure 1.

“Smaller” must be precise. A decreasing integer with no lower bound is insufficient: the mathematical sequence 1, -2, -5, ... keeps decreasing. A nonnegative quantity that stays unchanged is also insufficient. And this whole-number argument does not transfer to arbitrary real numbers: 1, 1/2, 1/4, ... can decrease forever without reaching zero.

A parameter may increase while remaining work decreases

Suppose a position starts at an integer from 0 through 10. Each hop adds 2. We want the number of hops needed to reach or pass 10.

int hops_to_ten(int pos) {
    if (pos >= 10) {
        return 0;
    }
    int rest = hops_to_ten(pos + 2);
    return 1 + rest;
}

For hops_to_ten(7), the positions are 7 → 9 → 11, so the answer is 2. The parameter increases. A suitable measure is the nonnegative distance still needed: V(pos) = max(10 - pos, 0). Here max(a, b) is mathematical notation for the larger value, not a C function you must call.

Reachable positions are in 0 through 11. For a recursive state with pos <= 8, the measure falls by 2. For pos = 9, it falls from 1 to 0 at child position 11. A state at 10 or 11 returns. Hence every child call strictly lowers a nonnegative integer measure, even though pos itself increases. The additions are safe on this small reachable range.

If the guard were only pos == 10, the odd-position path 7 → 9 → 11 → ... would skip the target. It would not later land on 10 in ordinary integer arithmetic. Do not run that defective variant: in C, continued execution may exhaust resources or eventually overflow a signed integer. An overflow does not supply a valid stopping rule or a predictable output.

Equality base cases can be correct when the contract and step guarantee exact arrival. Subtracting 3 from a nonnegative multiple of 3 eventually reaches 0. The same equality guard is not justified for every nonnegative integer. Choose the input domain, recursive step, stopping condition and returned meaning together. Merely changing == to <= or >= is not a universal repair.

Integer halving has two important boundary values

For positive starts, halving with a base case n == 1 can be justified. Once zero is admitted, that proof no longer covers the whole contract: 0 / 2 is still 0, so an unguarded call at zero repeats the same state. It does not make progress toward 1.

In our counting function, the correct base condition is n <= 1 because both 0 and 1 require zero steps. A base condition n == 0 would eventually stop for admitted nonnegative inputs, but would count an unnecessary final halving at 1. For example, it would return 1 at input 1 instead of the specified 0. Termination and the correct answer are separate obligations.

A guard must run before the expression it protects

For the following helper, admit starting integers from 0 through 31. Define its result as 0 at 0 and 1. At each larger state, add the integer quotient 12 / (n - 1) to the child's score after halving.

int guarded_score(int n) {
    if (n <= 1) {
        return 0;
    }
    int part = 12 / (n - 1);
    int rest = guarded_score(n / 2);
    return part + rest;
}

At n = 1, the return executes before the declaration and initialization of part. Thus 12 / (n - 1) is not evaluated; there is no division by zero. At each recursive state n >= 2, the denominator is at least 1, the child is smaller, and the same argument applies again. For guarded_score(6), the contributions are 12 / 5 = 2, then 12 / 2 = 6, followed by the base result 0, giving 8.

Moving int part = 12 / (n - 1); above the guard would evaluate the dangerous expression before the function could return at 1. A later base-case test cannot undo an earlier division by zero. The compiler does not make an invalid C expression safe because a nearby comment says it is a base case.

Here the same halving measure proves that the recursive chain is finite. Separately, we checked the division, subtraction and returned arithmetic. A termination argument alone does not prove that a C execution is defined or that its result matches the intended task.

A precise analogy

Imagine a counter showing how many floor markers remain before an exit. Moving two markers can pass the exit, so “at or beyond the exit” may be the right stopping rule. The current floor number may rise while the remaining distance falls. Once the counter reaches zero, you leave before operating equipment reserved for the unfinished task.

The analogy models a nonnegative whole-number measure and an early return. It does not claim that the program computes the measure, that every step reduces it by one, or that a real machine has unlimited space for waiting calls.

Key box for a termination argument

• State the admitted starting inputs and the required result at the boundaries.
• Check every reachable child state, including a state that passes the target.
• Choose a nonnegative integer measure and show strict decrease on every recursive call.
• Show that the base-case route actually returns without another recursive call.
• Place guards before any expression they must protect, and check defined arithmetic on the recursive route.
• Check result correctness separately: a function can terminate and still return the wrong count.
• A logical proof of finitely many calls does not guarantee success at arbitrary depth on finite hardware. Our short compiled tests check the stated small cases; they do not establish a universal resource bound.

Six original practice questions

Choose exactly one answer per question. Each has four options. Questions with incomplete context are function fragments, not standalone programs; question 3 is a complete program. Analyze invalid alternatives without executing them.

Question 1

For which one of these proposed starting-input sets does every call reach n == 0 by repeated subtraction of 3? Reason from the arguments; do not execute failing inputs. All listed values are mathematical integers represented as int.

int groups_of_three(int n) {
    if (n == 0) {
        return 0;
    }
    int rest = groups_of_three(n - 3);
    return 1 + rest;
}

A. Every integer from 0 through 9

B. Only 0, 3, 6 and 9

C. Only 1, 4 and 7

D. Every integer from -3 through 0

Question 2

For hops_to_ten with starting positions 0 through 10, which is a valid termination argument over all reachable calls?

int hops_to_ten(int pos) {
    if (pos >= 10) {
        return 0;
    }
    int rest = hops_to_ten(pos + 2);
    return 1 + rest;
}

A. max(10 - pos, 0) is a nonnegative integer and strictly decreases whenever a child call is made.

B. pos is a nonnegative integer and strictly decreases whenever a child call is made.

C. Having a return statement somewhere in the function is sufficient, regardless of the recursive step.

D. 10 - pos stays nonnegative at every reachable call, including the call at pos = 11.

Question 3

What does this complete program print?

#include <stdio.h>

int halve_rounds(int n) {
    if (n <= 1) {
        return 0;
    }
    int rest = halve_rounds(n / 2);
    return 1 + rest;
}

int main(void) {
    int a = halve_rounds(0);
    int b = halve_rounds(1);
    int c = halve_rounds(2);
    printf("%d %d %d\n", a, b, c);
    return 0;
}

A. 1 1 2

B. 0 1 2

C. 0 0 1

D. 0 0 0

Question 4

A student replaces the halving base condition with n == 1 and now admits zero. Which statement correctly diagnoses the call faulty_halves(0)? Do not execute it.

/* Reason about this fragment; do not run it at n = 0. */
int faulty_halves(int n) {
    if (n == 1) {
        return 0;
    }
    return 1 + faulty_halves(n / 2);
}

A. The next argument is 0.5, which then rounds up to 1.

B. The next argument remains 0, so the base test stays false and there is no strict progress.

C. Integer division automatically returns from the function when its result is zero.

D. Every recursive call reduces n by exactly 1, so zero soon becomes one.

Question 5

Admit starting integers 0 through 8. The required score is 0 at 0 and 1; for n >= 2 it is 12 / (n - 1) using integer division, plus the score at n / 2. Which implementation is defined and satisfies that rule for every admitted input? Inspect the incorrect options without running them.

A.

int guarded_score(int n) {
    if (n <= 1) { return 0; }
    int part = 12 / (n - 1);
    return part + guarded_score(n / 2);
}

B.

int guarded_score(int n) {
    int part = 12 / (n - 1);
    if (n <= 1) { return 0; }
    return part + guarded_score(n / 2);
}

C.

int guarded_score(int n) {
    if (n == 0) { return 0; }
    int part = 12 / (n - 1);
    return part + guarded_score(n / 2);
}

D.

int guarded_score(int n) {
    if (n <= 2) { return 0; }
    int part = 12 / (n - 1);
    return part + guarded_score(n / 2);
}

Question 6

The halving proof and tests in this lesson cover the stated small input domain. Which conclusion is justified?

A. A few successful runs alone prove that every possible signed int input satisfies the intended contract.

B. A termination measure also proves that every returned value is correct, without checking the recurrence or base values.

C. Once a nonnegative integer measure decreases, a real machine must support arbitrarily many active calls.

D. With the stated domain, defined operations and enough resources for these small cases, the decreasing measure rules out an endless call chain; arbitrary-depth resource safety remains a separate issue.

Answers and option-level feedback

Answer 1 B

• A. Incorrect. This set includes 1, whose next argument is -2; subtracting 3 will not bring that mathematical sequence back to zero.

• B. Correct. These are nonnegative multiples of 3. Each positive state loses 3 while remaining a nonnegative multiple of 3, and then reaches zero.

• C. Incorrect. Each value leaves remainder 1 on division by 3. The paths reach 1, then -2, and miss zero.

• D. Incorrect. Zero returns, but any listed negative start moves farther below zero. One successful member does not justify the whole domain.

Answer 2 A

• A. Correct. The measure falls by 2 for recursive positions at most 8, and from 1 to 0 for the step 9 to 11. Positions at least 10 return.

• B. Incorrect. The child argument is pos + 2, so pos increases. Remaining distance is the decreasing measure.

• C. Incorrect. A return must be reached. An equality-only check at 10 would miss it on the odd-position path.

• D. Incorrect. At position 11 this expression equals -1. Taking the maximum with zero supplies the claimed nonnegative measure on every reachable state.

Answer 3 C

• A. Incorrect. These are invocation counts for the three chains, not the returned numbers of halving steps.

• B. Incorrect. This would count a final step from 1 to 0. The actual guard returns immediately at 1.

• C. Correct. Inputs 0 and 1 need no steps. Input 2 makes the one step 2 to 1 and returns 1.

• D. Incorrect. Input 2 does not satisfy n <= 1. Its call must make and count one recursive step.

Answer 4 B

• A. Incorrect. In C11 integer division, 0 / 2 is 0. No fractional argument or upward rounding occurs.

• B. Correct. The logical argument sequence is 0, 0, 0, and so on. This is not a finite-return case; resource failure or compiler transformations must not be mistaken for reaching the base case.

• C. Incorrect. Computing a zero value does not execute return. The code tests whether n equals 1.

• D. Incorrect. Division by 2 is not subtraction by 1, and subtracting 1 from zero would not approach positive one either.

Answer 5 A

• A. Correct. The guard returns at 0 and 1 before division. At every other reachable state the denominator is positive, and the recursive step follows the specified score rule.

• B. Incorrect. At input 1, part is initialized by division by zero before the guard is tested. A later return does not repair that undefined behavior.

• C. Incorrect. At input 1, the n == 0 test is false and the denominator is zero. The guard omits a necessary boundary case.

• D. Incorrect. This version returns 0 at input 2, but the required result is 12 / 1 + score(1) = 12. It stops safely but returns the wrong score.

Answer 6 D

• A. Incorrect. Tests of selected inputs do not extend the contract to all signed integers. The domain and the reasoning must cover the claim being made.

• B. Incorrect. For example, changing the halving base value from 0 to 7 would preserve termination but corrupt the intended count.

• C. Incorrect. Finitely many required calls may still exceed a real implementation’s available resources. A measure is not a physical memory guarantee.

• D. Correct. The proof supplies logical progress and finite descent under the stated conditions. It neither promises unlimited resources nor replaces a separate check of the returned meaning.

Before moving on

For any new recursive helper, write three lines before tracing: “I admit these starts”, “these are the reachable boundary states”, and “this nonnegative integer gets smaller on each recursive call”. Then separately check the base result, arithmetic safety and the work done while returning.

If you chose a mere equality test, try one input that could step past it. If you used halving, check 0, 1, 2 and an odd input. If you placed a dangerous expression near a guard, follow statement order and ask whether return happens first. These habits prepare you for bounded-array recursion; they do not replace the later study of branching recursion, recurrence relations or resource complexity.

Source and scope note

The official GATE 2027 CS syllabus, checked 13 October 2026, lists recursion under Section 4, Programming and Data Structures. It is used only to establish topic relevance. The explanations, code, analogy and six questions are original teaching material, not official previous-year questions or predictions of an exam pattern. C11 is our teaching convention, not a claimed exam-language-version rule. This offline lesson does not assign a course year, change any existing course identity, or establish complete exam readiness.