Competitive Coding

Unit 3: Recursion & Advanced Techniques

From base cases to backtracking — master recursive thinking, optimise with memoization, and solve competition-level problems that unlock high-paying tech careers.

⏱️ Time: 7 hrs theory + 5 hrs practice | 💰 Earning: ₹8K–₹30K/month | 📝 30 MCQs (Bloom's Mapped)

💼 Jobs this unlocks: SDE-1 (₹8–15 LPA) | Competitive Programmer (₹10–25 LPA) | Algorithm Engineer (₹12–30 LPA)

Section A

Opening Hook — The Invisible Power Behind Every Search

🗺️ How Google Maps Finds the Shortest Path in Milliseconds

Every time you open Google Maps and ask for directions, a recursive algorithm called Depth-First Search (DFS) explores a graph of 1 billion+ nodes — intersections, roads, and landmarks across the planet. The algorithm recursively explores each path, backtracks when it hits a dead end, and finds the optimal route in under 200 milliseconds. That's recursion at planetary scale.

But recursion isn't just for tech giants. Every file explorer on your laptop — Windows Explorer, macOS Finder, or Linux's ls -R — uses recursive directory traversal. When you click "Search this PC," the OS recursively enters each folder, checks its contents, enters sub-folders, checks again... until every nested file is found. That's a recursive function calling itself on every subdirectory.

What if YOU could think recursively? What if you could take a massive problem, break it into identical smaller pieces, and let the computer solve billions of sub-problems automatically? That's exactly what this chapter teaches you — the most elegant and powerful problem-solving technique in all of computer science.

🌍 Google🛒 Amazon💻 Microsoft🏆 Codeforces💡 LeetCode🧩 HackerRank

Recursion exists in nature. Romanesco broccoli grows in a fractal spiral — each small cone is a miniature replica of the whole. Tree branches split recursively: a trunk splits into branches, each branch splits into smaller branches, each twig splits into leaves. Even your lungs use recursive branching — 23 levels of branching airways to maximize surface area in a compact space. Nature solved recursion billions of years before programmers did.

Section B

Learning Outcomes — Bloom's Taxonomy Mapped (12 Outcomes)

Bloom's Level	Learning Outcome
🔵 Remember	Define recursion and identify the two essential components: base case and recursive case
🔵 Remember	List and distinguish the types of recursion: direct, indirect, tail, and non-tail
🔵 Understand	Explain how the call stack works during recursive function execution, including push/pop of stack frames
🔵 Understand	Describe how memoization eliminates overlapping subproblems and reduces exponential time to linear
🟢 Apply	Write recursive solutions for factorial, Fibonacci, power(x,n), and sum-of-digits problems in C++ and Python
🟢 Apply	Implement a backtracking solution for the N-Queens problem with constraint checking
🟢 Analyze	Compare tail recursion vs non-tail recursion in terms of stack usage, performance, and compiler optimisation
🟢 Analyze	Analyze the time complexity difference between naive recursive Fibonacci O(2ⁿ) and memoized Fibonacci O(n)
🟠 Evaluate	Judge when recursion is a better choice than iteration, considering readability, performance, and stack limits
🟠 Evaluate	Evaluate the trade-offs between top-down memoization and bottom-up tabulation for dynamic programming
🟠 Create	Design a recursive Sudoku solver that uses backtracking with constraint propagation
🟠 Create	Build a complete backtracking solution for the subset-sum problem with pruning optimisation