CS Atlas GATE 2027
PDS course
0 / 103 complete

PDS/Phase 2 · Recursion

Checkpoint CP2 · Item 43 of 103

Recursion

Read at your own pace. Try the questions before opening the answers.

On this page

⏱️

15 questions · 23 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.

Q1MCQ1 markBase case

Which recursive function terminates for every n ≥ 0?

  • (A) f(n) { if (n <= 0) return 0; return f(n - 2); }
  • (B) f(n) { return f(n - 1); }
  • (C) f(n) { if (n == 0) return 0; return f(n - 2); }
  • (D) f(n) { if (n == 1) return 1; return f(n + 1); }

Q2MCQ2 marksOutput

What does this print?

void show(int n)
{
    if (n == 0)
        return;
    show(n / 10);
    printf("%d", n % 10);
}

void showRev(int n)
{
    if (n == 0)
        return;
    printf("%d", n % 10);
    showRev(n / 10);
}

int main(void)
{
    show(2027);
    printf(" ");
    showRev(2027);
    printf("\n");
    return 0;
}
  • (A) 7202 7202
  • (B) 2027 2027
  • (C) 2027 7202
  • (D) 7202 2027

Q3NAT1 markCalls

How many calls does recursive fib(4) make?

Numerical answer: ________

Q4NAT2 marksPrints

How many numbers does this print? (g as in Lesson 2.1.2, called as g(4))

void g(int n)
{
    if (n <= 0)
        return;
    g(n - 1);
    printf("%d ", n);
    g(n - 1);
}

int main(void)
{
    g(4);
    printf("\n");
    return 0;
}

Numerical answer: ________

Q5NAT1 markHanoi

Tower of Hanoi with 8 disks: total moves?

Numerical answer: ________

Q6MCQ1 markGCD

gcd(270, 192) by Euclid’s recursion is:

  • (A) 2
  • (B) 12
  • (C) 6
  • (D) 18

Q7NAT2 marksPower

Computing x¹⁶ by halving (x¹⁶ = (x⁸)², …, x¹ = (x⁰)²·x), how many recursive calls are made in total, counting the first call and the call with n = 0?

Numerical answer: ________

Q8NAT2 marksStatic

What does this print?

int f(int n)
{
    static int i = 1;
    if (n >= 5)
        return n;
    n = n + i;
    i++;
    return f(n);
}

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

Numerical answer: ________

Q9NAT2 marksRecurrence

f(0) = 0, f(1) = 1, f(n) = f(n − 1) + f(n − 2) + 1. What is f(6)?

Numerical answer: ________

Q10MCQ2 marksMystery

What does this print?

int mystery(int a, int b)
{
    if (b == 0)
        return 0;
    if (b % 2 == 0)
        return mystery(a + a, b / 2);
    return mystery(a + a, b / 2) + a;
}

int main(void)
{
    printf("%d %d\n", mystery(6, 7), mystery(13, 10));
    return 0;
}
  • (A) 13 23
  • (B) 42 130
  • (C) 42 120
  • (D) 36 130

Q11MCQ1 markDepth

The maximum stack depth (frames of f) of naive fib(n) is about:

  • (A) n
  • (B) log n
  • (C) n²
  • (D) 2ⁿ

Q12MCQ1 markBig-O

2n³ + n² log n is:

  • (A) O(n⁴)
  • (B) O(log n)
  • (C) O(n² log n)
  • (D) O(n³)

Q13NAT1 markLoop count

How many times does for (i = 1; i < 81; i *= 3) run?

Numerical answer: ________

Q14MCQ2 marksGrowth

Which program part dominates: an O(n log n) step followed by an O(n²) step inside a loop that runs log n times?

  • (A) O(n log n)
  • (B) O(n² log n)
  • (C) O(n²)
  • (D) O(log n)

Q15MSQ2 marksRecursion facts

Which are true?

  • (A) gcd(a, b) = gcd(b, a % b).
  • (B) Code after the recursive call runs in reverse order of the calls.
  • (C) A static local inside a recursive function has one copy per call.
  • (D) Hanoi’s largest disk moves once.

Answer Vault

Try the questions first. Open when you are ready to check.

Q1 Answer: (A)1 mark

Every input reaches n ≤ 0.

  • (B) is wrong: No base case.
  • (C) is wrong: Odd n skip 0 and go negative forever.
  • (D) is wrong: n moves away from 1.

