Rekurencja

[Daniello]

Wytłumaczcie mi na chłopski rozum do czego właściwie służy rekurencja. Gdzie ma zastosowanie. C++

[Karlik]

Rekurencja, o ile mnie pamięć nie myli to jest wywoływanie funkcji przez samą siebie, aż do określonego skutku

[Gość amdfanatyk]

rekurencja jest to metoda rozwiazywania problemow oparta na zalozeniu, ze dany problem mozna rozlozyc na k pomniejszych podproblemow; zeby rozwiazac problem wystarczy rozwiazac poszczegolne podproblemy; czesto nie jest mozliwe rozwiazanie zadanego problemu jako takiego i skazani jestesmy na rekurencyjne poszukiwanie rozwiazan czastkowych; rekurencja jest zjawiskiem naturalnym; np. jesli dziecko rozsypalo na podlodze klocki a rodzic kazal je pozbierac, to jak mozna sobie wyobrazic, dziecko bedzie zbierac po 1-kilka klockow i wrzucac je do pudelka, czyli najpierw rozwiaze k podproblemow, w efekcie rozwiazujac problem uprzatniecia zabawek; rekurencja jest zagadnieniem matematycznym (mowimy o rozwiazywaniu zadan rekurencyjnych lub krotko rekurencji) a konkretnie rekurencjami zajmuje sie matematyka dyskretna; w zwiazku z tym, ze funckje rekurencyjne sa bardzo proste i umozliwiaja rozwiazanie bardzo trudnych problemow, przystosowano kompilatory do obsugi rekurencji; przyklad:

 

int f(double param)

{

...

f(wyliczonyParametr);

...

}

 

rekurencja posiada rowniez wady: kazde wywolanie funkcji powoduje odlozenie na stos jej kopii i adresu powrotu z funkcji co czesto doprowadza do przepelnienia stosu, wyjatkiem jest rekurencja ogonowa, czyli taka, w ktorej wywolanie rekurencyjne wystepuje na koncu funkcji (po wywolaniu nie ma juz zadnego kodu) - wtedy nie ma potrzeby pamietania adresu powrotu z funkcji; nalezy rowniez pamietac, ze ciag wywolan rekurencyjnych musi byc zbierzny (skonczony), co zapewnia zwykle kontrola funkcji warunkowej lub sprawdzanie warunku w petli, jezeli takowe wywolanie zostalo w niej umieszczone (algorytmy z powrotami); jedne z najprostszych zastosowan rekurencji to: liczenie silni, liczenie liczb fibonacciego, funkcja ackermanna, funkcja sortowania szybkiego - quicksort.

[Gość _PaT]

Tu masz nieco nieudolny przykład programu z funkcją rekurencyjną ©:

#include <stdio.h>

int fibo(int n) {
if (n < 3 ){
 return 1;
 }
else {
 return fibo(n-1)+fibo(n-2);
}
}

int main() {
int ile;
int i;
printf("Podaj ile pierwszych licz fibonacciego mam wypisacn");
scanf("%d", &ile);

i = 1;
while (i<=ile){
 printf("%d ", fibo(i) );
 i++;
}
return 0;
}

Ciąg fibonacciego opisany jest wzorem: (szkoda, że nie ma tex-a)

a(n) = 1, dla n <=2

a(n) = a(n-1) + a(n-2), dla n>2

teraz wystarczy podstawiać odpowiednią wartość i krok po kroku można dojść do rozwiązania dużego problemu, jak to kolega nadmienił, za pomocą rozwiązywania małych podproblemów.

Zauważ, że ten algorytm jest bardzo niewydajny, bo dużo operacji wykonuje kilkunasto- dziesięciokrotnie. 2 najważniejsze zasady rekurencji:

1) Co ma zostać wykonane w danym kroku + ponowne wywołanie funkcji samej przez się

2) Reguła, dla której funkcja przestaje się wywoływać.

 

Mam jeszcze dwa ciekawe przykłady programów z użytą rekurencją, gdzie zastosowano tzw. rekurencję krokową (ew. rekurencję z powrotami). Jeśli krok jest możliwy, wykonujemy go, i tak aż do skutku. Dzięki rekurencji w tym przypadku możemy sprawdzić wszystkie kombinacje. Ten program jest także bardzo niewydajny, ale jest pierwszym krokowym, jaki napisałem

 

program hetmanik; {algorytm rekurencyjny z powrotami}
const max=8;
type tablica = array [1..max,1..max] of Boolean;

var tab : tablica;
   i,j : byte;
   ile_poprawnych : integer;

procedure wypisz(var tab:tablica);
var i,j	: byte;
begin
writeln;
ile_poprawnych:=ile_poprawnych+1;
for i:=1 to max do
begin
 for j:=1 to max do
  if tab[i,j]=false then write('O') else write('X');
writeln;
end;
end;

function ok(var tab:tablica):Boolean;
var i,j        : byte;
   k,l        : integer;
begin
ok:=true;

