Rekurencja:
w terminach programistycznych funkcję rekurencyjną można zdefiniować jako funkcję, która wywołuje się bezpośrednio lub pośrednio.
używając algorytmu rekurencyjnego, pewne problemy można dość łatwo rozwiązać. Towers of Hanoi (Toh) jest jednym z takich ćwiczeń programowania. Spróbuj napisać iteracyjny algorytm dla TOH. Ponadto każdy program rekurencyjny może być napisany metodami iteracyjnymi (zob. struktury danych Lipschutza).
matematycznie rekurencja pomaga w łatwym rozwiązaniu kilku zagadek.,
na przykład rutynowe pytanie o wywiad,
w partii N osób, każda osoba uściśnie sobie rękę ze sobą tylko raz. W sumie ile uścisków dłoni by się zdarzyło?
rozwiązanie:
można go rozwiązać na różne sposoby, wykresy, rekurencje itp. Zobaczmy, jak rekurencyjnie można to rozwiązać.
jest N osób. Każda osoba podaje sobie rękę tylko raz. Biorąc pod uwagę n-tą osobę, (s) musi podać rękę (N-1) osobom. Teraz problem zredukowano do małych instancji (N-1) osób. Przyjmując TN jako całkowity uścisk dłoni, można go sformułować rekurencyjnie.,
TN = (N-1) + TN-1
rozwiązując go rekurencyjnie otrzymujemy szereg arytmetyczny, który można oszacować na N (N-1) / 2.
ćwiczenie: w partii N par tylko jedna płeć (zarówno męska, jak i żeńska) może uścisnąć dłoń każdej z nich. Ile by się zdarzyło?
Zwykle programy rekurencyjne skutkują słabą złożonością czasową. Przykładem jest seria Fibonacciego. Złożoność czasowa obliczenia n-tej liczby Fibonacciego przy użyciu rekurencji wynosi około 1,6 N. oznacza to, że ten sam komputer zajmuje prawie 60% więcej czasu dla następnej liczby Fibonacciego. Rekurencyjny algorytm Fibonacciego ma zachodzące na siebie podproblemy., Istnieją inne techniki, takie jak programowanie dynamiczne, aby poprawić takie nakładające się algorytmy.
jednak niewiele algorytmów (np. sortowanie scalające, sortowanie szybkie itp.) powoduje optymalną złożoność czasową przy użyciu rekurencji.
przypadek podstawowy:
jednym z krytycznych wymagań funkcji rekurencyjnych jest punkt zakończenia lub przypadek podstawowy. Każdy program rekurencyjny musi mieć wielkość liter, aby upewnić się, że funkcja zostanie zakończona. Brak przypadku podstawowego skutkuje nieoczekiwanym zachowaniem.,
różne sposoby zapisu funkcji rekurencyjnych
funkcja wywołująca samą siebie: (Direct way)
większość z nas zna przynajmniej dwa różne sposoby zapisu programów rekurencyjnych. Poniżej znajduje się kod towers of Hanoi. Jest to przykład połączenia bezpośredniego.

Wyjście:

Move the disk 1 from S to DMove the disk 2 from S to AMove the disk 1 from D to AMove the disk 3 from S to DMove the disk 1 from A to SMove the disk 2 from A to DMove the disk 1 from S to D

złożoność czasowa TOH może być obliczona przez sformułowanie liczby ruchów.
musimy przenieść pierwsze N-1 dyski ze źródła do pomocniczego i z pomocniczego do docelowego, tzn. pierwsze N-1 dyski wymagają dwóch ruchów. Jeszcze jedno przesunięcie ostatniego dysku ze źródła do miejsca docelowego., Matematycznie można ją definiować rekurencyjnie.
MN = 2MN-1 + 1.
Możemy łatwo rozwiązać powyższą relację rekurencyjną (2N-1), która jest wykładnicza.
Rekurencja za pomocą wzajemnego wywołania funkcji: (sposób pośredni)
wywołanie pośrednie. Chociaż funkcja jest najmniej praktyczna, może wywołać inną funkcję, która inturn wywołuje poprzednią funkcję. W tym przypadku obie funkcje powinny mieć przypadek podstawowy.
Programowanie defensywne:
możemy połączyć techniki kodowania defensywnego z rekurencją, aby zapewnić pełną funkcjonalność aplikacji., Zwykle programowanie rekurencyjne nie jest dozwolone w aplikacjach o znaczeniu krytycznym dla bezpieczeństwa, takich jak sterowanie lotem, monitorowanie zdrowia itp. Można jednak użyć statycznej techniki liczenia, aby uniknąć niekontrolowanych wywołań (nie w systemach krytycznych dla bezpieczeństwa, może być stosowany w miękkich systemach czasu rzeczywistego).

głębokość wywołania zależy od rozmiaru ramki stosu funkcji i maksymalnego rozmiaru stosu.
Recursion using function pointers: (Indirect way)
Recursion can also implemented with function pointers. Przykładem jest obsługa sygnału w systemach reklamacyjnych POSIX., Jeśli funkcja obsługi spowoduje wywołanie tego samego Zdarzenia, z powodu którego zostanie wywołana, funkcja uruchomi się ponownie.