De ce contează?
Explorezi un labirint fără hartă. La fiecare răscruce alegi un coridor și mergi înainte. Dacă ajungi într-o fundătură, nu te panichezi: te întorci exact la ultima răscruce și încerci coridorul următor. Repeți până ai bătut toate drumurile. Backtracking-ul este fix asta: încerci o alegere, mergi mai adânc, iar dacă nu mai poți continua, te întorci și încerci alta.
Intuiția
Multe probleme cer să generezi toate configurațiile de un anumit fel: toate permutările, toate submulțimile, toate șirurile binare. Ideea comună e simplă: construiești soluția poziție cu poziție. Pe fiecare poziție încerci pe rând fiecare alegere validă, cobori să completezi poziția următoare, apoi anulezi alegerea și treci la următoarea. Așa atingi sistematic fiecare configurație, fără să uiți vreuna și fără să repeți.
Recursivitatea generează „buclele” dinamic: nu scrii tu n bucle imbricate, ci
un singur apel back(pozitie) care, la fiecare nivel, încearcă o alegere,
recurge pentru poziția următoare, apoi anulează alegerea. Adâncimea
recursiei ține locul numărului de bucle — și el poate fi oricât.