Mam dla Was następną część z cyklu rekurencji. Wiemy już, że rekurencja oznacza odwoływanie się funkcji do samej siebie. A co w przypadku chęci zrobienia w drugą stronę? Powiedzmy, że ktoś grymasi przy rekurencji i chciałby zaaplikować wersję iteracyjną jakiegoś algorytmu poprzez zwykłą pętlę. Da się tak zrobić, ba, nawet na taki manewr wymyślono hasło. Nie połamcie sobie języka: "derekursywacja"!
| Tweet |
NA CZYM POLEGA DEREKURSYWACJA?
Stawiając oba terminy obok siebie możemy jeszcze od biedy wywnioskować, że mają ze sobą jakiś związek. Tak, mają, tylko teraz pytanie, jaki? Otóż jest to wykonanie operacji przeciwnej do rekurencji. Czyli tam, gdzie rekurencja umożliwia rozwiązanie problemu w sposób rekurencyjny, tak derekursywacja polega na odwróceniu działania rekursywnego na działanie iteracyjne poprzez zwykłą pętlę czy to "while", czy to "for". Sztuka odwracania algorytmu rekurencyjnego w iteracyjny też wymaga niemałego poświęcenia intelektualnego, natomiast to też bym zaliczył do czynności niezbędnych do opanowania, aby wyróżniać się z tłumu jako przyszły programista.
PRZYKŁAD KODU ŹRÓDŁOWEGO
Ponownie zerkniemy na podsunięty przykład. Dla odmiany pokażę Wam ciąg Fibonacciego, algorytm polegający na tym, że każdy wyraz ciągu (przy założeniu, że n > 2) jest sumą dwóch poprzednich wyrazów, czyli pierwsze argumenty ciągu to: 1, 1, 2, 3, 5, 8 i tak dalej. Skonfrontujemy oba rozwiązania problemu algorytmicznego prezentując Wam przykład funkcji rekursywnej i funkcji iteracyjnej. Tak będzie najlepiej, żebyście mogli oba sposoby "postawić obok siebie". Aby zobaczyć na czym polega derekursywacja, najpierw trzeba mieć algorytm rekursywny. Proszę:
#include <stdio.h>
#define N 10
unsigned long fibonacciSequence(unsigned int n);
int main(void)
{
printf("Ciag Fibonacciego dla N rownego %d wynosi %lu.\n", N, fibonacciSequence(N));
getchar();
return 0;
}
unsigned long fibonacciSequence(unsigned int n)
{
if(n == 0)
{
return 0;
}
else if(n <= 2)
{
return 1;
}
else
{
return fibonacciSequence(n - 2) + fibonacciSequence(n - 1);
}
}Nic dodać, nic ująć. Czysta rekurencja. Ponownie zalecam wykorzystanie typów "unsigned", ponieważ omawiany ciąg również dotyczy jedynie liczb dodatnich. Przy większych wyrazach sam "int" może nie wytrzymać, więc lepiej będzie jak użyjecie typu "long". Możecie to sobie skompilować i zweryfikować prawdziwość działania. A teraz podejście iteracyjne. Normalnie, to musielibyście mocno pomyśleć jak to w pewien sposób skonwertować do innej postaci. Tym razem Was wyręczę i tak wygląda iteracyjne podejście, czyli przeprowadzona derekursywacja:
#include <stdio.h>
#define N 10
unsigned long fibonacciSequence(unsigned int n);
int main(void)
{
printf("Ciag Fibonacciego dla N rownego %d wynosi %lu.\n", N, fibonacciSequence(N));
getchar();
return 0;
}
unsigned long fibonacciSequence(unsigned int n)
{
unsigned long a = 0, b = 1;
for (unsigned int i = 2; i <= n; ++i)
{
unsigned long sum = b + a;
a = b;
b = sum;
}
return b;
}Jeśli nie pasuje nam rekurencja, mamy oto pętlę "for" i inny zapis dający nam prawie identyczne działanie. Dlaczego "prawie"? Bo rekurencja jak tłumaczyłem poprzednio "przechowuje" wszystkie osobne zmienne lokalne (parametry formalne) w celu "powrócenia" do początku i zwrócenia ostatecznego działania, a pętla po prostu robi swoje kawałek po kawałku i gdy uzna, że już wystarczy, zwraca obecny wynik i tyle, ale nie powiela żadnych zmiennych, operuje ona ciągle na tych samych, czyli 2x "unsigned long" na zewnątrz pętli jako "a" i "b", jeden "unsigned int" jako zmienna iteracyjna oraz jedna zmienna w środku pętli sumująca wyrazy ("unsigned long") i KONIEC.
Tymi wnioskami kończę dzisiejsze wypowiedzi. Rekurencja i derekursywacja nie są łatwymi rzeczami do opanowania, natomiast jeśli zrozumiecie cały sens działania, będzie to dobrze o Was świadczyło.