markon Temat założony przez niniejszego użytkownika |
algorytmy rekurencyjne » 2011-01-26 14:19:34 witam,
w jaki sposób funkcjonują funkcje rekurencyjne,
wiem, że polega to na wywołaniu funkcji z własnego ciała, ale w jaki sposób wartość z poprzedniego wywołania jest pamiętana i odczytywana w następnym wywołaniu
2. np. return min(min(tab)); // jak zachowa sie taki zapis rekurencyjny?
|
|
DejaVu |
» 2011-01-26 14:34:38 Twój przykład to nie jest rekurencja. |
|
jsc |
» 2011-01-26 14:47:42 Ja mam pytanie do autora co rozumie przez algorytmy rekurencyjne?
Jak znowu usłyszę silnia to się załamię.
A powszechny sposób jej nauki zasługuje na miano kłamstwo rekurencyjne. |
|
ison |
» 2011-01-26 15:07:31 przykład wyliczania n-tego elementu ciągu Fibonacciego przez rekurencję: #include <cstdio>
int fib( int n )
{
if( n <= 0 ) return 0;
if( n == 1 ) return 1;
return fib( n - 1 ) + fib( n - 2 );
}
int main()
{
int x;
scanf( "%d", & x );
printf( "%d\n", fib( x ) );
}
Powyższy przykład nie jest wydajną metodą na liczenie liczb Fibonacciego. Jest to tylko przykład rekurencji. |
|
jsc |
» 2011-01-26 16:10:46 Kod Isona można zastąpić tym:
#include <iostream>
using namespace std;
class fib
{
public:
int n1;
int n2;
fib()
{
n1 = 0;
n2 = 1;
}
};
unsigned int wylicz( int ilen )
{
if( ilen <= 1 )
{
return ilen == 1 ? 1: 0;
}
else
{
fib * licznik = new fib;
int temp;
for( int n = 2; n <= ilen; ++n )
{
temp = licznik->n1 + licznik->n2;
licznik->n1 = licznik->n2;
licznik->n2 = temp;
}
return licznik->n2;
}
}
int main()
{
int cos;
cin >> cos;
cout << wylicz( cos );
return 0;
}
Działanie rekurencji mogę opisać na tych kodach:
Kod funkcja Isona odkłada za każdym samowywołaniem na stos adres funkcji wywołującej i argumenty wywołania:
czyli wywołanie z main () powoduje ubytek 8 bajtów ze stosu, a każde wywołanie wewnętrzne kradnie już bodajże 16 bajtów. Utrata wydajności jest spowodowana operacjami na stosie i tym, że funkcja jest jakby najpierw deklarowana, a dopiero później wywoływana. Stosowalność jej użycia jest ściśle ograniczona wzorem:
wielkość_stosu = 8 bajtów + 16 bajtów * (argument_pierwotny - 2)
Mój kod jest zwykłą pętlą for. Jego bez jakiś cudów na obszarach bitowych jest ograniczona wielkością zakresu zmiennej. Więc pod tym względem wcale nie przesądzam, który kod jest lepszy. Ponieważ stosowalność można ustalić tylko po długotrwałych testach, do których nie mam ochoty ani czasu. |
|
ison |
» 2011-01-26 16:20:34 @jsc wg Ciebie Twój kod jest rekurencyjny? Odsyłam do wikipedii co to jest rekurencja :) Więc pod tym względem wcale nie przesądzam, który kod jest lepszy.
|
czytanie ze zrozumieniem rox... Powyższy przykład nie jest wydajną metodą na liczenie liczb Fibonacciego. Jest to tylko przykład rekurencji.
|
Kod funkcja Isona odkłada za każdym samowywołaniem na stos adres funkcji wywołującej i argumenty wywołania
|
wiesz, a ja bym powiedział, że mój kod jest wolny dlatego, że działa w czasie wykładniczym... ale już wspominałem że to był tylko przykład rekurencji Mój kod jest zwykłą pętlą for. Jego bez jakiś cudów na obszarach bitowych jest ograniczona wielkością zakresu zmiennej.
|
Napisałeś kod, który liczy liczby Fibonacciego! Super! ale moment moment, chyba nie tego tyczy się ten temat? Już pomijając sam fakt, że bez potrzeby używasz klas w swoim programie i to, że Twój kod jest znacznie przekombinowany Tak w ogóle to masz memory leak w Twojej funkcji (nie wiem po kiego grzyba w ogóle robisz to na wskaźnikach) |
|
jsc |
» 2011-01-26 16:30:37
Mój kod jest zwykłą pętlą for.
|
Ja chciałem tylko opisać ograniczenia rekurencji, że jej głównym problemem jest rozmiar stosu, a co tego porównywania stosowalności masz rzeczywiście rację, że się zagalopowałem (ponieważ ty i ja do przechowywania wyników używany unsigned int). Rozmiar stosu jest dlatego problemem ponieważ jego przepełnienie uniemożliwia poprawną kontynuację pracy programu, a mój może coś tam wydziwiać (nie przeczę, że ta metoda to więcej zachodu niż to warte) i przekształcić wyniki na string przechowujący postać graficzną prawidłowego wyniku. Dla mnie wady rekurencji muszą być okupione znacznym uproszczeniem algorytmu. |
|
DejaVu |
» 2011-01-26 16:56:28 Stos jest na tyle duży, że sensowna rekurencja i tak nie zapełni jego by aplikacja przestała działać. Poza tym jest on często szybszy niż rozwiązanie nierekurencyjne. |
|
| « 1 » 2 3 4 5 6 |