for i:=1 to max do
for j:=1 to max do
if tab[i,j]=true then {stoi hetman}
 begin
  {1 - sprawdz lewo}
  if i>2 then
  for k:=i-1 downto 1 do
   if tab[k,j]=true then begin ok:=false; exit; end;
  {2 - sprawdz prawo}
  if i<max then
  for k:=i+1 to max do
   if tab[k,j]=true then begin ok:=false; exit; end;
  {3 - sprawdz gore}
  if j>2 then
  for l:=j-1 downto 1 do
   if tab[i,l]=true then begin ok:=false; exit; end;
  {4 - sprawdz dol}
  if j<max then
  for l:=j+1 to max do
   if tab[i,l]=true then begin ok:=false; exit; end;
  {5 - sprawdz lewa gore}
  k:=i;l:=j;
  while ((k>1) and (l>1)) do 
   begin
    k:=k-1;
    l:=l-1;
    if tab[k,l]=true then begin ok:=false; exit; end;
   end;
  {6 - sprawdz lewy dol}
  k:=i;l:=j;
  while ((k>1) and (l<max)) do 
   begin
    k:=k-1;
    l:=l+1;
    if tab[k,l]=true then begin ok:=false; exit; end;
   end;
  {7 - sprawdz prawy dol}
  k:=i;l:=j;
  while ((k<max) and (l<max)) do 
   begin
    k:=k+1;
    l:=l+1;
    if tab[k,l]=true then begin ok:=false; exit; end;
   end;
  {8 - sprawdz prawa gore}
  k:=i;l:=j;
  while ((k<max) and (l>1)) do 
   begin
    k:=k+1;
    l:=l-1;
    if tab[k,l]=true then begin ok:=false; exit; end;
   end;
 end;
end;

procedure hetman(n:integer; var tab : tablica);{nr linii}
var i,j : byte;
begin
if n>max then 
begin if ok(tab) then wypisz(tab) end
else
for i:=1 to max do
begin
 {wyczysc obecny wiersz i postaw hetmana}
  for j:=1 to max do tab[n,j]:=false;
  tab[n,i]:=true;
  hetman(n+1, tab);
end;
end;


begin
ile_poprawnych:=0;
for i:=1 to max do
for j:=1 to max do
 tab[i,j]:=false;{0 - wolne pole,  1 - stoi hetman}
hetman(1,tab);
writeln('Znaleziono ',ile_poprawnych,' poprawne kombinacje');
end.

 

Teraz ostatni przykład, również algorytm krokowy, tym razem bardziej wydajny

program labirynt;
var tab : array [1..8,1..8] of integer;
   chk : array [1..8,1..8] of Boolean;
   wynikow : integer;

procedure wczytaj;
var plik : text;
   i, j : integer;
   dana : integer;
begin
assign(plik, 'dane');{/home/pat/prog/rek/dane}
reset(plik);
i:=1;
j:=0;
while not eof(plik) do
begin
 inc(j);
 read(plik, dana);
 tab[i,j] := dana;
 if eoln(plik) then begin inc(i); j:=0; end;
end;
end;

procedure przeladuj;
var i, j : integer;
begin
for i := 1 to 8 do
for j := 1 to 8 do
 chk [i,j] := false
end;

procedure wypisz_tablice;
var i,j :integer;
begin
writeln('Wczytana tablica to');
for i:=1 to 8 do
begin
for j:=1 to 8 do
 write(tab[i,j],' ');
writeln();
end;
end;

procedure wypisz_wynik;
var i,j :integer;
begin
writeln('Wynik');
for i:=1 to 8 do
begin
for j:=1 to 8 do
 if chk[i,j] then write ('x ') else  write(tab[i,j],' ');
writeln();
end;
end;

function pos(x,y : integer):Boolean;{move possibility}
begin
pos := false;
if (x>=1) and (x<=8) then
if (y>=1) and (y<=8) then
 if tab[x,y] = 1 then
  if chk[x,y] = false then
   pos := true
end;

procedure krok(x,y : integer);

begin
chk[x,y] := true;

if (x=8) and (y=8) then
begin
 wypisz_wynik;
 inc(wynikow);
end;

if pos(x-1,y) then krok(x-1,y);
if pos(x,y+1) then krok(x,y+1);
if pos(x,y-1) then krok(x,y-1);
if pos(x+1,y) then krok(x+1,y);

chk[x,y] := false;

end;



begin
wynikow := 0;
wczytaj;
wypisz_tablice;
przeladuj;
krok(1,1);
writeln('Istnieje ',wynikow,' sposobow na przejscie tej tablicy');
end.

Tylko musisz mieć do niego dołączony plik z tablicą, którą sprawdza. Plik nosi nazwę dane:

1 0 0 1 1 0 0 1
1 0 1 1 1 1 1 1
1 0 1 0 1 1 0 1
1 1 1 0 0 1 0 1
1 0 1 0 0 1 0 1
1 0 1 1 1 1 0 1
1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 1

 

I jeszcze jeden, dość prosty i bardzo popularny algorytm Quicksort:

program quicksortowanie;
const n = maxint;
var table : array [1..n] of integer;

procedure fill_table;
var i: integer;
begin
for i:=1 to n do table[i] := random(n)+1;
end;

procedure quicksort(L,P : integer);
var i,j : integer; //index
   x   : integer; //element 
   temp : integer;
begin
i:=L; j:=P;
x:=table[(L+P) div 2];
repeat
while table[i]<x do i:=i+1;
while table[j]>x do j:=j-1;
if i<=j then 
begin
 temp:=table[i];
 table[i]:=table[j];
 table[j]:=temp;
 i:=i+1;
 j:=j-1;
end
until i>j;
if L<j then quicksort(L, j);
if i<P then quicksort(i, P);
end;

procedure write_table;
var i: integer;
begin
for i:=1 to n do write(table[i], ' ');
end;

begin
fill_table;
quicksort(1, n);
write_table;
end.

 

Sorry, że w pascalu, ale może Ci się przydać. Przepisałbym to w C, oczywiście gdybym znał C, chociaż jak widać jeden program już mi się udało "na ślepo" napisać. Heh, szkoda, że nie ma kolorowania składni...

[yoshi314]

ktoś kiedyś ująl rekurencje w jednym eleganckim zdaniu.

 

żeby zrozumieć rekurencję trzeba najpierw zrozumiec rekurencję.

 

bez kitu, moge sie pod tym podpisac