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
How to work: for every example draw the call tree for a small input (e.g. n = 3). Once you understand in which order the calls open and close, recursion stops being "magic".

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.

2 Backtracking and generating

Systematically trying possibilities and going back: arrangements, subsets, puzzles.

3 Practice tasks

Collections of recursion and backtracking tasks with solutions.

4 What next

When recursion starts computing the same things many times, you move on to dynamic programming.

Suggested order

  1. Introduction to recursion (SR)
  2. Factorial, power and GCD (SR)
  3. Recursive algorithms
  4. Towers of Hanoi
  5. Backtracking (SR)
  6. Permutations and combinations (SR)
  7. Sudoku solver (SR)
  8. Tasks: backtracking and brute force (SR)
For competitors: recursion and backtracking are the first week of the plan Preparation for the national competition and SIO. Backtracking is enough when the input is small (n up to 20–25); for larger inputs you need dynamic programming or a greedy algorithm.

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