Rekursja albo rekurencja (ang. recursion, z łac. recurrere, przybiec z powrotem) to w programowaniu i w matematyce odwoływanie się (np. funkcji lub definicji) do samej siebie. Np. poniższa definicja ciągu Fibonacciego jest rekurencyjna:
\[\mathrm{fib}(0) = 0 \]
\[\mathrm{fib}(1) = 1 \]
\[\mathrm{fib}(n) = \mathrm{fib}(n-1) + \mathrm{fib}(n-2) \], dla \[n \ge 2 \]
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 \[\mathrm{fib}(4) \] wygląda tak: \[\mathrm{fib}(4)=\mathrm{fib}(3)+\mathrm{fib}(2)=(\mathrm{fib}(2)+\mathrm{fib}(1)) \]
+ \[(\mathrm{fib}(1)+\mathrm{fib}(0))=((\mathrm{fib}(1)+\mathrm{fib}(0))+\mathrm{fib}(1))+(\mathrm{fib}(1)+\mathrm{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 resztę z dzielenia n przez k).
Rekursja jest podstawową techniką wykorzystywaną w funkcyjnych językach programowania.
Należy jednak zachować ostrożność przy używaniu rekursji w rzeczywistych programach. Jeśli program nie jest w rzeczywistości rekurencyjny, to rekursja może dramatycznie zwiększyć złożoność obliczeniową. Ponadto rekursja prawie zawsze zwiększa pamięciowe zapotrzebowanie programu. Np. W powyższym przykładzie obliczania \[\mathrm{fib}(4) \] niepotrzebnie jest dwukrotnie obliczana wartość \[\mathrm{fib}(2) \]. Takie problemy nie pojawiają się przy drugim z przykładów. Niezaprzeczalną zaletą rekursji jest prostota programów, które z niej korzystają.
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.
Prezentowane filmy poczhodzą z serwisu YouTube, portal zgapa.pl nie jest ich autorem i nie ponosi odpowiedzialności za ich treści.