What are common examiner traps in Recursion?

Confusing linear reduction T(n-1) with divide-and-conquer partitioning T(n/2) Misidentifying the non-recursive base work (e.g., assuming O(n) work per step instead of a single move +1) Incorrect subproblem size reduction (e.g., writing T(n-2) instead of T(n-1))

Recursion

1 Qs · 2012 · 1 marks · 0 marks/paperStandard yield

Take topic test

GATE tests recursion under Algorithms by evaluating the ability to formulate exact recurrence relations for classic recursive paradigms and puzzles, such as the Towers of Hanoi. Qu… Guide

Type

GATE CSE 2012Q16MCQ1 markEasyThe recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with $n$ discs is

Topic guide

What does GATE test in Recursion?

GATE tests recursion under Algorithms by evaluating the ability to formulate exact recurrence relations for classic recursive paradigms and puzzles, such as the Towers of Hanoi. Questions assess whether candidates understand the subproblem structure (number of recursive calls and subproblem size) and the non-recursive work performed at each step.

Core concepts

Towers of Hanoi optimal move strategy
Formulating recurrence relations from recursive algorithms
Subproblem decomposition (reducing size n to n-1)
Accounting for constant-time non-recursive overhead per step

Recurring question patterns

Recurrence Formulation of Classical Recursive Problems
rare · MCQ · 1 marks · 2012
Identifying the exact recurrence relation $T(n)$ that models the optimal time complexity or step count of a canonical recursive problem with $n$ elements.

Formulas GATE uses

Towers of Hanoi Recurrence

T(n) = 2T(n - 1) + 1

Used to compute the optimal number of moves or execution time to transfer $n$ discs across 3 pegs in the Towers of Hanoi problem.

Examiner traps in Recursion

Confusing linear reduction T(n-1) with divide-and-conquer partitioning T(n/2)
Misidentifying the non-recursive base work (e.g., assuming O(n) work per step instead of a single move +1)
Incorrect subproblem size reduction (e.g., writing T(n-2) instead of T(n-1))

How questions are asked

Identify recurrence relation for a standard recursive problem

Paper trends

Direct identification of standard recurrence relations for foundational recursive algorithmic problems appeared as a 1-mark conceptual MCQ.
2012

Difficulty notes

Easy questions ask for standard, well-known recurrence relations directly from standard algorithmic problems (e.g., classic 3-peg Towers of Hanoi). Higher difficulty questions typically introduce modifications (e.g., restricted peg movements, 4 pegs, or asking for the exact closed-form count / state after $k$ steps via NAT).