Re-read: Lesson 2.1.1 — Base case and recursive case; tracing calls on the stack

Q2 Answer: (C)2 marks

Printing after the call restores the order; printing before reverses it.

Output

2027 7202
  • (A) is wrong: show keeps the order.
  • (B) is wrong: showRev prints the last digit first.
  • (D) is wrong: show prints after recursing: original order.

Re-read: Lesson 2.1.2 — Recursion trees; counting calls; work done before vs after the recursive call

Q3 Answer: 91 mark

1 + 5 + 3.

Re-read: Lesson 2.1.2 — Recursion trees; counting calls; work done before vs after the recursive call

Q4 Answer: 152 marks

2⁴ − 1 = 15.

Output

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

Re-read: Lesson 2.1.2 — Recursion trees; counting calls; work done before vs after the recursive call

Q5 Answer: 2551 mark

2⁸ − 1.

Re-read: Lesson 2.1.3 — Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursion

Q6 Answer: (C)1 mark

6: 270 → 192 → 78 → 36 → 6 → 0.

  • (A) is wrong: 6 is larger and divides both.
  • (B) is wrong: 12 does not divide 270.
  • (D) is wrong: 18 does not divide 192.

Re-read: Lesson 2.1.3 — Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursion

Q7 Answer: 62 marks

n = 16, 8, 4, 2, 1, 0: 6.

Re-read: Lesson 2.1.3 — Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursion

Q8 Answer: 72 marks

Shared i.

Output

7

Re-read: Lesson 2.1.4 — Computing what a recursive function returns via its recurrence; static and global variables inside recursion

Q9 Answer: 202 marks

0, 1, 2, 4, 7, 12, 20.

Re-read: Lesson 2.1.4 — Computing what a recursive function returns via its recurrence; static and global variables inside recursion

Q10 Answer: (B)2 marks

mystery multiplies.

Output

42 130
  • (A) is wrong: It does not add a and b.
  • (C) is wrong: 13 × 10 = 130.
  • (D) is wrong: 6 × 7 = 42.

Re-read: Lesson 2.1.4 — Computing what a recursive function returns via its recurrence; static and global variables inside recursion

Q11 Answer: (A)1 mark

The longest chain is n → n − 1 → … → 1.

  • (B) is wrong: n decreases by 1 along the chain.
  • (C) is wrong: Depth is linear.
  • (D) is wrong: That is the number of calls.

Re-read: Lesson 2.1.2 — Recursion trees; counting calls; work done before vs after the recursive call

Q12 Answer: (D)1 mark

n³ dominates.

  • (A) is wrong: Not tight; the dominant term is n³.
  • (B) is wrong: Far too small.
  • (C) is wrong: n³ grows faster.

Re-read: Lesson 2.2 — Counting work: a Big-O primer

Q13 Answer: 41 mark

i = 1, 3, 9, 27; 81 fails: 4.

Re-read: Lesson 2.2 — Counting work: a Big-O primer

Q14 Answer: (B)2 marks

The loop multiplies n² by log n; that dominates n log n.

  • (A) is wrong: The loop part is bigger.
  • (C) is wrong: Multiply by the loop count.
  • (D) is wrong: Too small.

Re-read: Lesson 2.2 — Counting work: a Big-O primer

Q15 Answer: (A) (B) (D)2 marks

A static has one copy for the whole program.

  • (C) is wrong: Statics are shared.

Re-read: Lesson 2.1.4 — Computing what a recursive function returns via its recurrence; static and global variables inside recursion

If you got these wrong, re-read

QuestionMarksTopicRe-read
Q11Base caseLesson 2.1.1
Q22OutputLesson 2.1.2
Q31CallsLesson 2.1.2
Q42PrintsLesson 2.1.2
Q51HanoiLesson 2.1.3
Q61GCDLesson 2.1.3
Q72PowerLesson 2.1.3
Q82StaticLesson 2.1.4
Q92RecurrenceLesson 2.1.4
Q102MysteryLesson 2.1.4
Q111DepthLesson 2.1.2
Q121Big-OLesson 2.2
Q131Loop countLesson 2.2
Q142GrowthLesson 2.2
Q152Recursion factsLesson 2.1.4
ONE MORE CONNECTION MADE

Ready for the next idea?

Mark this item complete when you’ve finished reading and working through it.