Recursion: 12-question learning review

Use this review to identify the next thing to repair

Complete the five introductory recursion lessons before this review: base case and call stack; termination and base-case design; returned values and pending calculations; bounded-array traversal; and total calls versus maximum active frames. You also need the earlier C lessons on copied function arguments, array bounds, conditions and integer arithmetic, including Array parameters and caller-visible changes. Question 12 is a transfer exercise combining that lesson’s shared-element writes with recursive unwinding.

This is standard learning practice: 12 original single-correct questions, each with four options. It is not an official previous-year paper, a full GATE mock, or a prediction of an exam’s question mix. There is no time limit or exam marking scheme assigned here. Try every question before reading the explanations. Record the call state or trace that supports your choice; a guessed option alone does not show which reasoning step is secure.

Shared conventions

• Use C11. Each question gives a small admitted input range or exact input; do not extrapolate to arbitrary signed integers or recursion depths.
• Every ordinary parameter/local belongs to its invocation. The array-parameter questions use existing caller storage; the selected length does not copy or resize an array.
• A prefix of length n contains indices 0 through n - 1. At n = 0 it is empty. All actual arrays shown have positive capacity; “empty prefix” does not mean declaring a zero-length C array.
• const int a[] prevents modifying elements through that parameter. It does not create a new array. Question 12 intentionally uses a writable array parameter.
• In call-count questions, include the initial and base-case invocations of the named helper. Exclude main and library calls. Count a waiting caller as active until it returns.
• Maximum active frames are logical call records, not measured stack bytes or a promise of the compiler’s physical allocation. Separately written child-call statements are executed in the displayed order; completed siblings no longer remain active.
• To run a function fragment as a program, add a valid caller and any required headers. Questions 1 and 12 are complete programs. Analyze question 8 and the failing alternatives in question 3 without executing undefined or nonterminating code.

Questions

Question 1

What does this complete program print? The admitted starting inputs for peel are 0 through 4.

#include <stdio.h>

int peel(int n) {
    if (n == 0) { return 5; }
    int child = peel(n - 1);
    return child - 1;
}

int main(void) {
    int n = 3;
    int result = peel(n);
    printf("%d %d\n", n, result);
    return 0;
}

A. 3 2

B. 0 2

C. 3 5

D. 0 5

Question 2

For starting inputs 0 through 26, reduce counts divisions by 3 until the value is at most 2. What does reduce(26) return?

int reduce(int n) {
    if (n <= 2) { return 0; }
    int child = reduce(n / 3);
    return 1 + child;
}

A. 0

B. 1

C. 2

D. 3

Question 3

Which proposed starting-input set is guaranteed to reach the equality base case for every member? Analyze the argument sequence; do not execute failing inputs.

int groups(int n) {
    if (n == 0) { return 0; }
    int child = groups(n - 4);
    return 1 + child;
}

A. Every integer from 0 through 12

B. Only 0, 4, 8 and 12

C. Only 2, 6 and 10

D. Only -4 and 0

Question 4

For starting inputs 0 through 3, what value does blend(3) return?

int blend(int n) {
    if (n == 0) { return 2; }
    int child = blend(n - 1);
    return 3 * child - 1;
}

A. 26

B. 41

C. 42

D. 53

Question 5

For starting inputs 0 through 4, what does zig(3) return? The test after the child call uses this caller’s n.

int zig(int n) {
    if (n == 0) { return 0; }
    int child = zig(n - 1);
    if (n % 2 == 0) { return child + 2; }
    return 2 * child + 1;
}

A. 3

B. 5

C. 7

D. 9

Question 6

Given int a[4] = {2, 1, 3, 8}, what does weighted(a, 3) return? Admit 0 <= n <= 4; each selected element is multiplied by its one-based position.

int weighted(const int a[], int n) {
    if (n == 0) { return 0; }
    int child = weighted(a, n - 1);
    return child + n * a[n - 1];
}

A. 7

B. 13

C. 21

D. 45

Question 7

Given int a[4] = {2, 1, 2, 5}, which pair gives (count_equal(a, 0, 2), count_equal(a, 3, 2))? Admit 0 <= n <= 4.

int count_equal(const int a[], int n, int target) {
    if (n == 0) { return 0; }
    int child = count_equal(a, n - 1, target);
    if (a[n - 1] == target) { return child + 1; }
    return child;
}

A. (1, 2)

B. (0, 3)

C. (4, 2)

D. (0, 2)

Question 8

For int a[3] = {4, 7, 9}, which diagnosis of bad_sum(a, 3) is correct? Do not execute this faulty call.

/* Analyze this faulty fragment; do not run bad_sum(a, 3). */
int bad_sum(const int a[], int n) {
    if (n == 0) { return 0; }
    int last = a[n];
    int child = bad_sum(a, n - 1);
    return last + child;
}

A. It must return 20 because all three stored elements are added.

