Recursion for Data Structures and Algorithmss
Recursion in DSA is solving a problem by calling a function on smaller versions of itself. This unit applies it to backtracking, which builds candidate solutions and undoes choices that fail, and also covers interval problems and greedy algorithms that pick the locally best option. Subsets, permutations and scheduling are typical examples.
Stage: Linear Structures · Part of the Data Structures and Algorithms roadmap · Last reviewed 19 November 2026
What to learn in Recursion
- Write a recursive function with a clear base case and recursive step
- Generate all subsets or permutations using backtracking
- Prune a backtracking search to avoid exploring invalid branches
- Merge overlapping intervals after sorting by start time
- Decide when a greedy choice is provably safe
Recursion interview questions
What is the template for a backtracking solution?
Choose an option, add it to the current path, recurse on the remaining choices, then remove the option to restore state. When the path meets the goal, record it. Pruning invalid choices early keeps the search tractable.
How do you know if a greedy algorithm is correct?
You need a proof, usually an exchange argument showing that swapping an optimal solution's choice for the greedy one does not make it worse. Without that, test it against counterexamples, because greedy often fails where dynamic programming is needed.
Where Recursion fits in the Data Structures and Algorithms roadmap
Recursion belongs to the Linear Structures stage (intermediate level), which takes about 43 hours. Sequences.
Other units in this stage
Back to the full Data Structures and Algorithms roadmap