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))

GATE CSE Recursion PYQs

Standard yield0.5% of Algorithms

GATE tests recursion under Algorithms by evaluating the ability to formulate exact recurrence relations for classic recursive paradigms and puzzles, such as the… Read the guide

Take topic test

Questions: 1
Asked: 2012
Total marks: 1
Marks / paper: 0

1 GATE CSE Recursion PYQs with solutions, from Algorithms. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

GATE CSE 2012 · Q16The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with $n$ discs isMCQ1 markEasySolve

What GATE tests in Recursion

Concepts, patterns, formulas and traps distilled from past papers.

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
RareMCQ1 marks2012
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).