Rekurencja (informatyka) - Recursion (computer science)

Drzewo stworzone przy użyciu języka programowania Logo i oparte w dużej mierze na rekurencji. Każda gałąź może być postrzegana jako mniejsza wersja drzewa.

W informatyce , rekurencja jest metodą rozwiązywania problemów, gdzie rozwiązanie zależy od rozwiązań mniejszych wystąpień tego samego problemu. Takie problemy można ogólnie rozwiązać za pomocą iteracji , ale wymaga to zidentyfikowania i zindeksowania mniejszych instancji w czasie programowania. Rekurencja rozwiązuje takie problemy rekurencyjne za pomocą funkcji, które wywołują się z własnego kodu. Podejście to można zastosować do wielu rodzajów problemów, a rekurencja jest jedną z głównych idei informatyki.

Siła rekurencji tkwi ewidentnie w możliwości zdefiniowania nieskończonego zbioru obiektów za pomocą skończonego zdania. W ten sam sposób nieskończoną liczbę obliczeń można opisać za pomocą skończonego programu rekurencyjnego, nawet jeśli ten program nie zawiera wyraźnych powtórzeń.

—  Niklaus Wirth , Algorytmy + Struktury danych = Programy , 1976

Większość języków programowania komputerowego obsługuje rekursję, umożliwiając funkcji wywoływanie siebie z własnego kodu. Niektóre funkcjonalne języki programowania (na przykład Clojure ) nie definiują żadnych konstrukcji pętli, ale polegają wyłącznie na rekursji w celu wielokrotnego wywoływania kodu. W teorii obliczalności zostało udowodnione, że te tylko rekurencyjne języki są zupełne Turinga ; oznacza to, że są tak samo potężne (mogą być używane do rozwiązywania tych samych problemów) jak języki imperatywne oparte na strukturach kontrolnych, takich jak whilei for.

Wielokrotne wywoływanie funkcji z jej wnętrza może spowodować, że stos wywołań będzie miał rozmiar równy sumie rozmiarów wejściowych wszystkich zaangażowanych wywołań. Wynika z tego, że w przypadku problemów, które można łatwo rozwiązać za pomocą iteracji, rekursja jest ogólnie mniej wydajna , a w przypadku dużych problemów podstawowe znaczenie ma stosowanie technik optymalizacji, takich jak optymalizacja funkcji ogona .

Funkcje i algorytmy rekurencyjne

Powszechną taktyką programowania komputerowego jest podzielenie problemu na podproblemy tego samego typu co oryginał, rozwiązanie tych podproblemów i połączenie wyników. Jest to często określane jako metoda dziel i zwyciężaj ; w połączeniu z tabelą przeglądową, która przechowuje wyniki wcześniej rozwiązanych podproblemów (aby uniknąć ich wielokrotnego rozwiązywania i ponoszenia dodatkowego czasu obliczeniowego), można to nazwać programowaniem dynamicznym lub zapamiętywaniem .

Przypadek podstawowy

Definicja funkcji rekurencyjnej ma jeden lub więcej przypadków bazowych , co oznacza dane wejściowe, dla których funkcja generuje wynik trywialnie (bez powtarzania) oraz jeden lub więcej przypadków rekurencyjnych , co oznacza dane wejściowe, dla których program powtarza się (wywołuje się) . Na przykład funkcję silni można zdefiniować rekurencyjnie równaniami 0! = 1 a dla wszystkich n > 0 , n ! = n ( n − 1)! . Żadne równanie samo w sobie nie stanowi pełnej definicji; pierwszy to przypadek podstawowy, a drugi to przypadek rekurencyjny. Ponieważ przypadek podstawowy przerywa łańcuch rekurencji, jest czasami nazywany również „przypadek kończący”.

Zadanie przypadków rekurencyjnych może być postrzegane jako rozkładanie złożonych danych wejściowych na prostsze. W prawidłowo zaprojektowanej funkcji rekurencyjnej, przy każdym wywołaniu rekurencyjnym, problem wejściowy musi być uproszczony w taki sposób, aby ostatecznie osiągnąć przypadek bazowy. (Funkcje, które nie są przeznaczone do zakończenia w normalnych warunkach — na przykład niektóre procesy systemowe i serwerowe — stanowią wyjątek od tej zasady). Zaniedbanie napisania przypadku podstawowego lub jego nieprawidłowe przetestowanie może spowodować nieskończoną pętlę .

W przypadku niektórych funkcji (takich jak ta, która oblicza szereg dla e = 1/0! + 1/1! + 1/2! + 1/3! + ... ) nie ma oczywistego przypadku bazowego implikowanego przez dane wejściowe ; dla nich można dodać parametr (taki jak liczba terminów do dodania, w naszym przykładzie serii), aby zapewnić „kryterium zatrzymania”, które ustala przypadek bazowy. Taki przykład jest bardziej naturalnie traktowany przez korkursję , gdzie kolejne wyrazy na wyjściu są sumami cząstkowymi; można to przekonwertować na rekurencję, używając parametru indeksowania do powiedzenia „oblicz n- ty termin ( n- ta suma częściowa)”.

Rekurencyjne typy danych

Wiele programów komputerowych musi przetwarzać lub generować dowolnie dużą ilość danych . Rekurencja to technika reprezentowania danych, których dokładny rozmiar jest nieznany programiście : programista może określić te dane za pomocą definicji autoreferencyjnej . Istnieją dwa rodzaje definicji autoreferencyjnych : definicje indukcyjne i koindukcyjne .

Dane definiowane indukcyjnie

Definiowana indukcyjnie rekurencyjna definicja danych to taka, która określa sposób konstruowania wystąpień danych. Na przykład, połączone listy mogą być definiowane indukcyjnie (tutaj za pomocą składni Haskella ):

data ListOfStrings = EmptyList | Cons String ListOfStrings

Powyższy kod określa listę ciągów, które mają być puste, lub strukturę zawierającą ciąg i listę ciągów. Samoodniesienie w definicji pozwala na konstruowanie list o dowolnej (skończonej) liczbie ciągów.

Innym przykładem definicji indukcyjnej są liczby naturalne (lub dodatnie liczby całkowite ):