B. The first non-base call reads a[3], outside the actual array; no predictable C output follows from this code.

C. The n == 0 guard makes every array access safe.

D. It must return 0 because a[3] is automatically initialized to zero.

Question 9

For starting inputs 0 through 5, consider jumps(5). Which triple is (returned value, total jumps invocations, maximum simultaneously active jumps invocations)? Include initial and base calls; exclude main and library calls.

int jumps(int n) {
    if (n <= 0) { return 0; }
    int child = jumps(n - 2);
    return 1 + child;
}

A. (3, 4, 4)

B. (4, 4, 4)

C. (3, 3, 3)

D. (3, 7, 4)

Question 10

For admitted starting inputs 0 through 3, consider leaves(2). Which triple is (returned value, total leaves invocations, maximum simultaneously active leaves invocations)? Count the logical execution, including initial/base calls and excluding main/library calls.

int leaves(int n) {
    if (n == 0) { return 1; }
    int left = leaves(n - 1);
    int right = leaves(n - 1);
    return left + right;
}

A. (4, 4, 3)

B. (4, 7, 7)

C. (7, 7, 3)

D. (4, 7, 3)

Question 11

For admitted starting inputs 0 through 4, what pair gives (total mixed invocations, maximum active mixed invocations) for mixed(3)? Use the same logical counting convention as question 10.

int mixed(int n) {
    if (n <= 1) { return 1; }
    int first = mixed(n - 1);
    int second = mixed(n - 2);
    return first + second;
}

A. (3, 3)

B. (5, 3)

C. (5, 5)

D. (7, 3)

Question 12

What does this complete program print? The array has capacity 3 and the selected length may be 0 through 3. void and return; mean that no numeric value is returned.

#include <stdio.h>

void raise_prefix(int a[], int n) {
    if (n == 0) { return; }
    raise_prefix(a, n - 1);
    a[n - 1] = a[n - 1] + n;
}

int main(void) {
    int a[3] = {3, 3, 3};
    raise_prefix(a, 2);
    printf("%d %d %d\n", a[0], a[1], a[2]);
    return 0;
}

A. 4 5 6

B. 3 3 3

C. 4 5 3

D. 5 4 3

Answers and complete option feedback

Answer 1: A

• A. Correct. Starting from the base value 5, the waiting calls return 4, 3 and 2. main keeps its own n = 3.

• B. Incorrect. The result 2 is right, but recursive parameter values do not overwrite main’s n.

• C. Incorrect. This keeps main’s n correctly but skips the three pending subtractions.

• D. Incorrect. This both changes the caller’s n and omits the waiting work.

Answer 2: C

• A. Incorrect. The initial 26 does not satisfy n <= 2, so at least one recursive step is needed.

• B. Incorrect. The first child is 8, which is still greater than 2; another step is required.

• C. Correct. Integer division gives 26 → 8 → 2. Two divisions are counted; the base-case call returns 0.

• D. Incorrect. Three invocations occur, but the returned count is two divisions. No division is performed at 2.

Answer 3: B

• A. Incorrect. This includes 1; the mathematical sequence 1, -3, -7, … never reaches zero.

• B. Correct. A nonnegative multiple of 4 stays a nonnegative multiple of 4 as it decreases toward zero.

• C. Incorrect. These paths reach 2 and then -2, skipping zero. Equality requires exact arrival.

• D. Incorrect. Zero returns, but -4 moves to -8 and farther away. One successful input does not justify the set.

Answer 4: B

• A. Incorrect. This is 3 * 3 * 3 - 1. It ignores the base value 2 and also subtracts only once instead of at every non-base return.

• B. Correct. Returning from arguments 0, 1, 2, 3 gives 2, 5, 14, 41. The final operation is 3 * 14 - 1.

• C. Incorrect. This multiplies 14 by 3 but omits the final subtraction of 1.

• D. Incorrect. This computes 2 * 3 * 3 * 3 - 1, subtracting only once. The code subtracts at each non-base return.

Answer 5: C

• A. Incorrect. This is zig(2); the waiting n = 3 caller still has work to do.

• B. Incorrect. This adds 2 to zig(2) = 3 as if the n = 3 caller were even. It is odd.

• C. Correct. The base returns 0; n = 1 returns 1, n = 2 returns 3, and n = 3 returns 2 * 3 + 1 = 7.

• D. Incorrect. This adds 2 once more after the odd branch has already returned. An executed return ends that call.

Answer 6: B

• A. Incorrect. This is the zero-based weighted sum 0 * 2 + 1 * 1 + 2 * 3. The code uses weights 1, 2 and 3.

• B. Correct. The selected prefix contributes 1 * 2 + 2 * 1 + 3 * 3 = 13. The element at index 3 is not selected.

• C. Incorrect. This adds the unselected value 8 to the correct prefix result without following the code.

• D. Incorrect. This is the four-element weighted total. The call selects only three elements.

