Dziś o rekurencji.
Czym jest rekurencja? To taki rodzaj definicji (bądź funkcji), która odwołuje się do samej siebie. Przy czym, musi być dodatkowo zdefiniowany jakiś stan brzegowy ("początkowy") w celu uniknięcia zapętlenia definicji w nieskończoność.
Dobrym przykładem takiej nieskończonej rekurencji jest trójkąt Sierpińskiego. Żeby przerobić zwykły trójkąt równoboczny na trójkąt Sierpińskiego, należy podzielić go trzema odcinkami na cztery identyczne trójkąty równoboczne, potem wyciąć środkowy, a pozostałe 3 przerobić na trójkąty Sierpińskiego. Czyli każdy z nich podzielić na cztery mniejsze, wyciąć środkowy i tak dalej. Efekt będzie, z grubsza, o taki.
Trójkąt Sierpińskiego to przykład rekurencji nieskończonej. W programowaniu komputerów mamy jednak do czynienia z rekurencją skończoną (komputery nie radzą sobie za dobrze z nieskończonością, podobnie zresztą jak człowiek). Skończoność rekurencji zapewniamy poprzez dodadnie warunku jej zakończenia.
Dobrym przykładem będzie tutaj silnia.
Silnię z zadanej liczby naturalnej N definiuje się jako iloczyn wszystkich liczb naturalnych od 1 do N.
Ponadto, definicja mówi explicite, że silnia z 0 wynosi 1.
0! = 1
1! = 1
2! = 1 * 2 = 2
3! = 1 * 2 * 3 = 6
4! = 1 * 2 * 3 * 4 = 24
I tak dalej. Jak łatwo zauważyć, silnię w prosty sposób można zdefiniować za pomocą rekurencji:
Silnia z N równa się 1 dla N równego 1. Silnia z N równa się silni z N-1 przemnożonej przez N, dla N większego od 1.
Proste?
Niekoniecznie?
No to popatrzmy:
1! = 1
2! = 1! * 2
3! = 2! * 3
4! = 3! * 4
...
100! = 99! * 100
Zgadza się?
Spróbujmy teraz zaprząc tę rekurencyjną zasadę do wyliczenia silni za pomocą VBA. Od razu uprzedzam, że ponieważ jest to pchełka, nie będziemy bawić się w jakieś zaawansowane algorytmy, liczące silnie z liczb stucyfrowych - napiszemy sobie najprostszy przypadek, który będzie liczył silnię tak długo, aż wyjdzie poza dopuszczalny zakres Long (Long to w VBA typ całkowitoliczbowy 32-bitowy, ze znakiem) - a więc maksymalna możliwa wartość to 2^31-1=2147483647 (ciut ponad dwa miliardy).
Ponieważ silnia rośnie dość szybko, okaże się, że będziemy w stanie policzyć silnię z dwunastu (która wynosi coś z pół miliarda), ale już nie z trzynastu (ponad sześć miliardów, a więc poza dopuszczalnym zakresem typu Long).
OK, zaczynamy. Alt-F11, nowy moduł, wklejamy kod:
Option Explicit
Public Function silnia(n As Integer) As Long
On Error Resume Next
If n = 1 Then
silnia = 1
Else
silnia = n * silnia(n - 1)
End If
If Err.Number <> 0 Then silnia = 0
On Error GoTo 0
End Function
Przechodzimy do okna poleceń natychmiastowych (Ctrl-G) i wpisujemy:
? silnia(1)
Wynik: 1
Próbujemy coś większego:
? silnia(6)
720
Faktycznie, 1*2*3*4*5*6=720
? silnia(10)
3628800
Zgadza się, 1*2*3*4*5*6*7*8*9*10=3628800
? silnia(13)
0
Ano, zgodnie z zapowiedzią, funkcja się zesrała przy trzynastce. No i fajnie.
Teraz część opisowa - osoby, które jeszcze nie zasnęły, a bardzo by chciały zasnąć, proszone są o pozostanie na swoich miejscach.
Public Function silnia(n As Integer) As Long
Deklarujemy funkcję silnia z jednym parametrem wejściowym n typu Integer (całkowitoliczbowy, 16-bitowy ze znakiem, czyli max 32767 - a i tak zadziała tylko do 12) oraz z parametrem wyjściowym typu Long (całkowitoliczbowy, 32-bitowy ze znakiem).
On Error Resume Next
Ponieważ spodziewany się błędu przepełnienia, od razu zabezpieczamy się przed jego wystąpieniem - po szczegóły działania dyrektywy "On Error" kieruję do poprzedniego odcinka.
If n = 1 Then
silnia = 1
Else
silnia = n * silnia(n - 1)
End If
Tutaj jest samo gęste, czyli właściwe obliczenie. Jeżeli n=1 to zwracamy jedynkę, w przeciwnym wypadku zwracamy silnię z n-1 przemnożoną przez n.
If Err.Number <> 0 Then silnia = 0
Tutaj wstawiamy protezę dla n>12 = funkcja zwróci 0 (które jest nieprawidłowym wynikiem, ale dzięki temu obsługujemy błąd)
On Error GoTo 0
Resetujemy obsługę błędu.
Ot i cała filozofia.
No a teraz pytanie, dałoby się to samo ale bez rekurencji?
A dlaczego bez? Przecież z rekurencją działa elegancko.
Ano, z jednej strony owszem, działa. Z drugiej jednak strony, rekurencja nie jest zalecana w "porządnych" projektach software-owych, ponieważ jest ona dość zasobożerna. Zauważmy, że w naszym przypadku funkcja silnia woła samą siebie kilka (-naście) razy - za każdym razem musi ona gdzieś zapamiętać swój aktualny stan (a więc, wartości wszystkich zmiennych oraz punkt powrotu) - akurat tych kilkanaście iteracji nam komputera nie ubije, ale możemy sobie wyobrazić o wiele bardziej złożone sytuacje, gdzie funkcja wywoła się kilkaset albo kilka milionów razy - i każde jedno wywołanie zajmie odrobinę pamięci.
Dlatego też pisząc "porządne" programy starajmy się unikać rekurencji.
Dlaczego więc w ogóle o niej piszę?
Ano, z dwóch przyczyn. Po pierwsze, algorytm zapisany rekurencyjnie jest zwykle o wiele prostszy do zrozumienia i krótszy w zapisie. A po drugie, czasami można pozostawić rozwiązanie rekurencyjne - o ile tylko wiemy na pewno, że nie rozpuchnie nam się ono kiedyś w jakiegoś pożeracza pamięci. Dość dobrym przykładem może tu być analiza węzłów XML - wiemy na pewno, że plik XML ma skończoną wielkość, więc można go potraktować rekurencją bez większych obaw.
Już dawno temu udowodniono, że każde rozwiązanie rekurencyjne da się zapisać w postaci nierekurencyjnej.
Spróbujmy więc naszą pchełkę wyleczyć z rekurencji:
Public Function silnia2(n As Integer) As Long
Dim i As Integer, w As Long
w = 1
On Error Resume Next
For i = 1 To n
w = w * i
If Err.Number <> 0 Then w = 0
Next i
On Error GoTo 0
silnia2 = w
End Function
Wreszcie wersja najbardziej leniwa:
Public Function silnia3(n As Integer) As Long
silnia3 = Switch(n = 1, 1, n = 2, 2, n = 3, 6, n = 4, 24, n = 5, 120, n = 6, 720, n = 7, 5040, n = 8, 40320, n = 9, 362880, n = 10, 3628800, n = 11, 39916800, n = 12, 479001600, True, 0)
End Function
Analizę dwóch ostatnich pchełek pozostawiam Czytelnikowi, zaraz po tym jak się obudzi.
Halo, pobudka!
Halo...
Zaiste, ozywcze… :)))