Rekurencja
Z Wikipedii
Rekurencja albo rekursja (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. Wbrew próbom rozróżnienia terminów[potrzebne źródło] rekursja i rekurencja w rzeczywistości słowa te mają identyczne znaczenie[potrzebne źródło].
W logice wnioskowanie rekurencyjne opiera się na założeniu istnienia pewnego stanu początkowego oraz zdania (lub zdań) stanowiącego podstawę wnioskowania (przy czym aby cały dowód był poprawny zarówno reguła jak i stan początkowy muszą być prawdziwe). Istotą rekurencji jest tożsamość dziedziny i przeciwdziedziny reguły wnioskowania, wskutek czego wynik wnioskowania może podlegać tej samej regule zastosowanej ponownie.
Na prostym przykładzie:
reguła: każdy ojciec jest starszy od swojego syna; każdy ojciec jest czyimś synem
stan początkowy: jestem 22-letnim mężczyzną
teza: ojciec ojca mojego ojca jest starszy ode mnie
dowód:
- mój ojciec jest starszy ode mnie
- mój ojciec jest czyimś synem
- ojciec mojego ojca jest starszy od mojego ojca
- ojciec mojego ojca jest czyimś synem
- itd.
Na przykładzie zastosowań matematycznych poniższa definicja ciągu Fibonacciego jest rekurencyjna:
- fib(0) = 0
- fib(1) = 1
- fib(n) = fib(n − 1) + fib(n − 2), dla
gdyż definiuje funkcję odwołując się w definicji do niej samej.
Każda definicja rekurencyjna potrzebuje przynajmniej jednego przypadku bazowego (nie rekurencyjnego), w tym przypadku są to wartości dla 0 i 1. W przeciwnym wypadku nigdy się nie zakończy.
Dla przykładu, obliczenie fib(4) wygląda następująco:
fib(4) = fib(3) + fib(2) = (fib(2) + fib(1)) + (fib(1) + fib(0)) = ((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0)) = ((1 + 0) + 1) + (1 + 0) = 3
Innym przykładem jest wyliczanie największego wspólnego dzielnika za pomocą algorytmu Euklidesa:
- gcd(0,n)=n,
- gcd(k,n)=gcd(n mod k, k) dla k>0 (n mod k oznacza tu resztę z dzielenia n przez k).
lub inaczej:
Rekurencja jest podstawową techniką wykorzystywaną w funkcyjnych językach programowania.
Należy jednak zachować ostrożność przy używaniu rekurencji w rzeczywistych programach. Jeśli program nie jest w rzeczywistości rekurencyjny, to rekurencja może dramatycznie zwiększyć złożoność obliczeniową. Ponadto rekurencja zawsze zwiększa pamięciowe zapotrzebowanie programu (chyba że zostanie użyta możliwa w pewnych przypadkach optymalizacja zwana rekursją ogonową), gdyż wymaga ona zapamiętania m.in. adresów powrotu, pozwalających programowi "zorientować się" do którego miejsca ma wrócić po zakończeniu jednego z wywołań rekurencyjnych. Inną częstą wadą rekurencji jest kompletnie niezależne rozwiązywanie podproblemów, tak, że czasem jeden problem jest rozwiązywany w kilku miejscach rozwinięcia rekurencji, np. w powyższym przykładzie obliczania fib(4) niepotrzebnie jest dwukrotnie obliczana wartość fib(2) (porównaj: programowanie dynamiczne). Takie problemy nie pojawiają się przy drugim z przykładów. Niezaprzeczalną zaletą rekurencji jest przejrzystość programów, które z niej korzystają.
[edytuj] Przykłady
- wielomiany Hermite'a
- wielomiany Legendre'a
- algorytm Euklidesa
- ciąg Fibonacciego
- definicja silni
- symbol Newtona