Guide · Algorithms · Recursion and backtracking
Recursion and Backtracking – Learning Guide
Recursion is a technique in which a function solves a problem by calling itself for a smaller problem. Backtracking, graph search, "divide and conquer" and dynamic programming are all based on it.
The guide goes from the first recursive program, through classic examples, to backtracking and generating all arrangements. All lessons have tasks with solutions in C++.
- Grades 7–8 and secondary school
- C++
- Competition preparation
Some lessons linked below are available only in Serbian for now. They are marked (SR).
1 Recursion basics
What recursion is, the base case, the call stack and classic examples from mathematics.
Introduction to recursion (SR)
The base case, the recursive step, the call stack, recursion or a loop.
Open lesson →Factorial, power and GCD (SR)
Factorial, fast exponentiation, Euclid's algorithm, Fibonacci and the number of calls.
Open lesson →Recursive algorithms
Power, Fibonacci, binary notation, the determinant and the inverse matrix.
Open lesson →Towers of Hanoi
A classic recursive problem and 2ⁿ − 1 moves.
Open lesson →2 Backtracking and generating
Systematically trying possibilities and going back: arrangements, subsets, puzzles.
Backtracking (SR)
The choose–explore–undo pattern, subsets with a given sum, N queens, a maze.
Open lesson →Permutations and combinations (SR)
Generating permutations, combinations, variations and subsets; next_permutation.
Open lesson →Sudoku solver (SR)
A complete solver and speeding it up by choosing the cell with the fewest possibilities.
Open lesson →3 Practice tasks
Collections of recursion and backtracking tasks with solutions.
Recursive algorithms – examples
Tasks that are solved with recursion.
Open lesson →Backtracking and brute force – tasks (SR)
N queens, Sudoku, a maze and other tasks with solutions.
Open lesson →Combinatorial problems – examples (SR)
Generating variations, subsets and permutations.
Open lesson →N queens – solution
A detailed solution that prints the arrangements.
Open lesson →4 What next
When recursion starts computing the same things many times, you move on to dynamic programming.
Suggested order
- Introduction to recursion (SR)
- Factorial, power and GCD (SR)
- Recursive algorithms
- Towers of Hanoi
- Backtracking (SR)
- Permutations and combinations (SR)
- Sudoku solver (SR)
- Tasks: backtracking and brute force (SR)
Useful external resources
- Petlja – collections of tasks with automatic checking (in Serbian)
- CSES Problem Set – the "Introductory Problems" section (Permutations, Chessboard and Queens, Grid Paths)
- C++ Tutor – running recursion step by step, showing the call stack