A natural number is either 1 or n+1, where n is a natural number.

Podobnie definicje rekurencyjne są często używane do modelowania struktury wyrażeń i instrukcji w językach programowania. Projektanci języków często wyrażają gramatyki w składni takiej jak Backus-Naur form ; oto taka gramatyka, dla prostego języka wyrażeń arytmetycznych z mnożeniem i dodawaniem:

 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)

Oznacza to, że wyrażenie jest liczbą, iloczynem dwóch wyrażeń lub sumą dwóch wyrażeń. Rekurencyjnie odwołując się do wyrażeń w drugim i trzecim wierszu, gramatyka pozwala na dowolnie skomplikowane wyrażenia arytmetyczne, takie jak (5 * ((3 * 6) + 8)), z więcej niż jednym iloczynem lub operacją sumy w jednym wyrażeniu.

Dane zdefiniowane koindukcyjnie i współkursje

Definicja danych indukcyjnych to taka, która określa operacje, które można wykonać na danych; zazwyczaj dla struktur danych o nieskończonym rozmiarze stosuje się samoodnoszące się definicje koindukcyjne.

Coindukcyjna definicja nieskończonych strumieni ciągów, podana nieformalnie, może wyglądać tak:

A stream of strings is an object s such that:
 head(s) is a string, and
 tail(s) is a stream of strings.

Jest to bardzo podobne do indukcyjnej definicji list ciągów; różnica jest taka, że ta definicja określa, w jaki sposób uzyskać dostęp do zawartości dane struktura-mianowicie poprzez dostępowych funkcji headi tail-i jakie mogą być te treści, natomiast indukcyjnych definition Określa sposób utworzyć strukturę i jakie mogą być stworzone z.

Korkursja jest związana z koindukcją i może być używana do obliczania konkretnych wystąpień (prawdopodobnie) nieskończonych obiektów. Jako technika programowania jest używana najczęściej w kontekście leniwych języków programowania i może być preferowana niż rekursja, gdy żądany rozmiar lub precyzja danych wyjściowych programu jest nieznany. W takich przypadkach program wymaga zarówno definicji nieskończenie dużego (lub nieskończenie precyzyjnego) wyniku, jak i mechanizmu pobierania skończonej części tego wyniku. Problem obliczania pierwszych n liczb pierwszych to taki, który można rozwiązać za pomocą programu współbieżnego (np. tutaj ).

Rodzaje rekurencji

Rekurencja pojedyncza i rekurencja wielokrotna

Rekurencja, która zawiera tylko jedno odniesienie do siebie, jest znana jako pojedyncza rekursja , podczas gdy rekursja zawierająca wiele samoodniesień jest znana jakowielokrotna rekurencja . Standardowe przykłady pojedynczej rekursji obejmują przechodzenie przez listę, takie jak wyszukiwanie liniowe lub obliczanie funkcji silni, podczas gdy standardowe przykłady wielokrotnej rekursji obejmująprzechodzenie przez drzewo, takie jak wyszukiwanie w głąb.

Pojedyncza rekurencja jest często znacznie bardziej wydajna niż wielokrotna rekurencja i generalnie można ją zastąpić obliczeniami iteracyjnymi, działającymi w czasie liniowym i wymagającymi stałej przestrzeni. W przeciwieństwie do tego, wielokrotna rekurencja może wymagać wykładniczego czasu i przestrzeni i jest zasadniczo rekurencyjna, nie można jej zastąpić iteracją bez wyraźnego stosu.

Wielokrotna rekursja może czasami zostać przekonwertowana na pojedynczą rekursję (i, w razie potrzeby, na iterację). Na przykład, podczas gdy obliczanie ciągu Fibonacciego naiwnie jest wielokrotną iteracją, ponieważ każda wartość wymaga dwóch poprzednich wartości, można ją obliczyć za pomocą pojedynczej rekurencji, przekazując dwie kolejne wartości jako parametry. Jest to bardziej naturalnie sformułowane jako korekursja, budowanie z początkowych wartości, śledzenie na każdym kroku dwóch kolejnych wartości – patrz korekursja: przykłady . Bardziej wyrafinowanym przykładem jest użycie wątkowego drzewa binarnego , które umożliwia iteracyjne przechodzenie po drzewie zamiast wielokrotnej rekursji.

Rekurencja pośrednia

Pokazuje większość podstawowych przykładów rekurencji i większość przykładów przedstawionych tutaj bezpośrednia rekursja , w której funkcja wywołuje samą siebie. Rekurencja pośrednia występuje, gdy funkcja jest wywoływana nie sama, ale przez inną funkcję, którą wywołała (bezpośrednio lub pośrednio). Na przykład, jeśli f woła f, jest to bezpośrednia rekurencja, ale jeśli f woła g, co woła f, to jest to pośrednia rekurencja f. Możliwe są łańcuchy trzech lub więcej funkcji; na przykład funkcja 1 wywołuje funkcję 2, funkcja 2 wywołuje funkcję 3, a funkcja 3 ponownie wywołuje funkcję 1.

Rekurencja pośrednia jest również nazywana rekurencją wzajemną , co jest pojęciem bardziej symetrycznym, chociaż jest to po prostu różnica akcentów, a nie inne pojęcie. Oznacza to, że jeżeli m wywołuje g i potem g połączenia F, co z kolei wywołuje g ponownie z punktu widzenia f Tylko F pośrednio rekurencyjnej, a z punktu widzenia g sam, pośrednio rekurencyjnej, natomiast z punktu widzenia obu f i g wzajemnie się powtarzają. Podobnie zestaw trzech lub więcej funkcji, które wywołują się nawzajem, można nazwać zestawem wzajemnie rekurencyjnych funkcji.

Anonimowa rekurencja

Rekurencja jest zwykle wykonywana przez jawne wywołanie funkcji według nazwy. Jednak rekursję można również wykonać przez niejawne wywołanie funkcji na podstawie bieżącego kontekstu, co jest szczególnie przydatne w przypadku funkcji anonimowych i jest znane jako anonimowa rekursja .

Rekurencja strukturalna a generatywna

