Máme danú tyč, ktorá je dlhá N metrov. Našou úlohou je vypísať procedúru, ktorá vypíše všetky možné riešenia ro zdelenia tyče na kúsky dlhé 1a 2 metre. Napríklad N=3 riešením je:111,12,21,

1. Tyč delíme na časti dlhé 1 a 2 metre. Jednotlivé, už odrezané časti si musíme niekde pamätať, na to použijeme pole, ktoré bude globálne deklarované v programe (nie v procedúre). Na to, aby sme vedeli, koľko časti (ktorý prvok v poli) máme oddelené použijeme premennú k, tiež deklarovanú ako globálnu premennú v hlavnom programe a inicializovaná na hodnotu 0.

   Vieme, že pri prvom zavolaní procedúry má k hodnotu 0, najprv (predtým, než začneme čokoľvek robiť v procedúre) hodnotu zvýšime. Potom rozdelíme tyč na časť dlhú 1 meter a túto časť uložíme do poľa. Po odrezaní tejto časti sa nám problém zníži o jeden stupeň. Teda môžme zavolať tú istú procedúru s parametrom n-1.
   
   Procedúra:
   

   procedure rozdel(n:integer);
   var i:integer;
   begin
   	k:=k+1;
   	casti[k]:=1;
   	rozdel(n-1);
   end;

   
   
2. Takto napisaná procedúra bude deliť len na jednotky, takže musíme doplniť príkazy, aby sa delilo aj na dvojky. K tomuto celému stačí doplniť podobné príkazy. Do poľa sa na miesto k vloží číslo 2 a ostane podproblém stupňa n-2. Môžem doplniť príkaz rekurzívneho volania s parametrom n-2:
   
   

   procedure rozdel(n:integer);
   var i:integer;
   begin
   	k:=k+1;
   	casti[k]:=1;
   	rozdel(n-1);
   	casti[k]:=2;
   	rozdel(n-2);
   end;

   
   
3. Ak sa pozrieme na procedúru, tak stále zvyšujeme hodnotu premennej k. Pri prvom vnorení je to v poriadku. Problém nastáva ak sa vynoríme a ideme druhý raz vložiť prvok 2 do poľa. Pri vkladaní potrebujeme takú istú hodnotu premennej k, ako v prvom prípade. Inak povedané: pred príkazom rekurzívneho volania musíme hodnotu k zvýšiť a po rekurzívnom volaní hodnotu k znížiť:
   
   

   k:=k+1;

   casti[k]:=1;

   rozdel(n-1);

   k:=k-1;

   k:=k+1;

   casti[k]:=2;

   rozdel(n-2);

   k:=k-1;

   
   
4. Ak sa pozrieme na riadok 4 a 5, tak vidíme, že po ich vykonaní hodnota v premennej je rovnaká (jeden znižuje a druhy zvyšuje hodnotu k). Teda ich môžme vynechať a ostane nám len prvé zvýšenie a posledné zníženie hodnoty premennej:
   

   procedure rozdel(n:integer);
   var i:integer;
   begin
   	k:=k+1;
   	casti[k]:=1;
   	rozdel(n-1);
   	casti[k]:=2;
   	rozdel(n-2);
   	k:=k-1;
   end;

   
   
5. S takto upravenou procedúrou máme zabezpečené, že sa tyč bude deliť na časti 1 a 2 a vygenerujú sa všetký riešenia. Je však potrebné doplniť podmienku ukončenia. Vieme, že parameter znižujeme o 1 alebo 2. Teda podmienka vykávania procedúry je ak n>1:
   
   

   procedure rozdel(n:integer);
   var i:integer;
   begin
   	if n>1 then
   	begin
   		k:=k+1;
   		casti[k]:=1;
   		rozdel(n-1);
   		casti[k]:=2;
   		rozdel(n-2);
   		k:=k-1;
   	end;
   end;

   
   
6. Ak podmienka nie je splnená, tak je potrebné vypísať pole (riešenie). Ostáva otázka, čo ak n=1? To je prípad, že sme z tyče odrezali všetky časti a ostala posledná časť dlhá 1 meter. To ošetríme pri výpise riešenia. Ak n=1 tak sa k vypísanému riešeniu dopíšeme ešte 1:
   
   

   procedure rozdel(n:integer);
   var i:integer;
   begin
   	if n>1 then
   	begin
   		k:=k+1;
   		casti[k]:=1;
   		rozdel(n-1);
   		casti[k]:=2;
   		rozdel(n-2);
   		k:=k-1;
   	end
   	else
   	begin
   		for i:=1 to k do write(casti[i],' ');
   		if n=1 then write('1');
   		writeln;
   	end;
   end;