REKURENCJA


 REKURENCJA inaczej REKURSJA

Jest to bardzo efektowna i efektywna metoda, polegająca na wywołaniu procesu samego przez siebie i rozłożenia problemu na podproblemy elementarne. Jednak niedostatecznie przemyślany warunek zakończenia takiego procesu może prowadzić do nieskończonych wywołań i zawieszeniem się programu z powodu przepełnienia stosu (stack overflow). Programy z zastosowaniem rekurencji wymagają też często dużej ilości pamięci operacyjnej. W podejściu rekurencyjnym do postawionemu problemu stosuje się metodę „dziel i zwyciężaj”.


„Dziel i zwyciężaj" (ang. divide and conquer) – jedna z głównych metod projektowania algorytmów w informatyce, prowadząca do bardzo efektywnych rozwiązań. Nazwa pochodzi od łacińskiej sentencji dziel i rządź (łac. divide et impera). W strategii tej problem dzieli się rekurencyjnie na dwa lub więcej mniejszych podproblemów tego samego (lub podobnego) typu, tak długo, aż fragmenty staną się wystarczająco proste do bezpośredniego rozwiązania. Z kolei rozwiązania otrzymane dla podproblemów scala się, uzyskując rozwiązanie całego zadania.

[WIKIPEDIA]

Funkcje rekurencyjne są to takie funkcje, które wywołują same siebie.


 SILNIA

Nazwa funkcji: sil
0! = 1, 1!=1, 2!=2, 3!=6, 4!=24, … 10!=3628800


 POTĘGA - wykładnik naturalny

Nazwa funkcji: pot
5550=1, 20181=2018, 210=1024, 106=1000000


 POTĘGA - wykładnik całkowity

Funkcja pot_c wykorzystuje poprzednią funkcję pot. W programie muszą wystąpić obie.
210=1024, 2-3=0.125, 0.05-6=64000000


 ALGORYTM EUKLIDESA

Nazwa funkcji: nwd
nwd(168,189)=21,   nwd(10090, 6054)=2018


 CIĄG FIBONACCIEGO

Nazwa funkcji: fib
F1=1, F3=2, F17=1597, F40=102334455