Niektórzy autorzy klasyfikują rekurencję jako „strukturalną” lub „generatywną”. Rozróżnienie dotyczy tego, gdzie procedura rekurencyjna pobiera dane, na których działa, i jak przetwarza te dane:

[Funkcje, które wykorzystują dane strukturalne] zazwyczaj rozkładają swoje argumenty na ich bezpośrednie elementy strukturalne, a następnie przetwarzają te elementy. Jeśli jeden z bezpośrednich komponentów należy do tej samej klasy danych co dane wejściowe, funkcja jest rekurencyjna. Z tego powodu funkcje te nazywamy (STRUKTURALNIE) FUNKCJAMI REKURSOWYMI.

—  Felleisen, Findler, Flatt i Krishnaurthi, Jak projektować programy , 2001

Tak więc cechą definiującą strukturalnie rekurencyjną funkcję jest to, że argumentem każdego wywołania rekurencyjnego jest zawartość pola oryginalnego wejścia. Rekurencja strukturalna obejmuje prawie wszystkie przechodzenie przez drzewa, w tym przetwarzanie XML, tworzenie i wyszukiwanie drzew binarnych itp. Biorąc pod uwagę strukturę algebraiczną liczb naturalnych (to znaczy, że liczba naturalna jest albo zerem, albo następcą liczby naturalnej), funkcje takie jako silnię można również uznać za rekurencję strukturalną.

Alternatywą jest rekurencja generatywna :

Wiele znanych algorytmów rekurencyjnych generuje z podanych danych zupełnie nową porcję danych i powtarza się na niej. HtDP ( How to Design Programs ) odnosi się do tego rodzaju rekurencji generatywnej. Przykłady rekursji generatywnej to: gcd , quicksort , wyszukiwanie binarne , mergesort , metoda Newtona , fraktale i adaptacyjna integracja .

—  Matthias Felleisen, Zaawansowane programowanie funkcjonalne , 2002 r

To rozróżnienie jest ważne przy dowodzeniu zakończenia funkcji.

  • Wszystkie strukturalnie rekurencyjne funkcje na skończonych ( zdefiniowanych indukcyjnie ) strukturach danych można łatwo pokazać, że się kończą, poprzez indukcję strukturalną : intuicyjnie, każde wywołanie rekurencyjne otrzymuje mniejszą część danych wejściowych, aż do osiągnięcia przypadku bazowego.
  • Natomiast funkcje generatywnie rekurencyjne niekoniecznie dostarczają mniejszych danych wejściowych do ich wywołań rekurencyjnych, więc dowód ich zakończenia niekoniecznie jest tak prosty, a unikanie nieskończonych pętli wymaga większej ostrożności. Te generatywnie rekurencyjne funkcje mogą być często interpretowane jako funkcje korekursywne – każdy krok generuje nowe dane, takie jak kolejne aproksymacje w metodzie Newtona – a zakończenie tej kokurencji wymaga, aby dane ostatecznie spełniły pewien warunek, który niekoniecznie jest gwarantowany.
  • Jeśli chodzi o warianty pętli , rekurencja strukturalna występuje wtedy, gdy istnieje oczywisty wariant pętli, a mianowicie rozmiar lub złożoność, która zaczyna się skończona i zmniejsza się na każdym kroku rekurencyjnym.
  • W przeciwieństwie do tego, rekurencja generatywna ma miejsce, gdy nie ma tak oczywistego wariantu pętli, a zakończenie zależy od funkcji, takiej jak „błąd aproksymacji”, który niekoniecznie zmniejsza się do zera, a zatem zakończenie nie jest gwarantowane bez dalszej analizy.

Problemy wdrożeniowe

W rzeczywistej implementacji, zamiast czystej funkcji rekurencyjnej (pojedyncza kontrola przypadku bazowego, w przeciwnym razie etap rekurencyjny), można wprowadzić szereg modyfikacji, dla celów przejrzystości lub wydajności. Obejmują one:

  • Funkcja owijarki (u góry)
  • Zwarcie obudowy podstawowej, czyli „rekurencja na długość ramienia” (na dole)
  • Algorytm hybrydowy (na dole) – przejście na inny algorytm, gdy dane są wystarczająco małe

Ze względu na elegancję funkcje owijarki są ogólnie akceptowane, podczas gdy zwieranie obudowy podstawowej jest mile widziane, szczególnie w środowisku akademickim. Algorytmy hybrydowe są często używane w celu zwiększenia wydajności, w celu zmniejszenia narzutu związanego z rekurencją w małych przypadkach, a rekurencja na zasadach rynkowych jest tego szczególnym przypadkiem.

Funkcja owijarki

Funkcja opakowująca to funkcja, która jest wywoływana bezpośrednio, ale sama nie jest rekursywna, zamiast tego wywołuje oddzielną funkcję pomocniczą, która faktycznie wykonuje rekurencję.

Funkcje opakowujące mogą być używane do sprawdzania poprawności parametrów (dzięki czemu funkcja rekurencyjna może je pominąć), wykonywania inicjalizacji (alokowania pamięci, inicjowania zmiennych), szczególnie w przypadku zmiennych pomocniczych, takich jak „poziom rekurencji” lub częściowych obliczeń do zapamiętywania i obsługi wyjątków i błędów . W językach, które obsługują funkcje zagnieżdżone , funkcja pomocnicza może być zagnieżdżona w funkcji opakowującej i korzystać ze wspólnego zakresu. W przypadku braku funkcji zagnieżdżonych, funkcje pomocnicze są zamiast tego oddzielną funkcją, jeśli to możliwe, prywatną (ponieważ nie są wywoływane bezpośrednio), a informacje są współdzielone z funkcją opakowującą za pomocą pass-by-reference .

Zwarcie obudowy bazowej

Silnia: zwykła vs. zwarciowa
Zwykła rekurencja Rekurencja zwarcia
int fac1(int n) {
   if (n <= 0)
      return 1;
   else
      return fac1(n-1)*n;
}
static int fac2(int n) {
   // assert(n >= 2);
   if (n == 2)
      return 2;
   else
      return fac2(n-1)*n;
}
int fac2wrapper(int n) {
   if (n <= 1)
      return 1;
   else
      return fac2(n);
}