Answer 7: D

• A. Incorrect. An empty selected prefix contains no matches, even though storage exists beyond it.

• B. Incorrect. The selected three values are 2, 1 and 2. Only two equal the target; the element count is not the match count.

• C. Incorrect. Array capacity 4 is not the answer for an empty selected prefix.

• D. Correct. n = 0 returns 0 before reading any element. At n = 3, indices 0 and 2 match the target, giving 2.

Answer 8: B

• A. Incorrect. The intended sum does not define what an out-of-bounds C access will do.

• B. Correct. The valid indices are 0, 1 and 2. At n = 3, a[n] is already an invalid read; the last selected element would be a[n - 1].

• C. Incorrect. The guard handles the empty case, not the incorrect index used on a positive-length case.

• D. Incorrect. There is no fourth array element. Rules for omitted initializers do not create additional elements.

Answer 9: A

• A. Correct. The argument chain is 5, 3, 1, -1. Four calls coexist just before the base returns; three non-base calls each add 1.

• B. Incorrect. The base returns 0 and does not add 1, so the returned value is 3, not the four-call count.

• C. Incorrect. This omits the base invocation at -1 from both call counts.

• D. Incorrect. There is only one child per non-base call, so no extra sibling calls exist. Seven would count an imagined tree.

Answer 10: D

• A. Incorrect. Four is the number of base-case leaves, not all invocations. The root and two non-base children must also be counted.

• B. Incorrect. Seven invocations occur over time, but sibling branches are evaluated sequentially, not all active at once.

• C. Incorrect. Each base returns 1 and only those values are added. The returned value is 4, not the total invocation count 7.

• D. Correct. There is one root, two n = 1 calls and four n = 0 calls: seven total. A longest active path is 2 → 1 → 0: three calls. The four base values sum to 4.

Answer 11: B

• A. Incorrect. Three is the returned value and also the maximum depth here, but total calls include both children of the n = 2 call and the final n = 1 sibling.

• B. Correct. List the invocations in order: 3, 2, 1, 0, 1. Five occur, and the longest active path is 3 → 2 → 1 (or 0), with three active calls.

• C. Incorrect. Earlier child calls finish before the second child starts. Total calls do not remain active together.

• D. Incorrect. The second child of n = 3 is n = 1 and returns immediately. It is not another n = 2 subtree.

Answer 12: C

• A. Incorrect. This changes the unselected third element. The initial selected length is 2, not the capacity 3.

• B. Incorrect. The array elements are shared caller storage, not a copied array. Valid writes through a change the caller-visible elements.

• C. Correct. After the empty call returns, n = 1 adds 1 to a[0], then n = 2 adds 2 to a[1]. a[2] is untouched, giving 4 5 3.

• D. Incorrect. This adds 2 to the first element and 1 to the second, reversing the increments for n = 1 and n = 2. Each returning call adds its own n to a[n - 1].

Use the result to choose the next lesson to revisit

• Questions 1, 4 and 5: keep a separate caller record and write the exact pending operation before substituting the child’s returned value.
• Questions 2 and 3: state the accepted domain, check the boundary, and explain progress rather than spotting a return statement.
• Questions 6, 7, 8 and 12: write actual capacity, selected length and last valid selected index. Distinguish a copied length from shared element storage.
• Questions 9, 10 and 11: draw one node per invocation, then highlight only one currently active root-to-current-call path. Total nodes, maximum active calls and returned value are different quantities.

For a compact worked check of question 11, mixed(3) first enters mixed(2); that call enters mixed(1), which returns, then mixed(0), which returns. mixed(2) returns 2. Only then does the root enter its second child, mixed(1). That call returns 1, so the root returns 3. The five invocations were never all active together; the peak was three. Use this explanation to diagnose the counting error rather than memorize “five”.

A precise analogy

Keep one ticket for every visit to a helper. The pile of all tickets records total invocations. A separate stack of unfinished tickets records active calls; a finished child’s ticket leaves that stack before its sibling starts. The number written as an answer on a ticket is a third quantity. Tickets are a logical tracing aid, not a statement about physical C stack storage.

Key box for the next practice attempt

1. State the input contract and the meaning of the returned result.
2. Stop safely at the boundary before reading an invalid element.
3. Keep each caller’s own state and pending computation.
4. Distinguish shared array elements from copied parameters.
5. Count total calls and maximum active calls separately.
6. Explain a wrong option before changing your answer.

Finishing this review closes only the introductory module. It does not certify complete recursion, algorithmic-complexity, data-structure or GATE CS coverage. More complex recursion, formal recurrence analysis and larger data structures require separate study.

Source note

The official GATE 2027 CS syllabus, verified on 13 October 2026, establishes recursion and array topic relevance within Programming and Data Structures. The questions and explanations here are original practice, not official PYQs. C11 is the teaching convention. This material does not change an existing course year or its access settings.