Kiedy stosować rekurencję?

Kiedy są jakieś (względnie) podstawowe przypadki (myślę, że student pierwszego roku CS na studiach), kiedy zamiast pętli można by użyć rekurencji?

Nauczyłem C ++ studentów pierwszego roku od około dwóch lat i obejmowałem rekursję. Z mojego doświadczenia wynika, że ​​twoje pytanie i uczucia są bardzo częste. W skrajności niektórzy studenci uważają rekurencję za trudną do zrozumienia, podczas gdy inni chcą jej używać do praktycznie wszystkiego.

Myślę, że Dave dobrze to podsumowuje: używaj go tam, gdzie jest to właściwe. Oznacza to, że używaj go, gdy wydaje się to naturalne. Kiedy napotkasz problem, w którym pasuje dobrze, najprawdopodobniej go rozpoznasz: będzie wydawać się, że nie możesz nawet znaleźć iteracyjnego rozwiązania. Również przejrzystość jest ważnym aspektem programowania. Inne osoby (i ty również!) Powinny być w stanie przeczytać i zrozumieć kod, który tworzysz. Myślę, że można bezpiecznie powiedzieć, że pętle iteracyjne są łatwiejsze do zrozumienia na pierwszy rzut oka niż rekurencja.

Nie wiem, jak dobrze znasz programowanie lub informatykę ogólnie, ale mocno czuję, że nie ma sensu mówić o funkcjach wirtualnych, dziedziczeniu ani o żadnych zaawansowanych koncepcjach. Często zaczynałem od klasycznego przykładu obliczania liczb Fibonacciego. Ładnie tu pasuje, ponieważ liczby Fibonacciego są definiowane rekurencyjnie . Jest to łatwe do zrozumienia i nie wymaga żadnych wymyślnych funkcji języka. Po tym, jak uczniowie zrozumieli podstawową wiedzę na temat rekurencji, przyjrzeliśmy się kilku prostym funkcjom, które wcześniej zbudowaliśmy. Oto przykład:

Czy ciąg zawiera znak ?$x$

Tak to robiliśmy wcześniej: iteruj ciąg i sprawdź, czy jakikolwiek indeks zawiera .$x$

bool find(const std::string& s, char x)
{
   for(int i = 0; i < s.size(); ++i)
   {
      if(s[i] == x)
         return true;
   }

   return false;
}

Pytanie brzmi: czy możemy to zrobić rekurencyjnie? Jasne, że możemy, oto jeden sposób:

bool find(const std::string& s, int idx, char x)
{
   if(idx == s.size())
      return false;

   return s[idx] == x || find(s, ++idx);
}

Kolejne naturalne pytanie brzmi: czy powinniśmy to zrobić w ten sposób? Prawdopodobnie nie. Czemu? Trudniej to zrozumieć i trudniej jest wymyślić. Dlatego też jest bardziej podatny na błędy.

Rozwiązania niektórych problemów są bardziej naturalnie wyrażane za pomocą rekurencji.

Załóżmy na przykład, że masz strukturę danych drzewa z dwoma rodzajami węzłów: liście, które przechowują wartość całkowitą; i gałęzie, które w swoich polach mają lewe i prawe poddrzewo. Załóżmy, że liście są uporządkowane, aby najniższa wartość znajdowała się w liściu najbardziej po lewej stronie.

Załóżmy, że zadaniem jest wydrukowanie wartości drzewa w kolejności. Algorytm rekurencyjny do tego celu jest całkiem naturalny:

class Node { abstract void traverse(); }
class Leaf extends Node { 
  int val; 
  void traverse() { print(val); }
} 
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

Pisanie równoważnego kodu bez rekurencji byłoby znacznie trudniejsze. Spróbuj!

Mówiąc bardziej ogólnie, rekurencja działa dobrze w przypadku algorytmów w strukturach danych rekurencyjnych, takich jak drzewa, lub w przypadku problemów, które można naturalnie podzielić na podproblemy. Sprawdź, na przykład, dziel i zdobywaj algorytmy .

Jeśli naprawdę chcesz zobaczyć rekurencję w jej najbardziej naturalnym środowisku, powinieneś spojrzeć na funkcjonalny język programowania, taki jak Haskell. W takim języku nie ma pętli, więc wszystko wyraża się za pomocą rekurencji (lub funkcji wyższego rzędu, ale to już inna historia, o której też warto wiedzieć).

Należy również zauważyć, że funkcjonalne języki programowania wykonują zoptymalizowaną rekurencję ogona. Oznacza to, że nie kładą ramki stosu, chyba że nie muszą - w zasadzie rekurencję można przekształcić w pętlę. Z praktycznego punktu widzenia możesz pisać kod w naturalny sposób, ale uzyskać wydajność kodu iteracyjnego. Dla przypomnienia, wydaje się, że kompilatory C ++ również optymalizują wywołania ogonowe , więc nie ma dodatkowego obciążenia związanego z używaniem rekurencji w C ++.

Od kogoś, kto praktycznie żyje w rekurencji , postaram się rzucić nieco światła na ten temat.

Kiedy po raz pierwszy zapoznałeś się z rekurencją, dowiadujesz się, że jest to funkcja, która się wywołuje i jest zasadniczo zademonstrowana za pomocą algorytmów takich jak przechodzenie przez drzewo. Później okazuje się, że jest często używany w programowaniu funkcjonalnym dla języków takich jak LISP i F #. Z F # piszę, większość tego, co piszę, to rekurencyjne i dopasowywanie wzorców.

