Dawno temu u Jasona, padł temat rekurencji. Dzisiaj rozbudujemy sobie ten wątek o kontynuację opisując Wam na czym polega rekurencja ogonowa. Popatrzymy sobie na przykład obliczania silni dodając do niej "upgrade" rekurencyjny ;)!
| Tweet |
REKURENCJA OGONOWA NIE MUSI WRACAĆ DO SAMEGO POCZĄTKU...
...i to jest kwintesencja tego tematu. Przy standardowej rekurencji (jak dobrze wiem o tym ja i wszyscy ci, którzy raczyli przeczytać mój artykuł), po dojściu do przypadku podstawowego (warunku przerywającego pętlę) musi ona wrócić do pierwszego wywołania funkcji, niezależnie od głębokości stosu wywołań. Kiedy mamy do czynienia z rekurencją ogonową (ang. tail recursion), to gdy dojdzie do przerwania pętli, zwracany jest wynik i żegna się ze stosem natychmiast!!! Nie musi wracać do samego początku. Czyż to nie cudowne?
KOD ŹRÓDŁOWY
Wrócimy sobie do przykładu sprzed trzech lat kiedy to opisywałem, jak można zaprogramować silnię rekurencyjnie. Teraz popatrzymy sobie jak wygląda rekurencja ogonowa i czym się różni od tej "normalnej". Kodzik w języku C:
#include <stdio.h>
#define N 10
unsigned long factorial(unsigned int n, unsigned long result);
int main(void)
{
printf("%d! = %u\n", N, factorial(N));
getchar();
return 0;
}
unsigned long factorial(unsigned int n, unsigned long result)
{
if(n <= 1)
{
return result;
}
else
{
return factorial(n – 1, result*n);
}
}Przypomnijmy sobie postać funkcji wyliczającej silnię rekurencyjnie w sposób tradycyjny:
unsigned long factorial(unsigned int n)
{
if(n <= 1)
{
return 1;
}
else
{
return n*factorial(n - 1);
}
}Czy potraficie dostrzec jedną niezbyt subtelną różnicę? Dodatkowy parametr formalny!!! To "result" przechowuje aktualny wynik działania funkcji i właśnie dzięki niemu rekurencja ogonowa może obejść to powracanie do początku stosu. Taka dodatkowa zmienna jest nazywana fachowo "akumulatorem", gdyż robi dosłownie za "składzik" wartości aktualnej. Poza tą modyfikacją, to widzimy zmianę "return 1" na zwracanie aktualnej wartości ("return result"), a w rekursywnym wywołaniu modyfikujemy nasz rezultat co każdą iterację ("result*n"). A pozostała część jest taka sama.
Jeśli nie do końca kumasz co nam to daje, popatrz na to wizualnie. Swoim kolegom zawsze daję porównanie rekurencji "zwykłej" do ogonowej, jak wchodzenie na "piramidkę" do wchodzenia po schodkach, a wchodzenie w obu przypadkach jest bez zawracania. W piramidce jest spadek w drugą stronę (powrót do początku stosu), a po schodkach idzie się do góry i tam droga się kończy (rekurencja nie musi wracać).
Mógłbym pisać mądrze i długo, ale skwituję to schludnie i krótko: jeśli rozumiesz jak funkcjonuje rekurencja ogonowa, to tak jakbyś osiągnął wyższy poziom w grze RPG ;). Na dzisiejszym temacie kończę uzupełnianie materiału o programowaniu ogólnie, już wystarczy :D!