Haskell/Funkcje rekurencyjne

Rekurencja

Chyba każdy program (poza "Hello world") napisany w języku imperatywnym wykorzystuje jakiegoś rodzaju pętle. Działanie pętli kończy się, gdy zostanie spełniony (lub nie spełniony) pewien warunek. Wiąże się to ze zmianą wartości zmiennej będącej licznikiem pętli. Jak wiadomo, zmiana wartości zmiennej w Haskellu nie jest możliwa, a więc zastosowanie pętli staje się również niemożliwe. Wszystkie zadania, które w językach imperatywnych są wykonywane w pętli, w Haskellu można zrealizować wykorzystując rekurencję.

Silnia

Wspomnianym już wcześniej przykładem, który doskonale obrazuje działanie rekurencji, jest funkcja obliczająca wartość silni z danej liczby. Zadaniem funkcji jest pomnożenie wszystkich liczb naturalnych mniejszych lub równych danej liczbie. Na przykład silnia z liczby 5 to 5 * 4 * 3 * 2 * 1 = 120.

Aby zobrazować działanie rekurencji przyjrzyjmy się silni z dwóch kolejnych liczb:

silnia 5 =  5 * 4 * 3 * 2 * 1
silnia 4 =      4 * 3 * 2 * 1

Jak widać silnia z liczby 5 jest równa silni z liczby 4 pomnożonej przez liczbę 5.

silnia 5 = 5 * silnia 4

Można uogólnić ten zapis w następujący sposób:

silnia n = n * silnia (n-1)

Rekurencyjna definicja funkcji potrzebuje przynajmniej jednego przypadku bazowego (nie rekurencyjnego), oraz przypadku ogólnego (rekurencyjnego). Jeśli funkcja rekurencyjna nie ma zdefiniowanego przypadku bazowego jej działanie nigdy się nie zakończy. Powyżej zdefiniowany został przypadek ogólny. Pozostało więc jeszcze zdefiniowanie przypadku bazowego. Będzie nim obliczenie wartości silni dla liczby 0. Zastosowanie ogólnej definicji dla liczby 0 wyglądałoby następująco:

silnia 0 = 0 * silnia (-1)

Zapis ten jest błędny, ponieważ nie możliwe jest obliczenie silni z liczby ujemnej. Zgodnie z definicją silni:

silnia 0 = 1

Pełna definicja funkcji wyznaczającej silnię jest więc następująca:

silnia 0 = 1
silnia n = n * silnia (n-1)

Rekurencyjne mnożenie dwóch liczb

Z pewnością każdy programista, zarówno piszący w językach imperatywnych jak i funkcyjnych, aby pomnożyć dwie liczby a i b napisze po prostu a * b. Mnożenie można jednak zapisać w sposób rekurencyjny. Wykorzystamy do tego definicję podawaną dzieciom w szkole podstawowej. Aby pomnożyć liczbę a razy liczbę b, weź liczbę a i dodaj do siebie b razy. Na przykład 6*4 = 6+6+6+6. Podobnie jak w poprzednim przykładzie, zapiszmy dwa przykłady mnożenia.

6 * 4 = 6 + 6 + 6 + 6
6 * 3 =     6 + 6 + 6 

Tak samo jak w przypadku silni zapis ten możemy uogólnić:

a * b = a + a * (b-1)

Pozostaje jeszcze zdefiniowanie przypadku bazowego. Będzie to mnożenie przez liczbę 0. Dowolna liczba pomnożona przez 0 daje 0.

a * 0 = 0

Funkcja pomnoz zapisana w Haskellu będzie więc wyglądać następująco:

pomnoz a 0 =  0
pomnoz a b =  a + pomnoz a (b-1)