In capitolul 1 am prezentat rutina de backtracking clasica,nerecursiva.In acest capitol prezentam rutina de backtracking recursiva.Procedurile si functiile folosite sunt in general aceleasi,cu doua mici exceptii: g8c19cy
Ø SUCCESOR nu mai este procedura ci functie booleana ;
Ø rutina backtracking se transforma in procedura,care se apeleaza prin BACK(1)
Principiul de functionare al procedurii BACK,corespunzator unui nivel k este urmatorul:
· in situatia in care avem o solutie,o tiparim si revenim pe nivelul anterior
· in caz contrar se initializeaza nivelul si se cauta un succesor
· cand am gasit unul verificam daca este valid;procedura se autoapeleaza pentru (k+1) , in caz contrar urmand a se continua cautarea succesorului;
· daca nu avem succesor,se trece pe nivel inferior (k-1) prin iesirea din procedura BACK

Vom explica in continuare utilizarea backtrackingului recursiv prin generarea permutarilor:

program permutari; type stiva=arraya1..9i of integer; var st:stiva; ev:boolean;n,k:integer; procedure init(k:integer;var st:stiva); begin staki:=0; end; function succesor(var st:stiva;k:integer):boolean; begin if staki<n then begin staki:=staki+1; succesor:=true; end else succesor:=false; end; procedure valid(var ev:boolean;st:stiva;k:integer); var i:integer; begin ev:=true; for i:=1 to k-1 do if staii=staki then ev:=false; end;

function solutie(k:integer):boolean; begin solutie:=(k=n+1); end;

procedure tipar; var i:integer; begin for i:=1 to n do writeln(staii);

writeln; end; procedure back(k:integer); begin if solutie (k) then tipar else begin init(k,st);
while succesor(st,k) do begin valid(ev,st,k); if ev then back(k+1); end; end; end;

begin
write('n=');readln(n); back(1); end.

Desigur orice problema care admite rezolvare backtracking,poate fi rezolvata in acest mod.Insa,de multe ori,aceeasi problema se poate rezolva scriind mai putin,daca renuntam la standardizare.