Jeśli dowiesz się więcej o programowaniu funkcjonalnym, takim jak F #, dowiesz się, że listy F # są implementowane jako pojedynczo połączone listy, co oznacza, że ​​operacje, które mają dostęp tylko do nagłówka listy, to O (1), a dostęp do elementu to O (n). Kiedy się tego nauczysz, masz tendencję do przeglądania danych jako listy, budowania nowej listy w odwrotnej kolejności, a następnie odwracania listy przed powrotem z bardzo skutecznej funkcji.

Teraz, jeśli zaczniesz o tym myśleć, wkrótce zdasz sobie sprawę, że funkcje rekurencyjne będą pchać ramkę stosu za każdym razem, gdy zostanie wywołane funkcja, i może spowodować przepełnienie stosu. Jeśli jednak zbudujesz funkcję rekurencyjną, aby mogła ona wykonać wywołanie ogonowe a kompilator obsługuje możliwość optymalizacji kodu dla wywołania ogonowego. tj. .NET OpCodes.Tailcall Pole nie spowoduje przepełnienia stosu. W tym momencie zaczynasz pisać każdą pętlę jako funkcję rekurencyjną, a każdą decyzję jako dopasowanie; dni ifi whileteraz są historią.

Po przejściu na sztuczną inteligencję za pomocą cofania w takich językach, jak PROLOG, wszystko jest rekurencyjne. Chociaż wymaga to myślenia w sposób zupełnie inny niż kod imperatywny, jeśli PROLOG jest właściwym narzędziem do rozwiązania problemu, uwalnia cię od konieczności pisania wielu wierszy kodu i może radykalnie zmniejszyć liczbę błędów. Zobacz: eoTek - klient Amzi

Aby wrócić do pytania o to, kiedy użyć rekurencji; jeden sposób patrzenia na programowanie to sprzęt na jednym końcu i abstrakcyjne koncepcje na drugim końcu. Im bliżej problemu sprzętowego, tym więcej myślę w językach imperatywnych ifi whileim bardziej abstrakcyjny jest problem, tym więcej myślę w językach wysokiego poziomu z rekurencją. Jeśli jednak zaczniesz pisać kod systemu niskiego poziomu i tak dalej, i chcesz sprawdzić, czy jest on poprawny, wówczas przydadzą Ci się rozwiązania takie jak dowody twierdzeń , które w dużym stopniu opierają się na rekurencji.

Jeśli spojrzysz na Jane Street , zobaczysz, że używają funkcjonalnego języka OCaml . Chociaż nie widziałem żadnego z ich kodu, czytając o tym, co wspominają o swoim kodzie, z grubsza myślą rekurencyjnie.

EDYTOWAĆ

Ponieważ szukasz listy zastosowań, dam ci podstawowe wyobrażenie o tym, czego należy szukać w kodzie oraz listę podstawowych zastosowań, które w większości oparte są na koncepcji katamorfizmu która jest poza podstawami.

W przypadku C ++: jeśli zdefiniujesz strukturę lub klasę, która ma wskaźnik do tej samej struktury lub klasy, wówczas należy rozważyć rekurencję dla metod przejścia wykorzystujących wskaźniki.

Prosty przypadek to lista jednokierunkowa. Przetwarzasz listę zaczynając od głowy lub ogona, a następnie rekurencyjnie przechodzisz przez listę za pomocą wskaźników.

Drzewo to kolejny przypadek, w którym często stosuje się rekurencję; tak bardzo, że jeśli widzisz przechodzenie drzewa bez rekurencji, powinieneś zacząć pytać, dlaczego? To nie jest źle, ale coś, co należy zauważyć w komentarzach.

Typowe zastosowania rekurencji to:

• sortowanie
• badawczy
• mapa
• zagięcie
• filtr

Aby dać ci przypadek użycia, który jest mniej tajemny niż te podane w innych odpowiedziach: rekurencja bardzo dobrze miesza się ze strukturami klasy drzewiastej (obiektowej) pochodzącymi ze wspólnego źródła. Przykład C ++:

class Expression {
public:
    // The "= 0" means 'I don't implement this, I let my subclasses do that'
    virtual int ComputeValue() = 0;
}

class Plus : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() + right->ComputeValue(); }
}

class Times : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() * right->ComputeValue(); }
}

class Negate : public Expression {
private:
    Expression* expr;
public:
    virtual int ComputeValue() { return -(expr->ComputeValue()); }
}

class Constant : public Expression {
private:
    int value;
public:
    virtual int ComputeValue() { return value; }
}

W powyższym przykładzie użyto rekurencji: ComputeValue jest implementowana rekurencyjnie. Aby przykład działał, korzystasz z funkcji wirtualnych i dziedziczenia. Nie wiesz, czym dokładnie są lewa i prawa część klasy Plus, ale nie obchodzi cię to: może coś obliczyć swoją wartość, a to wszystko, co musisz wiedzieć.

Kluczową zaletą powyższego podejścia jest to, że każda klasa zajmuje się własnymi obliczeniami . Całkowicie oddzielasz różne implementacje wszystkich możliwych podwyrażeń: nie znają się nawzajem. Ułatwia to rozumowanie programu, a tym samym ułatwia jego zrozumienie, utrzymanie i rozszerzenie.

Pierwszym przykładem zastosowanym do nauczenia rekurencji w mojej początkowej klasie programowania była funkcja osobnego wyświetlania wszystkich cyfr w liczbie w odwrotnej kolejności.

void listDigits(int x){
     if (x <= 0)
        return;
     print x % 10;
     listDigits(x/10);
}

Lub coś w tym stylu (idę z pamięci i nie testuję). Ponadto, gdy przejdziesz do klas wyższego poziomu, będziesz używał rekurencji dużo, szczególnie w algorytmach wyszukiwania, algorytmach sortowania itp.

Może więc teraz wydawać się bezużyteczną funkcją w języku, ale na dłuższą metę jest bardzo przydatna.