Рекурсия, интересные рекурсивные решения Опции

[Altair]

======= ВОЗВЕДЕНИЕ В СТЕПЕНЬ ===========
Вчера посмотрел на мои лабораторные по прологу и вспомнил про рекурсию.
Вот решил сделать на пасе. Посмотрите что получилось:

Код

{----------------------------------------------|
| процедура рекурсивного возведения |
| числа p в степень n, результат           |
|  - число r                                           |
|----------------------------------------------}
Procedure S(Var p,n,r : Integer);
Begin
IF r=0 Then r:=1;
IF n=0 Then Exit;
r:=r*p;
Dec(n);
S(p,n,r)
End;

Var
a,b,c:Integer;
Begin
ReadLn(a,b);
S(a,b,c);
WriteLn(c);
End.

Процедура возводит число p в n -ую степень.


--------------
Выкладывайте сюда свои интересные рекурсивные решения!

[mithquessir]

Рекурсивное нахождение чисел Фибоначчи:

Код

function fib(n:integer):longint;
 begin
   case n of
     0: fib := 0;
     1,2:fib := 1
     else
       fib := fib(n-1) + fib(n-2)
   end;
 end;

begin
 WriteLn(fib(33));
end.

Рекурсивный перевод чисел в двоичную систему счисления:

Код

procedure bin(n:longint);
 begin
   if n > 1 then
     bin(n div 2);
   Write(n mod 2);
 end;

begin
 bin(256);
end.

Быстрая сортировка Хоара:

Код

const
 n = 5;
 a:array[1..n] of integer= (2,5,2,1,-4);
var
 i:integer;  
procedure QSort(m,l:word);
 var
   x,i,j:integer;
   w:word;
 begin
   i := m;
   j := l;
   x := a[(m+l) div 2];
   repeat
     while a[i] < x do
     inc(i);
     while a[j] > x do
     dec(j);
     if i <= j then
     begin
       w := a[i];
       a[i] := a[j];
       a[j] := w;
       inc(i);
       dec(j);
     end;
   until i > j;
   if m < j then QSort(m,j);
   if i < l then QSort(i,l);
end;

begin
 QSort(1,n);
 for i := 1 to n do
   Write(a[i]:2);
end.