Zwarcie przypadku bazowego, zwane również rekurencją na długość ramienia, polega na sprawdzeniu przypadku bazowego przed wykonaniem wywołania rekurencyjnego – tj. sprawdzeniu, czy następne wywołanie będzie przypadkiem bazowym, zamiast wywoływania, a następnie sprawdzaniu przypadku bazowego . Zwarcie jest wykonywane szczególnie ze względu na wydajność, aby uniknąć narzutu wywołania funkcji, która natychmiast powraca. Należy zauważyć, że ponieważ przypadek bazowy został już sprawdzony (bezpośrednio przed krokiem rekurencyjnym), nie trzeba go sprawdzać osobno, ale należy użyć funkcji opakowującej dla przypadku, gdy całkowita rekursja zaczyna się od przypadku bazowego samo. Na przykład, w funkcji silni, właściwie podstawą przypadku jest 0! = 1, natychmiast zwracając 1 za 1! jest zwarciem i może pominąć 0; można to złagodzić za pomocą funkcji opakowującej. W ramce wyświetlany jest kod C, aby skrócić przypadki silni 0 i 1.

Zwarcie jest problemem przede wszystkim w przypadku napotkania wielu przypadków bazowych, takich jak wskaźniki zerowe w drzewie, które mogą być liniowe w liczbie wywołań funkcji, co oznacza znaczne oszczędności dla algorytmów O ( n ) ; jest to zilustrowane poniżej dla wyszukiwania w głąb. Krótkie spięcie na drzewie odpowiada uznaniu liścia (niepustego węzła bez dzieci) za przypadek podstawowy, a nie uznaniu pustego węzła za przypadek podstawowy. Jeśli istnieje tylko jeden przypadek podstawowy, na przykład przy obliczaniu silni, zwarcie zapewnia tylko O (1) oszczędności.

Koncepcyjnie można uznać, że zwarcie ma ten sam przypadek podstawowy i krok rekurencyjny, sprawdzając przypadek podstawowy tylko przed rekurencją, lub można uznać, że ma inny przypadek podstawowy (jeden krok usunięty ze standardowego przypadku podstawowego) i bardziej złożony krok rekurencyjny, a mianowicie "sprawdź poprawność, a następnie rekursywnie", jak w przypadku rozpatrywania węzłów liścia zamiast węzłów zerowych jako przypadków bazowych w drzewie. Ponieważ zwarcie ma bardziej skomplikowany przebieg w porównaniu z wyraźnym oddzieleniem przypadku podstawowego i kroku rekurencyjnego w standardowej rekursji, jest często uważane za kiepski styl, szczególnie w środowisku akademickim.

Wyszukiwanie w głąb

Podstawowy przykład zwarcia podano w przeszukiwaniu dogłębnym (DFS) drzewa binarnego; zobacz sekcję o drzewach binarnych, aby zapoznać się ze standardową rekurencyjną dyskusją.

Standardowy algorytm rekurencyjny dla systemu plików DFS to:

  • przypadek podstawowy: Jeśli bieżący węzeł ma wartość Null, zwróć false
  • krok rekurencyjny: w przeciwnym razie sprawdź wartość bieżącego węzła, zwróć true, jeśli pasuje, w przeciwnym razie rekurencja na dzieciach

W zwarciu jest to zamiast tego:

  • sprawdź wartość bieżącego węzła, zwróć true, jeśli pasuje,
  • w przeciwnym razie na dzieciach, jeśli nie Null, to rekurencja.

Jeśli chodzi o standardowe kroki, przesuwa to sprawdzenie przypadku podstawowego przed krokiem rekurencyjnym. Alternatywnie można je uznać odpowiednio za inną formę przypadku podstawowego i kroku rekurencyjnego. Zauważ, że wymaga to funkcji opakowującej do obsługi przypadku, gdy samo drzewo jest puste (węzeł główny ma wartość Null).

W przypadku idealnego drzewa binarnego o wysokości h, jako dzieci mamy 2 h +1 −1 węzłów i 2 h +1 wartości zerowych (po 2 dla każdego z 2 h liści), więc zwarcie obcina liczbę funkcji w najgorszym przypadku dzwoni na pół.

W C standardowy algorytm rekurencyjny może być zaimplementowany jako:

bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // base case
    else if (tree_node->data == i)
        return true;
    else
        return tree_contains(tree_node->left, i) ||
               tree_contains(tree_node->right, i);
}

Algorytm zwarciowy może być zaimplementowany jako:

// Wrapper function to handle empty tree
bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // empty tree
    else
        return tree_contains_do(tree_node, i);  // call auxiliary function
}

// Assumes tree_node != NULL
bool tree_contains_do(struct node *tree_node, int i) {
    if (tree_node->data == i)
        return true;  // found
    else  // recurse
        return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||
               (tree_node->right && tree_contains_do(tree_node->right, i));
}

Zwróć uwagę na użycie oceny zwarcia operatorów logicznych && (AND), aby wywołanie rekurencyjne było wykonywane tylko wtedy, gdy węzeł jest prawidłowy (nie ma wartości Null). Zauważ, że podczas gdy pierwszy termin w AND jest wskaźnikiem do węzła, drugi termin jest wartością logiczną, więc ogólne wyrażenie jest wartością logiczną. Jest to powszechny idiom w zwarciu rekurencyjnym. Jest to dodatek do oceny zwarcia logicznego || (LUB), aby sprawdzić tylko prawe dziecko, jeśli lewe dziecko zawiedzie. W rzeczywistości cały przepływ sterowania tymi funkcjami można zastąpić pojedynczym wyrażeniem logicznym w instrukcji return, ale czytelność nie wpływa na wydajność.

Algorytm hybrydowy

