OCaml/Rekurencja i iteracje

Z Wikibooks, biblioteki wolnych podręczników.

W językach funkcyjnych bardzo naturalną techniką jest rekurencja. Tworząc funkcje rekurencyjne dodajemy do definicji słówko "rec", bez niego funkcja nie będzie mogła wywoływać samej siebie. Dla przykładu prostą pętlę można rozwiązać w następujący sposób:

# let rec loop i =
	print_endline "Looping!";
	if (i>1) then loop (i-1)
;;
val loop : int -> unit = <fun>
# loop 3;;
Looping!
Looping!
Looping!
- : unit = ()

Funkcje "tail-recursive" to taki przypadek rekurencyjnych funkcji, w których ponowne wejście do funkcji znajduje się na ich końcu. Caml optymalizuje wszystkie takie przypadki generując assembler lub kod bajtowy w postaci normalnej iteracji. Dlatego stosowanie rekurencji do zapętlania programu nie jest obciążone żadnym większym zużyciem pamięci ani czasem potrzebnym na wywołanie funkcji jakby to miało miejsce w języku C i podobnych.

Istnieją również implementacje pętli for i while, lecz zazwyczaj się z nich nie korzysta. W Camlu nie istnieją wyrażenia break i continue. Jeśli jednak zajdzie potrzeba przerwania rekurencji lub pętli używany jest wyjątek Exit (zdefiniowany w Pervasives). W modułach zdefiniowane jest również wiele "iteratorów" -- funkcji służących do wykonywania cyklicznych operacji na np. elementach list, które opiszemy później.

Rekurencji ciąg dalszy:

# let rec silnia n =
	if n = 0 then 1 else n * silnia (n - 1);;
 
# let rec fib n =
	if (n < 2) then
		1
	else	fib (n - 1) + fib (n - 2);;
val fib : int -> int = <fun>

Pierwsza funkcja, jak każdy się pewnie domyślił, pozwala obliczyć silnię z n. Druga zwraca n-ty wyraz ciągu Fibonacciego (licząc od zera). Widzimy tu, wiele opisanych wcześniej elementów. Ostatnie wyrażenie w "bloku kodu" zwraca wartość, oraz że każdy blok posiada jakiś typ. Jeśli np. w else zechcielibyśmy zwrócić typ float (zamiast "1" umieszczając tam "1.0") otrzymamy informację, że używane przez nas wyrażenie o typie float, jest używane jako int.

Funkcja fib nie jest funkcją "tail-recursive", dlatego możemy ją efektywniej napisać stosując funkcję pomocniczą, stworzoną za pomocą konstrukcji let ... in

# let fib x = 
	(* Funkcja pomocnicza *)
	let rec loop a b i =
		if i <= 2 then
			b
		else	let next = a + b in
			loop b next (i-1)
	in
 
	loop 1 1 x (* Jej wywołanie *)
;;
val fib : int -> int = <fun>
 
(* Wspomniana pętla for. Wyświetla początek 
 * ciągu fibonacciego: *)
# for i = 1 to 10 do
	print_int (fib i);
	print_newline ();
  done;;
1
1
2
3
5
8
(...)
- : unit = ()
(* Wyrażenie w pętli "for" musi zwracać typ unit. *)