W programowaniu: moduł programu lub podprogram, który wywołuje sam siebie w celu wykonania operacji iteracyjnej; innymi słowy, czyste wyrażenie powtarza się, aby osiągnąć znacznie bardziej złożoną operację.
Zasadę rekurencji ilustrują liczby Fibonacciego, szereg liczb, w którym pierwsze dwa wyrazy to 1; kolejne wyrazy podaje się sumując dwa poprzednie wyrazy (1,1, 2, 3, 5, 8,13, 21, 34, 55, 89, 144, itd.). Liczby Fibonacciego można generować za pomocą następującego równania, o ile n jest większe niż 2: Fibonacci («) = Fibonacci (« – 1) + Fibonacci (n – 2).
Technipages wyjaśnia rekurencję
Rekurencja to metoda rozwiązywania problemów w programowaniu, w której problem jest rozbijany na mniejsze jednostki zadań i rozwiązywany indywidualnie. Tak więc pierwsze rozwiązanie jest zależne od mniejszych rozwiązań, z których pochodzi mniej drobnych problemów. Rekurencja pomaga w rozwiązywaniu problemów, ponieważ pytanie jest rozwiązywane na jego warunkach.
Najlepiej ilustrują to rosyjskie lalki Matrioszki, czyli zestaw lalek zamkniętych w większej lalce; każdy kawałek lalki jest bezpośrednią repliką następnej lub poprzedniej lalki, z wyjątkiem mniejszych. Tak więc każda lalka jest małą lub bardziej znaczącą wersją drugiej. Programowanie rekurencyjne opiera się na tej zasadzie, w której problem jest rozwiązywany poprzez rozbicie go na mniejsze problemy.
Rekurencję można prześledzić wstecz do 1958 roku, John McCarthy był pierwszym, który zastosował zasadę rekurencji w programowaniu i można to znaleźć w jego pracy nad LISP-em. LISP był pierwszym językiem programowania, który zawierał funkcje rekurencyjne, takie jakie mamy dzisiaj. Praca McCarthy'ego została zainspirowana pracami Alonzo Church, które były dwie dekady wcześniej. Godne uwagi wzmianki związane z rekurencją można również datować na pracę Dedekinda na temat liczb naturalnych w 1888 roku. Rozsa Peter przedstawiła funkcje rekurencyjne w 1932 na Międzynarodowym Kongresie Matematyków w Zurychu w 1932.
Typowe zastosowania rekurencji
- Rekurencja pomaga w rozwiązywaniu problemów, ponieważ rozwiązuje problem na jego warunkach, od rozbicia problemu na mniejsze problemy
- Lepszy sposób na rozwiązanie problemów byłby przez Rekurencja bo poszerza perspektywę na dany problem
- w Rekurencja, nowy zestaw problemów jest sobie nawzajem replikami, a każdy z nich jest rozwiązywany osobno.
Typowe nadużycia rekurencji
- Rekurencja nie rozwiązuje problemów, mimo że problem jest podzielony na rozwiązywanie na mniejszą skalę
- Rekurencja tylko upraszcza problem, a nie rozwiązuje go.