Algorytmy rekurencyjne są często nieefektywne w przypadku małych danych ze względu na obciążenie powtarzających się wywołań funkcji i zwrotów. Z tego powodu wydajne implementacje algorytmów rekurencyjnych często zaczynają się od algorytmu rekurencyjnego, ale następnie przełączają się na inny algorytm, gdy dane wejściowe stają się małe. Ważnym przykładem jest merge sort , który jest często implementowany przez przełączenie na nierekurencyjne sortowanie z wstawianiem, gdy dane są wystarczająco małe, jak w przypadku kafelkowego merge sort . Hybrydowe algorytmy rekurencyjne często mogą być dalej udoskonalane, tak jak w Timsort , wywodzące się z hybrydowego sortowania przez scalanie/wstawianie.

Rekurencja a iteracja

Rekurencja i iteracja są równie ekspresyjne: rekurencję można zastąpić iteracją z jawnym stosem wywołań , podczas gdy iterację można zastąpić rekurencją ogonową . To, które podejście jest preferowane, zależy od rozważanego problemu i używanego języka. W programowaniu imperatywnym preferowana jest iteracja, szczególnie w przypadku prostej rekursji, ponieważ pozwala uniknąć narzutu wywołań funkcji i zarządzania stosem wywołań, ale rekursja jest zwykle używana do wielokrotnej rekursji. Z kolei w językach funkcjonalnych preferowana jest rekurencja, przy czym optymalizacja rekurencji ogonowej prowadzi do niewielkiego narzutu. Implementacja algorytmu za pomocą iteracji może nie być łatwa do osiągnięcia.

Porównaj szablony, aby obliczyć x n zdefiniowane przez x n = f(n, x n-1 ) z x base :

function recursive(n)
    if n == base
        return xbase
    else
        return f(n, recursive(n-1))
function iterative(n)
    x = xbase
    for i = base+1 to n
        x = f(i, x)
    return x

Dla języka imperatywnego narzutem jest zdefiniowanie funkcji, dla języka funkcjonalnego narzutem jest zdefiniowanie zmiennej akumulatora x.

Na przykład funkcję silni można zaimplementować iteracyjnie w C , przypisując ją do zmiennej indeksu pętli i zmiennej akumulatora, a nie przez przekazywanie argumentów i zwracanie wartości przez rekursję:

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

Ekspresyjna moc

Większość używanych obecnie języków programowania umożliwia bezpośrednią specyfikację funkcji i procedur rekurencyjnych. Kiedy taka funkcja nazywa się program za środowisko uruchomieniowe śledzi różne instancje danej funkcji (często z użyciem stosu wywołań , chociaż mogą być stosowane inne metody). Każdą funkcję rekurencyjną można przekształcić w funkcję iteracyjną, zastępując wywołania rekurencyjne iteracyjnymi konstrukcjami kontrolnymi i symulując stos wywołań ze stosem jawnie zarządzanym przez program.

Odwrotnie, wszystkie funkcje i procedury iteracyjne, które mogą być oceniane przez komputer (patrz kompletność Turinga ) mogą być wyrażone w kategoriach funkcji rekurencyjnych; iteracyjne konstrukcje sterujące, takie jak pętle while i pętle for, są rutynowo przepisywane w formie rekurencyjnej w językach funkcjonalnych . Jednak w praktyce to przepisywanie zależy od eliminacji ogona , co nie jest cechą wszystkich języków. C , Java i Python to godne uwagi języki głównego nurtu, w których wszystkie wywołania funkcji, w tym wywołania ogona , mogą powodować alokację stosu, która nie wystąpiłaby przy użyciu konstrukcji pętli; w tych językach działający program iteracyjny przepisany w formie rekurencyjnej może przepełnić stos wywołań , chociaż eliminacja wywołań ogonowych może być cechą, która nie jest objęta specyfikacją języka, a różne implementacje tego samego języka mogą różnić się możliwościami eliminacji wywołań ogonowych.

Problemy z wydajnością

W językach (takich jak C i Java ), które faworyzują konstrukcje pętli iteracyjnych, z programami rekurencyjnymi zwykle wiążą się znaczne koszty czasu i przestrzeni, ze względu na narzut wymagany do zarządzania stosem i względną powolność wywołań funkcji; w językach funkcjonalnych wywołanie funkcji (w szczególności wywołanie ogona ) jest zazwyczaj bardzo szybką operacją, a różnica jest zwykle mniej zauważalna.

Jako konkretny przykład, różnica w wydajności między implementacjami rekurencyjnymi i iteracyjnymi powyższego przykładu „silnikowego” zależy w dużym stopniu od używanego kompilatora . W językach, w których preferowane są konstrukcje zapętlone, wersja iteracyjna może być nawet o kilka rzędów wielkości szybsza niż wersja rekurencyjna. W językach funkcjonalnych całkowita różnica czasu obu implementacji może być nieistotna; w rzeczywistości koszt pomnożenia najpierw większych liczb, a nie mniejszych liczb (co zdarza się w wersji iteracyjnej podanej tutaj) może przytłaczać każdy czas zaoszczędzony dzięki wybraniu iteracji.

Miejsce na stos

W niektórych językach programowania maksymalny rozmiar stosu wywołań jest znacznie mniejszy niż miejsce dostępne w stercie , a algorytmy rekurencyjne zwykle wymagają więcej miejsca na stosie niż algorytmy iteracyjne. W związku z tym języki te czasami ograniczają głębokość rekurencji, aby uniknąć przepełnienia stosu ; Python jest jednym z takich języków. Zwróć uwagę na poniższe zastrzeżenie dotyczące szczególnego przypadku rekurencji ogona .

Słaby punkt

Ponieważ algorytmy rekurencyjne mogą podlegać przepełnieniom stosu, mogą być podatne na patologiczne lub złośliwe dane wejściowe. Niektóre złośliwe programy atakują w szczególności stos wywołań programu i wykorzystują rekurencyjną naturę stosu. Nawet w przypadku braku złośliwym oprogramowaniem, przepełnienie stosu spowodowane nieograniczonej rekursji mogą być śmiertelne dla programu i obsługę wyjątków logiczne nie mogą przeszkadzać w odpowiedni sposób przed zakończone .

Pomnóż rekurencyjne problemy

