Co to jest rekurencja?

Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu i w matematyce odwoływanie się np. 
funkcji lub definicji do samej siebie.

Każda definicja rekurencyjna potrzebuje przynajmniej jednego przypadku bazowego (nie rekurencyjnego).

Przyjrzyjmy się definicji silni:

n! = 1               dla n=0
n! = n · (n - 1)!    dla n>0

Jak widać silnia jest zdefiniowana za pomocą silni, a przypadkiem bazowym jest 0! = 1.

Mamy więc do czynienia z definicją rekurencyjną.

Co to jest funkcja rekurencyjna?

Funkcja rekurencyjna to funkcja, która w swojej definicji odwołuje się sama do siebie.

Func nazwa_funkcji_rekurencyjnej(parametry)
             ...
   ...nazwa_funkcji_rekurencyjnej(parametry)
             ...
EndFunc

Tworzymy funkcję rekurencyjną

Uzbrojeni w tą wiedzę spróbujmy stworzyć w AutoIt funkcję rekurencyjną obliczającą silnię, w oparciu o jej rekurencyjną definicję:

Func silnia($n)
   if $n=0 Then Return 1.0  ;przypadek bazowy dla n=0, podano 1.0, dzięki temu
                            ;nie przekroczymy szybko zakresu liczb całkowitych
   Return $n*silnia($n-1)   ;rekurencyjna definicja silni
EndFunc

Dla porównania ta sama funkcja napisana w sposób nierekurencyjny:

Func silnia($n)
   Local $i, $s=1.0            ;inicjacja zmiennych, $s jako zmiennoprzecinkowej
   If $n=0 Then Return 1       ;przypadek dla n=0
   For $i=1 to $n              ;obliczenia w pętli For ... Next
      $s=$s*$i
   Next
   Return $s                   ;zwracana wartość silni dla przypadku ogólnego
EndFunc

Nietrudno zauważyć, że rekurencyjna definicja funkcji jest o wiele krótsza i bardziej przejrzysta. Nie używa też żadnych wewnętrznych zmiennych.

UWAGA:

Stosowanie rekurencji należy ograniczyć do rozwiązania problemów z natury rekurencyjnych (tak jak ten w powyższym przykładzie).

W innych przypadkach rekurencja używana "na siłę" może dramatycznie zwiększyć złożoność obliczeniową programu.

Ponadto rekurencja zawsze zwiększa pamięciowe zapotrzebowanie programu.

Ilość wywołań rekurencyjnych funkcji jest ograniczona przez możliwość przepełnienia stosu, na którym AutoIt odkłada adres powrotu z każdego wywołania.

Jeżeli takie niebezpieczeństwo wystąpi to wykonanie programu zostanie automatycznie przerwane.

Ćwiczenia

1. Napisać funkcję rekurencyjną sumującą liczby całkowite w przedziale od m do n (m i n podawane jako parametry).

Funkcja powinna działać prawidłowo także dla liczb ujemnych, oraz niezależnie od kolejności podanych parametrów.

Jeżeli podamy jeden parametr to sumowanie powinno być od zera lub do zera (dla liczb ujemnych).

2. Napisać rekurencyjną funkcję obliczającą liczbę e. Funkcja ta powinna korzystać z rekurencyjnej funkcji silna zdefiniowanej w powyższym przykładzie.

Skorzystać z rozwinięcia w szereg e = 1 + 1/1! + 1/2! + ... + 1/n! + ... (graniczna wartość n podawana jako parametr).

(dla sprawdzenia przybliżona wartość e = 2.718281828459...)

Przykładowe rozwiązania: AutoIt/Ćwiczenia dla zaawansowanych - przykładowe rozwiązania