Pchełki VBA – Odcinek 8: rekurencja

In Pchełki VBA by xpil1 Comment

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) <enter>

Wynik: 1

Próbujemy coś większego:

? silnia(6) <enter>

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…

Dodaj komentarz

1 Komentarz do "Pchełki VBA – Odcinek 8: rekurencja"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
agnieszka_sto
Gość

Zaiste, ozywcze… :)))

wpDiscuz