Pomnóż rekurencyjne problemy są z natury rekurencyjne, ze względu na wcześniejszy stan, który muszą być śledzone. Jednym z przykładów jest przechodzenie przez drzewo, jak w przeszukiwaniu w głąb ; chociaż używane są zarówno metody rekurencyjne, jak i iteracyjne, kontrastują one z przechodzeniem po listach i wyszukiwaniem liniowym na liście, które jest metodą pojedynczo rekurencyjną, a zatem naturalnie iteracyjną. Inne przykłady obejmują algorytmy dziel i zwyciężaj, takie jak Quicksort i funkcje, takie jak funkcja Ackermanna . Wszystkie te algorytmy można implementować iteracyjnie za pomocą jawnego stosu , ale wysiłek programisty związany z zarządzaniem stosem i złożoność wynikowego programu prawdopodobnie przewyższają wszelkie zalety rozwiązania iteracyjnego.

Refaktoryzacja rekurencji

Algorytmy rekurencyjne można zastąpić odpowiednikami nierekurencyjnymi. Jedną z metod zastępowania algorytmów rekurencyjnych jest ich symulacja przy użyciu pamięci sterty zamiast pamięci stosu . Alternatywą jest opracowanie algorytmu zastępowania całkowicie opartego na metodach nierekurencyjnych, co może być trudne. Na przykład, rekurencyjnych algorytmów dopasowywania literowych , takie jak Rich Salz ' wildmat algorytmu niegdyś typowe. Algorytmy nierekurencyjne do tego samego celu, takie jak algorytm dopasowania symboli wieloznacznych Kraussa , zostały opracowane w celu uniknięcia wad rekurencji i są ulepszane tylko stopniowo w oparciu o techniki, takie jak zbieranie testów i profilowanie wydajności.

Funkcje rekurencyjne ogona

Funkcje rekurencyjne ogona to funkcje, w których wszystkie wywołania rekurencyjne są wywołaniami ogona, a zatem nie tworzą żadnych odroczonych operacji. Na przykład funkcja gcd (pokazana ponownie poniżej) jest tail-recursive. Natomiast funkcja silnia (również poniżej) nie jest rekurencyjna na ogonie; ponieważ jego wywołanie rekurencyjne nie znajduje się w pozycji końcowej, tworzy odroczone operacje mnożenia, które muszą zostać wykonane po zakończeniu końcowego wywołania rekurencyjnego. Z kompilatorem lub interpreterem, który traktuje wywołania rekurencyjne jako skoki, a nie wywołania funkcji, funkcja rekurencyjna, taka jak gcd, będzie wykonywana przy użyciu stałej spacji. W ten sposób program jest zasadniczo iteracyjny, równoważny użyciu imperatywnych struktur kontroli języka, takich jak pętle "for" i "while".

Rekurencja ogona : Rozszerzenie rekurencji:
//INPUT: Integers x, y such that x >= y and y >= 0
int gcd(int x, int y)
{
  if (y == 0)
     return x;
  else
     return gcd(y, x % y);
}
//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

Znaczenie rekurencji tail jest takie, że podczas wykonywania wywołania tail-recursive (lub jakiegokolwiek wywołania tail), pozycja powrotu wywołującego nie musi być zapisana na stosie wywołań ; gdy rekursywne wywołanie powróci, rozgałęzi się bezpośrednio na poprzednio zapisaną pozycję powrotu. Dlatego w językach, które rozpoznają tę właściwość zawołań ogona, rekurencja ogona oszczędza zarówno przestrzeń, jak i czas.

Kolejność wykonania

Rozważ te dwie funkcje:

Funkcja 1

void recursiveFunction(int num) {
    printf("%d\n", num);
    if (num < 4)
        recursiveFunction(num + 1);
}

Rekursywny1.svg

Funkcja 2

void recursiveFunction(int num) {
    if (num < 4)
        recursiveFunction(num + 1);
    printf("%d\n", num);
}

Rekursywny2.svg

Funkcja 2 to funkcja 1 z zamienionymi liniami.

W przypadku funkcji wywołującej samą siebie tylko raz, instrukcje umieszczone przed wywołaniem rekurencyjnym są wykonywane raz na rekursję przed którąkolwiek z instrukcji umieszczonych po wywołaniu rekurencyjnym. Te ostatnie są wykonywane wielokrotnie po osiągnięciu maksymalnej rekurencji.

Należy również zauważyć, że kolejność instrukcji print jest odwrócona, co wynika ze sposobu przechowywania funkcji i instrukcji na stosie wywołań .

Procedury rekurencyjne

Factorial

Klasycznym przykładem procedury rekurencyjnej jest funkcja służąca do obliczania silni liczby naturalnej :

Pseudokod (rekurencyjny):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ]
end factorial

Funkcję można również zapisać jako relację rekurencyjną :

Ta ocena relacji powtarzalności pokazuje obliczenia, które zostałyby wykonane przy ocenie powyższego pseudokodu:

Obliczanie relacji rekurencyjności dla n = 4:
b4           = 4 × b3
             = 4 × (3 × b2)
             = 4 × (3 × (2 × b1))
             = 4 × (3 × (2 × (1 × b0)))
             = 4 × (3 × (2 × (1 × 1)))
             = 4 × (3 × (2 × 1))
             = 4 × (3 × 2)
             = 4 × 6
             = 24

Tę funkcję czynnikową można również opisać bez użycia rekurencji, używając typowych konstrukcji pętli występujących w imperatywnych językach programowania:

Pseudokod (iteracyjny):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop 1. if n is 0, exit loop 2. set running_total to (running_total × n) 3. decrement n 4. repeat loop
3. return running_total
end factorial

Powyższy kod imperatywny jest równoważny tej matematycznej definicji wykorzystującej zmienną akumulatorową t :

Powyższa definicja przekłada się bezpośrednio na funkcjonalne języki programowania, takie jak Scheme ; jest to przykład iteracji zaimplementowanej rekurencyjnie.

Największy wspólny dzielnik

Euklidesowa algorytm , który oblicza największy wspólny dzielnik dwóch liczb całkowitych, mogą być napisane rekurencyjnie.

Definicja funkcji :

Pseudokod (rekurencyjny):
function gcd is:
input: integer x, integer y such that x > 0 and y >= 0

1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ]
end gcd

Relacja rekurencyjna dla największego wspólnego dzielnika, gdzie wyraża resztę z :

Jeśli
Obliczenie relacji rekurencyjności dla x = 27 i y = 9:
gcd(27, 9)   = gcd(9, 27 % 9)
             = gcd(9, 0)
             = 9
Obliczenie relacji rekurencyjności dla x = 111 i y = 259:
gcd(111, 259)   = gcd(259, 111 % 259)
                = gcd(259, 111)
                = gcd(111, 259 % 111)
                = gcd(111, 37)
                = gcd(37, 111 % 37)
                = gcd(37, 0)
                = 37

Powyższy program rekurencyjny jest tail-recursive ; jest to odpowiednik algorytmu iteracyjnego, a obliczenia pokazane powyżej pokazują etapy oceny, które zostałyby wykonane przez język eliminujący wywołania ogona. Poniżej znajduje się wersja tego samego algorytmu wykorzystująca jawną iterację, odpowiednią dla języka, który nie eliminuje wywołań ogona. Utrzymując swój stan całkowicie w zmiennych x i y oraz używając konstrukcji pętli, program unika wykonywania wywołań rekurencyjnych i powiększania stosu wywołań.

Pseudokod (iteracyjny):
function gcd is:
input: integer x, integer y such that x >= y and y >= 0
1. create new variable called remainder
2. begin loop 1. if y is zero, exit loop 2. set remainder to the remainder of x/y 3. set x to y 4. set y to remainder 5. repeat loop
3. return x
end gcd

Algorytm iteracyjny wymaga zmiennej tymczasowej, a nawet przy znajomości algorytmu euklidesowego trudniej jest zrozumieć proces za pomocą prostej inspekcji, chociaż oba algorytmy są bardzo podobne w swoich krokach.

Wieże Hanoi

Wieże Hanoi

Wieże Hanoi to matematyczna zagadka, której rozwiązanie ilustruje rekurencję. Istnieją trzy kołki, które mogą pomieścić stosy dysków o różnych średnicach. Większy dysk nigdy nie może być układany na mniejszym. Zaczynając od n krążków na jednym kołku, należy je przenosić pojedynczo na inny kołek. Jaka jest najmniejsza liczba kroków do przesunięcia stosu?

Definicja funkcji :

Relacja nawrotu dla hanoi :

Obliczanie relacji rekurencyjności dla n = 4:
hanoi(4)     = 2×hanoi(3) + 1
             = 2×(2×hanoi(2) + 1) + 1
             = 2×(2×(2×hanoi(1) + 1) + 1) + 1
             = 2×(2×(2×1 + 1) + 1) + 1
             = 2×(2×(3) + 1) + 1
             = 2×(7) + 1
             = 15


Przykładowe implementacje:

Pseudokod (rekurencyjny):
function hanoi is:
input: integer n, such that n >= 1
1. if n is 1 then return 1
2. return [2 * [call hanoi(n-1)] + 1]
end hanoi

Chociaż nie wszystkie funkcje rekurencyjne mają jednoznaczne rozwiązanie, sekwencję Wieży Hanoi można zredukować do jawnej formuły.

Wyraźna formuła dla Wież Hanoi:
h1 = 1   = 21 - 1
h2 = 3   = 22 - 1
h3 = 7   = 23 - 1
h4 = 15  = 24 - 1
h5 = 31  = 25 - 1
h6 = 63  = 26 - 1
h7 = 127 = 27 - 1
In general:
hn = 2n - 1, for all n >= 1

Wyszukiwanie binarne

Przeszukiwanie binarne algorytm jest sposób przeszukiwania posortowanej tablicy dla jednego elementu poprzez wycięcie w szereg rekurencyjnego połowie do każdego przebiegu. Sztuczka polega na wybraniu punktu środkowego w pobliżu środka tablicy, porównaniu danych w tym punkcie z danymi przeszukiwanymi, a następnie zareagowaniu na jeden z trzech możliwych warunków: dane znajdują się w punkcie środkowym, dane w punkcie środkowym są większe niż wyszukiwane dane lub dane w punkcie środkowym są mniejsze niż wyszukiwane dane.

Rekurencja jest używana w tym algorytmie, ponieważ przy każdym przejściu tworzona jest nowa tablica poprzez przecięcie starej na pół. Procedura wyszukiwania binarnego jest następnie wywoływana rekurencyjnie, tym razem na nowej (i mniejszej) tablicy. Zazwyczaj rozmiar tablicy jest dostosowywany przez manipulowanie indeksem początkowym i końcowym. Algorytm wykazuje logarytmiczny rząd wzrostu, ponieważ zasadniczo dzieli domenę problemu na pół przy każdym przejściu.

Przykładowa implementacja wyszukiwania binarnego w C:

 /*
  Call binary_search with proper initial conditions.

  INPUT:
    data is an array of integers SORTED in ASCENDING order,
    toFind is the integer to search for,
    count is the total number of elements in the array

  OUTPUT:
    result of binary_search

 */
 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (beginning index)
    //  End = count - 1 (top index)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Binary Search Algorithm.

   INPUT:
        data is a array of integers SORTED in ASCENDING order,
        toFind is the integer to search for,
        start is the minimum array index,
        end is the maximum array index
   OUTPUT:
        position of the integer toFind within array data,
        -1 if not found
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Get the midpoint.
    int mid = start + (end - start)/2;   //Integer division


    if (start > end)                     //Stop condition (base case)
       return -1;
    else if (data[mid] == toFind)        //Found, return index
       return mid;
    else if (data[mid] > toFind)         //Data is greater than toFind, search lower half
       return binary_search(data, toFind, start, mid-1);
    else                                 //Data is less than toFind, search upper half
       return binary_search(data, toFind, mid+1, end);
 }

Rekurencyjne struktury danych (rekurencja strukturalna)

Ważnym zastosowaniem rekurencji w informatyce jest definiowanie dynamicznych struktur danych, takich jak listy i drzewa . Rekurencyjne struktury danych mogą dynamicznie rosnąć do teoretycznie nieskończonego rozmiaru w odpowiedzi na wymagania środowiska wykonawczego; w przeciwieństwie do tego, rozmiar tablicy statycznej musi być ustawiony w czasie kompilacji.

„Algorytmy rekurencyjne są szczególnie odpowiednie, gdy podstawowy problem lub dane, które mają być przetwarzane, są zdefiniowane w terminach rekurencyjnych”.

Przykłady w tej sekcji ilustrują tak zwaną „rekurencję strukturalną”. Termin ten odnosi się do faktu, że procedury rekurencyjne działają na danych, które są zdefiniowane rekurencyjnie.

Dopóki programista czerpie szablon z definicji danych, funkcje stosują rekurencję strukturalną. Oznacza to, że rekursje w ciele funkcji zużywają bezpośrednią część danej wartości złożonej.

Połączone listy

Poniżej znajduje się definicja w języku C struktury węzłów połączonej listy. Zwróć uwagę zwłaszcza na to, jak węzeł jest zdefiniowany pod względem samego siebie. „Następny” element węzła struktury jest wskaźnikiem do innego węzła struktury , skutecznie tworząc typ listy.

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

Ponieważ struktura danych węzła struktury jest zdefiniowana rekurencyjnie, procedury, które na niej działają, mogą być zaimplementowane naturalnie jako procedury rekurencyjne. List_print procedura określona poniżej spacery listę w dół, aż lista jest pusta (czyli wskaźnik lista ma wartość NULL). Dla każdego węzła wypisuje element danych (liczba całkowita). W implementacji C lista pozostaje niezmieniona przez procedurę list_print .

void list_print(struct node *list)
{
    if (list != NULL)               // base case
    {
       printf ("%d ", list->data);  // print integer data followed by a space
       list_print (list->next);     // recursive call on the next node
    }
}

Drzewa binarne

Poniżej znajduje się prosta definicja węzła drzewa binarnego. Podobnie jak węzeł dla list połączonych, jest on definiowany rekurencyjnie. Istnieją dwa samoodnoszące się wskaźniki: lewy (wskazujący na lewe poddrzewo) i prawy (wskazujący na prawe poddrzewo).

struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};

Operacje na drzewie mogą być realizowane za pomocą rekurencji. Zwróć uwagę, że ponieważ istnieją dwa wskaźniki odwołujące się do siebie (lewy i prawy), operacje na drzewie mogą wymagać dwóch wywołań rekurencyjnych:

// Test if tree_node contains i; return 1 if so, 0 if not.
int tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return 0;  // base case
    else if (tree_node->data == i)
        return 1;
    else
        return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}

Co najwyżej dwa wywołania rekurencyjne zostaną wykonane dla dowolnego wywołania tree_contains, jak zdefiniowano powyżej.

// Inorder traversal:
void tree_print(struct node *tree_node) {
    if (tree_node != NULL) {              // base case
        tree_print(tree_node->left);      // go left
        printf("%d ", tree_node->data);   // print the integer followed by a space
        tree_print(tree_node->right);     // go right
    }
}

Powyższy przykład ilustruje przechodzenie w kolejności drzewa binarnego. Binarne drzewo poszukiwań jest szczególnym przypadkiem binarnym drzewem gdzie elementy danych z każdego węzła są w porządku.

Przechodzenie przez system plików

Ponieważ liczba plików w systemie plików może się różnić, rekursja jest jedynym praktycznym sposobem przechodzenia, a tym samym wyliczania jego zawartości. Przechodzenie przez system plików jest bardzo podobne do przechodzenia przez drzewo , dlatego koncepcje przechodzenia przez drzewo mają zastosowanie do przechodzenia przez system plików. Dokładniej, poniższy kod byłby przykładem przechodzenia przedpremierowego systemu plików.

import java.io.File;

public class FileSystem {

	public static void main(String [] args) {
		traverse();
	}

	/**
	 * Obtains the filesystem roots
	 * Proceeds with the recursive filesystem traversal
	 */
	private static void traverse() {
		File[] fs = File.listRoots();
		for (int i = 0; i < fs.length; i++) {
			System.out.println(fs[i]);
			if (fs[i].isDirectory() && fs[i].canRead()) {
				rtraverse(fs[i]);
			}
		}
	}

	/**
	 * Recursively traverse a given directory
	 *
	 * @param fd indicates the starting point of traversal
	 */
	private static void rtraverse(File fd) {
		File[] fss = fd.listFiles();

		for (int i = 0; i < fss.length; i++) {
			System.out.println(fss[i]);
			if (fss[i].isDirectory() && fss[i].canRead()) {
				rtraverse(fss[i]);
			}
		}
	}

}

Ten kod jest zarówno rekurencją, jak i iteracją - pliki i katalogi są iterowane, a każdy katalog jest otwierany rekurencyjnie.

Metoda „rtraverse” jest przykładem bezpośredniej rekurencji, podczas gdy metoda „traverse” jest funkcją opakowującą.

Scenariusz „podstawowy” polega na tym, że w danym systemie plików zawsze będzie stała liczba plików i/lub katalogów.

Efektywność czasowa algorytmów rekurencyjnych

Wydajność czasową algorytmów rekurencyjnych można wyrazić w relacji rekurencyjnej w notacji Big O . Można je (zwykle) następnie uprościć do pojedynczego terminu Big-O.

Reguła skrótu (twierdzenie główne)

Jeżeli złożoność czasowa funkcji ma postać

Wtedy wielkie O złożoności czasowej wygląda następująco:

  • Jeśli dla jakiejś stałej , to
  • Jeśli , to
  • Jeśli dla pewnej stałej , i jeśli dla pewnej stałej c < 1 i wszystkich wystarczająco dużych n , to

gdzie a reprezentuje liczbę wywołań rekurencyjnych na każdym poziomie rekurencji, b reprezentuje o jaki czynnik mniejszy jest dane wejściowe dla następnego poziomu rekurencji (tj. liczba kawałków, na które dzielisz problem), a f  ( n ) reprezentuje pracę funkcja działa niezależnie od jakiejkolwiek rekurencji (np. partycjonowanie, rekombinacja) na każdym poziomie rekurencji.

Zobacz też

Uwagi

Bibliografia