Zrozumienie rekurencji [zamknięte]

Mam poważne problemy ze zrozumieniem rekurencji w szkole. Ilekroć profesor o tym mówi, wydaje mi się, że rozumiem, ale jak tylko spróbuję, to zupełnie rozwala mi mózg.

Przez całą noc próbowałem rozwiązać Towers of Hanoi i całkowicie oszalałem. Mój podręcznik ma tylko około 30 stron w rekursji, więc nie jest zbyt przydatny. Czy ktoś wie o książkach lub zasobach, które mogą pomóc w wyjaśnieniu tego tematu?

Jak opróżniasz wazon zawierający pięć kwiatów?

Odpowiedź: jeśli wazon nie jest pusty, wyjmujesz jeden kwiat, a następnie opróżniasz wazon zawierający cztery kwiaty.

Jak opróżniasz wazon zawierający cztery kwiaty?

Odpowiedź: jeśli wazon nie jest pusty, wyjmujesz jeden kwiat, a następnie opróżniasz wazon zawierający trzy kwiaty.

Jak opróżnić wazon zawierający trzy kwiaty?

Odpowiedź: jeśli wazon nie jest pusty, wyjmujesz jeden kwiat, a następnie opróżniasz wazon zawierający dwa kwiaty.

Jak opróżnić wazon zawierający dwa kwiaty?

Odpowiedź: jeśli wazon nie jest pusty, wyjmujesz jeden kwiat, a następnie opróżniasz wazon zawierający jeden kwiat.

Jak opróżnić wazon zawierający jeden kwiat?

Odpowiedź: jeśli wazon nie jest pusty, wyjmiesz jeden kwiat, a następnie opróżnisz wazon bez kwiatów.

Jak opróżnić wazon bez kwiatów?

Odpowiedź: jeśli wazon nie jest pusty, wyjmiesz jeden kwiat, ale wazon jest pusty, więc gotowe.

To powtarzalne. Uogólnijmy to:

Jak opróżniasz wazon zawierający N kwiatów?

Odpowiedź: jeśli wazon nie jest pusty, wyjmujesz jeden kwiat, a następnie opróżniasz wazon zawierający kwiaty N-1 .

Hmm, możemy to zobaczyć w kodzie?

void emptyVase( int flowersInVase ) {
  if( flowersInVase > 0 ) {
   // take one flower and
    emptyVase( flowersInVase - 1 ) ;

  } else {
   // the vase is empty, nothing to do
  }
}

Hmm, czy nie mogliśmy tego zrobić w pętli for?

Dlaczego tak, rekurencję można zastąpić iteracją, ale często rekurencja jest bardziej elegancka.

Porozmawiajmy o drzewach. W informatyce drzewo jest strukturą złożoną z węzłów , przy czym każdy węzeł ma pewną liczbę elementów potomnych, które są również węzłami lub są zerowe. Binarne drzewo jest drzewem z węzłów, które mają dokładnie dwa dzieci, zwykle nazywane „lewa” i „prawa”; znowu dzieci mogą być węzłami lub zerami. korzeń to węzeł, który nie jest dzieckiem żadnego innego węzła.

Wyobraź sobie, że węzeł oprócz swoich potomków ma wartość, liczbę i wyobraź sobie, że chcemy zsumować wszystkie wartości w jakimś drzewie.

Aby zsumować wartość w dowolnym węźle, dodalibyśmy wartość samego węzła do wartości jego lewego dziecka, jeśli istnieje, i wartości jego prawego dziecka, jeśli istnieje. Przypomnijmy teraz, że dzieci, jeśli nie są zerowe, są również węzłami.

Tak więc, podsumowując lewe dziecko, dodalibyśmy wartość samego węzła potomnego do wartości jego lewego dziecka, jeśli istnieje, i wartości jego prawego dziecka, jeśli istnieje.

Tak więc, aby zsumować wartość lewego dziecka podrzędnego, dodalibyśmy wartość samego węzła podrzędnego do wartości jego lewego dziecka, jeśli istnieje, i do wartości jego prawego dziecka, jeśli istnieje.

Być może spodziewałeś się, gdzie idę i chciałbyś zobaczyć kod? DOBRZE:

struct node {
  node* left;
  node* right;
  int value;
} ;

int sumNode( node* root ) {
  // if there is no tree, its sum is zero
  if( root == null ) {
    return 0 ;

  } else { // there is a tree
    return root->value + sumNode( root->left ) + sumNode( root->right ) ;
  }
}

Zauważ, że zamiast jawnego testowania dzieci, aby sprawdzić, czy są one puste lub węzły, po prostu sprawiamy, że funkcja rekurencyjna zwraca zero dla węzła zerowego.

Powiedzmy, że mamy drzewo, które wygląda tak (liczby są wartościami, ukośniki wskazują na dzieci, a @ oznacza wskaźnik na null):

     5
    / \
   4   3
  /\   /\
 2  1 @  @
/\  /\
@@  @@

Jeśli wywołamy sumNode w katalogu głównym (węzeł o wartości 5), zwrócimy:

return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

Rozwińmy to na miejscu. Wszędzie, gdzie widzimy sumNode, zastąpimy go rozszerzeniem instrukcji return:

sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + 0 + 0
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + sumNode(null ) + sumNode( null ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + 0 + 0 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 
 + 3  ;

return 5 + 4 
 + 2 
 + 1 
 + 3  ;

return 5 + 4 
 + 3
 + 3  ;

return 5 + 7
 + 3  ;

return 5 + 10 ;

return 15 ;

Zobaczmy teraz, jak podbiliśmy strukturę o dowolnej głębokości i „rozgałęzieniu”, traktując ją jako wielokrotne stosowanie złożonego szablonu? za każdym razem dzięki naszej funkcji sumNode mieliśmy do czynienia tylko z jednym węzłem, używając pojedynczej gałęzi if / then i dwóch prostych instrukcji return, które prawie napisały same w sobie, bezpośrednio z naszej specyfikacji?

How to sum a node:
 If a node is null 
   its sum is zero
 otherwise 
   its sum is its value 
   plus the sum of its left child node
   plus the sum of its right child node

To jest siła rekurencji.

Powyższy przykład wazy jest przykładem rekurencji ogona . Cała ta rekurencja ogona oznacza to to, że w funkcji rekurencyjnej, jeśli się powtórzyliśmy (to znaczy, jeśli ponownie wywołaliśmy funkcję), to była ostatnia rzecz, którą zrobiliśmy.

Przykład drzewa nie był rekurencyjny, ponieważ mimo że ostatnią rzeczą, którą zrobiliśmy, było ponowne skierowanie do prawego dziecka, zanim to zrobiliśmy, to powtórzyliśmy lewe dziecko.

W rzeczywistości kolejność, w której nazywaliśmy dzieci i dodawaliśmy wartość bieżącego węzła, nie miała żadnego znaczenia, ponieważ dodawanie jest przemienne.

Teraz spójrzmy na operację, w której kolejność ma znaczenie. Użyjemy binarnego drzewa węzłów, ale tym razem przechowywana wartość będzie znakiem, a nie liczbą.

Nasze drzewo będzie miało specjalną właściwość, że dla każdego węzła jego znak następuje po (w kolejności alfabetycznej) znaku w posiadaniu jego lewego dziecka, a przed (w kolejności alfabetycznej) znakiem w posiadaniu prawego dziecka.

Chcemy wydrukować drzewo w kolejności alfabetycznej. To łatwe do zrobienia, biorąc pod uwagę specjalną właściwość drzewa. Po prostu drukujemy lewe dziecko, następnie znak węzła, a następnie prawe dziecko.

Nie chcemy tylko drukować nie chcąc, więc przekażemy naszej funkcji coś do wydrukowania. Będzie to obiekt z funkcją print (char); nie musimy martwić się o to, jak to działa, po prostu, gdy wywoływane jest print, wydrukuje coś gdzieś.

Zobaczmy to w kodzie:

struct node {
  node* left;
  node* right;
  char value;
} ;

// don't worry about this code
class Printer {
  private ostream& out;
  Printer( ostream& o ) :out(o) {}
  void print( char c ) { out << c; }
}

// worry about this code
int printNode( node* root, Printer& printer ) {
  // if there is no tree, do nothing
  if( root == null ) {
    return ;

  } else { // there is a tree
    printNode( root->left, printer );
    printer.print( value );
    printNode( root->right, printer );
}

Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );

Poza kolejnością operacji, która ma teraz znaczenie, ten przykład pokazuje, że możemy przekazać rzeczy do funkcji rekurencyjnej. Jedyne, co musimy zrobić, to upewnić się, że przy każdym rekurencyjnym połączeniu nadal go przekazujemy. Do funkcji przekazaliśmy wskaźnik węzła i drukarkę, a przy każdym wywołaniu rekurencyjnym przekazaliśmy je „w dół”.

Teraz, jeśli nasze drzewo wygląda tak:

         k
        / \
       h   n
      /\   /\
     a  j @  @
    /\ /\
    @@ i@
       /\
       @@

Co wydrukujemy?

From k, we go left to
  h, where we go left to
    a, where we go left to 
      null, where we do nothing and so
    we return to a, where we print 'a' and then go right to
      null, where we do nothing and so
    we return to a and are done, so
  we return to h, where we print 'h' and then go right to
    j, where we go left to
      i, where we go left to 
        null, where we do nothing and so
      we return to i, where we print 'i' and then go right to
        null, where we do nothing and so
      we return to i and are done, so
    we return to j, where we print 'j' and then go right to
      null, where we do nothing and so
    we return to j and are done, so
  we return to h and are done, so
we return to k, where we print 'k' and then go right to
  n where we go left to 
    null, where we do nothing and so
  we return to n, where we print 'n' and then go right to
    null, where we do nothing and so
  we return to n and are done, so 
we return to k and are done, so we return to the caller

Więc jeśli popatrzymy na linie, które zostały wydrukowane:

    we return to a, where we print 'a' and then go right to
  we return to h, where we print 'h' and then go right to
      we return to i, where we print 'i' and then go right to
    we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
  we return to n, where we print 'n' and then go right to

Widzimy, że wydrukowaliśmy „ahijkn”, który rzeczywiście jest w kolejności alfabetycznej.

Udaje nam się wydrukować całe drzewo w kolejności alfabetycznej, po prostu wiedząc, jak wydrukować pojedynczy węzeł w kolejności alfabetycznej. Co było po prostu (ponieważ nasze drzewo miało specjalną właściwość porządkowania wartości po lewej stronie wartości alfabetycznie późniejszych) wiedząc, że drukuje lewe dziecko przed wydrukowaniem wartości węzła i drukuje prawe dziecko po wydrukowaniu wartości węzła.

I to jest siła rekurencji: zdolność do robienia całych rzeczy, wiedząc tylko, jak zrobić część całości (i wiedząc, kiedy przestać się powtarzać).

Przypominając, że w większości języków operator || („lub”) powoduje zwarcie, gdy pierwszy argument jest prawdziwy, ogólną funkcją rekurencyjną jest:

void recurse() { doWeStop() || recurse(); } 

Luc M komentuje:

SO powinien stworzyć odznakę dla tego rodzaju odpowiedzi. Gratulacje!

Dzięki Luc! Ale w rzeczywistości, ponieważ edytowałem tę odpowiedź więcej niż cztery razy (aby dodać ostatni przykład, ale głównie w celu poprawienia literówek i wypolerowania go - pisanie na małej klawiaturze netbooka jest trudne), nie mogę uzyskać więcej punktów za to . Co nieco zniechęca mnie do wkładania tyle wysiłku w przyszłe odpowiedzi.

Zobacz mój komentarz tutaj na ten temat: /programming/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

Twój mózg wysadził w powietrze, ponieważ wpadł w nieskończoną rekurencję. To częsty błąd początkującego.

Wierzcie lub nie, już rozumiecie rekurencję, po prostu ciągnie was zwykła, ale błędna metafora funkcji: małe pudełko z materiałami, które wchodzą i wychodzą.

Pomyśl zamiast zadania lub procedury, takich jak „dowiedz się więcej o rekurencji w sieci”. To rekurencyjne i nie masz z tym problemu. Aby wykonać to zadanie, możesz:

a) Przeczytaj stronę wyników Google dotyczącą „rekurencji”
b) Po przeczytaniu kliknij pierwszy link i ...
a.1) Przeczytaj nową stronę o rekurencji 
b.1) Po przeczytaniu kliknij pierwszy link i ...
a.2) Przeczytaj nową stronę o rekurencji 
b.2) Po przeczytaniu, kliknij pierwszy link i ...

Jak widać, od dłuższego czasu robisz rzeczy rekurencyjne bez żadnych problemów.

Jak długo miałbyś wykonywać to zadanie? Na zawsze, dopóki twój mózg nie wybuchnie? Oczywiście, że nie, zatrzymasz się w danym punkcie, ilekroć uważasz, że wykonałeś zadanie.

Nie musisz tego określać, prosząc cię o „dowiedzieć się więcej na temat rekurencji w sieci”, ponieważ jesteś człowiekiem i możesz to wywnioskować samodzielnie.

Komputer nie może wywnioskować, że jack, dlatego musisz podać wyraźne zakończenie: „dowiedz się więcej o rekurencji w sieci, dopóki NIE zrozumiesz tego lub przeczytasz maksymalnie 10 stron ”.

Wywniosłeś również, że powinieneś zacząć od strony wyników Google dotyczącej „rekurencji”, i znowu tego nie może zrobić komputer. Pełny opis naszego zadania rekurencyjnego musi również zawierać wyraźny punkt początkowy:

„dowiedz się więcej na temat rekurencji w sieci, dopóki nie zrozumiesz tego lub nie przeczytałeś maksymalnie 10 stron i zaczynasz na www.google.com/search?q=recursion ”

Aby przejrzeć całość, sugeruję wypróbowanie którejkolwiek z tych książek:

• Common Lisp: Delikatne wprowadzenie do obliczeń symbolicznych. To najsłodsze niematematyczne wyjaśnienie rekurencji.
• Mały intrygant.

Aby zrozumieć rekurencję, wystarczy spojrzeć na etykietę butelki szamponu:

function repeat()
{
   rinse();
   lather();
   repeat();
}

Problem polega na tym, że nie ma warunku zakończenia, a rekurencja będzie się powtarzać w nieskończoność lub do momentu wyczerpania szamponu lub gorącej wody (warunki zewnętrznego zakończenia, podobne do wysadzenia stosu).

Jeśli potrzebujesz książki, która dobrze wyjaśnia objaśnienie rekurencji w prostych słowach, spójrz na Gödel, Escher, Bach: An Eternal Golden Braid autorstwa Douglasa Hofstadtera, a konkretnie rozdział 5. Oprócz rekurencji nieźle się tłumaczy szereg złożonych koncepcji w informatyce i matematyce w zrozumiały sposób, z jednym wyjaśnieniem opartym na drugim. Jeśli wcześniej nie miałeś zbyt dużej styczności z tego rodzaju pojęciami, może to być naprawdę zadziwiająca książka.

To bardziej skarga niż pytanie. Czy masz bardziej szczegółowe pytanie dotyczące rekurencji? Podobnie jak w przypadku mnożenia, ludzie nie piszą dużo.

Mówiąc o pomnożeniu, pomyśl o tym.

Pytanie:

Co to jest * b?

Odpowiedź:

Jeśli b wynosi 1, to jest to. W przeciwnym razie jest to a + a * (b-1).

Co to jest * (b-1)? Zobacz powyższe pytanie, jak to rozwiązać.

Myślę, że ta bardzo prosta metoda powinna pomóc ci zrozumieć rekurencję. Metoda będzie się wywoływać do momentu spełnienia określonego warunku, a następnie zwróci:

function writeNumbers( aNumber ){
 write(aNumber);
 if( aNumber > 0 ){
  writeNumbers( aNumber - 1 );
 }
 else{
  return;
 }
}

Ta funkcja wydrukuje wszystkie liczby od pierwszej liczby, którą podasz do 0. Tak więc:

writeNumbers( 10 );
//This wil write: 10 9 8 7 6 5 4 3 2 1 0
//and then stop because aNumber is no longer larger then 0

To, co się dzieje basowo, polega na tym, że writeNumbers (10) zapisuje 10, a następnie wywołuje writeNumbers (9), które zapisuje 9, a następnie wywołuje writeNumber (8) itd. Do momentu writeNumbers (1) zapisuje 1, a następnie wywołuje writeNumbers (0), który napisze 0 butt nie wywoła writeNumbers (-1);

Ten kod jest zasadniczo taki sam jak:

for(i=10; i>0; i--){
 write(i);
}

Więc po co używać rekurencji, możesz zapytać, jeśli pętla for robi w zasadzie to samo. Cóż, najczęściej używasz rekurencji, gdy musisz zagnieżdżać pętle, ale nie wiesz, jak głęboko są zagnieżdżone. Na przykład podczas drukowania elementów z tablic zagnieżdżonych:

var nestedArray = Array('Im a string', 
                        Array('Im a string nested in an array', 'me too!'),
                        'Im a string again',
                        Array('More nesting!',
                              Array('nested even more!')
                              ),
                        'Im the last string');
function printArrayItems( stringOrArray ){
 if(typeof stringOrArray === 'Array'){
   for(i=0; i<stringOrArray.length; i++){ 
     printArrayItems( stringOrArray[i] );
   }
 }
 else{
   write( stringOrArray );
 }
}

printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'

Ta funkcja może przyjąć tablicę, która może być zagnieżdżona na 100 poziomach, a pisanie pętli for wymagałoby wtedy zagnieżdżenia jej 100 razy:

for(i=0; i<nestedArray.length; i++){
 if(typeof nestedArray[i] == 'Array'){
  for(a=0; i<nestedArray[i].length; a++){
   if(typeof nestedArray[i][a] == 'Array'){
    for(b=0; b<nestedArray[i][a].length; b++){
     //This would be enough for the nestedAaray we have now, but you would have
     //to nest the for loops even more if you would nest the array another level
     write( nestedArray[i][a][b] );
    }//end for b
   }//endif typeod nestedArray[i][a] == 'Array'
   else{ write( nestedArray[i][a] ); }
  }//end for a
 }//endif typeod nestedArray[i] == 'Array'
 else{ write( nestedArray[i] ); }
}//end for i

Jak widać metoda rekurencyjna jest znacznie lepsza.

W rzeczywistości używasz rekurencji, aby zmniejszyć złożoność problemu. Stosujesz rekurencję, aż dojdziesz do prostej skrzynki podstawowej, którą można łatwo rozwiązać. Dzięki temu możesz rozwiązać ostatni cykl rekurencyjny. I z tym wszystkimi innymi rekurencyjnymi krokami do pierwotnego problemu.

Spróbuję wyjaśnić to na przykładzie.

Wiesz co! znaczy? Jeśli nie: http://en.wikipedia.org/wiki/Factorial

3! = 1 * 2 * 3 = 6

tutaj idzie pseudokod

function factorial(n) {
  if (n==0) return 1
  else return (n * factorial(n-1))
}

Spróbujmy więc:

factorial(3)

jest n 0?

Nie!

więc pogłębiamy naszą rekurencję:

3 * factorial(3-1)

3-1 = 2

jest 2 == 0?

Nie!

więc schodzimy głębiej! 3 * 2 * silnia (2-1) 2-1 = 1

jest 1 == 0?

Nie!

więc schodzimy głębiej! 3 * 2 * 1 * silnia (1-1) 1-1 = 0

jest 0 == 0?

tak!

mamy trywialną sprawę

więc mamy 3 * 2 * 1 * 1 = 6

mam nadzieję, że ci pomogłem

Rekurencja

Metoda A wywołuje metodę A wywołuje metodę A. W końcu jedna z tych metod A nie wywołuje i nie kończy, ale jest rekurencją, ponieważ coś wywołuje samą siebie.

Przykład rekurencji, w której chcę wydrukować nazwę każdego folderu na dysku twardym: (in c #)

public void PrintFolderNames(DirectoryInfo directory)
{
    Console.WriteLine(directory.Name);

    DirectoryInfo[] children = directory.GetDirectories();

    foreach(var child in children)
    {
        PrintFolderNames(child); // See we call ourself here...
    }
}

Z której książki korzystasz?

Standardowym podręcznikiem algorytmów, który jest naprawdę dobry, jest Cormen & Rivest. Z mojego doświadczenia wynika, że ​​całkiem dobrze uczy rekursji.

Rekurencja jest jedną z trudniejszych części programowania do opanowania i chociaż wymaga instynktu, można się jej nauczyć. Ale potrzebuje dobrego opisu, dobrych przykładów i dobrych ilustracji.

Ponadto, ogólnie 30 stron to dużo, 30 stron w jednym języku programowania jest mylące. Nie próbuj uczyć się rekurencji w języku C lub Java, zanim nie zrozumiesz ogólnie rekurencji z ogólnej książki.

Funkcja rekurencyjna to po prostu funkcja, która wywołuje się tyle razy, ile jest to konieczne. Jest to przydatne, jeśli musisz przetworzyć coś wiele razy, ale nie masz pewności, ile razy będzie to faktycznie wymagane. W pewnym sensie można by pomyśleć o funkcji rekurencyjnej jako o rodzaju pętli. Jednak, podobnie jak pętla, musisz określić warunki do przerwania procesu, w przeciwnym razie stanie się nieskończony.

http://javabat.com to zabawne i ekscytujące miejsce do ćwiczenia rekurencji. Ich przykłady zaczynają się dość lekko i pracują przez obszerne (jeśli chcesz posunąć się tak daleko). Uwaga: ich podejście uczy się poprzez ćwiczenie. Oto funkcja rekurencyjna, którą napisałem, aby po prostu zastąpić pętlę for.

Pętla for:

public printBar(length)
{
  String holder = "";
  for (int index = 0; i < length; i++)
  {
    holder += "*"
  }
  return holder;
}

Oto rekursja, aby zrobić to samo. (zauważ, że przeciążamy pierwszą metodę, aby upewnić się, że jest używana tak jak powyżej). Mamy również inną metodę utrzymania naszego indeksu (podobnie jak w przypadku instrukcji for dla Ciebie powyżej). Funkcja rekurencyjna musi utrzymywać własny indeks.

public String printBar(int Length) // Method, to call the recursive function
{
  printBar(length, 0);
}

public String printBar(int length, int index) //Overloaded recursive method
{
  // To get a better idea of how this works without a for loop
  // you can also replace this if/else with the for loop and
  // operationally, it should do the same thing.
  if (index >= length)
    return "";
  else
    return "*" + printBar(length, index + 1); // Make recursive call
}

Krótko mówiąc, rekurencja jest dobrym sposobem na napisanie mniej kodu. W ostatnim printBar zauważ, że mamy instrukcję if. JEŻELI nasz warunek został osiągnięty, wyjdziemy z rekurencji i wrócimy do poprzedniej metody, która powraca do poprzedniej metody itp. Jeśli wysłałem printBar (8), otrzymam ********. Mam nadzieję, że na przykładzie prostej funkcji, która robi to samo co pętla for, może to pomoże. Możesz jednak ćwiczyć to więcej w Java Bat.

Prawdziwie matematyczny sposób patrzenia na budowę funkcji rekurencyjnej wyglądałby następująco:

1: Wyobraź sobie, że masz funkcję poprawną dla f (n-1), zbuduj f tak, aby f (n) była poprawna. 2: Zbuduj f, tak aby f (1) był poprawny.

W ten sposób możesz udowodnić, że funkcja jest poprawna matematycznie i nazywa się Indukcja . Odpowiada to różnym przypadkom bazowym lub bardziej skomplikowanym funkcjom na wielu zmiennych). Jest to również równoważne z wyobrażeniem sobie, że f (x) jest poprawne dla wszystkich x

Teraz „prosty” przykład. Zbuduj funkcję, która może określić, czy możliwe jest połączenie monet o wartości 5 centów i 7 centów, aby uzyskać x centów. Na przykład można mieć 17 centów na 2x5 + 1x7, ale nie można mieć 16 centów.

Teraz wyobraź sobie, że masz funkcję, która mówi ci, czy można utworzyć x centów, o ile x <n. Wywołaj tę funkcję can_create_coins_small. Wyobraź sobie, jak wykonać funkcję dla n. Teraz zbuduj swoją funkcję:

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins_small(n-7))
        return true;
    else if (n >= 5 && can_create_coins_small(n-5))
        return true;
    else
        return false;
}

Sztuczka polega na tym, aby zdać sobie sprawę, że fakt, że can_create_coins działa na n, oznacza, że ​​możesz zastąpić can_create_coins przez can_create_coins_small, dając:

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

Ostatnią rzeczą do zrobienia jest posiadanie podstawowego przypadku, aby zatrzymać nieskończoną rekurencję. Pamiętaj, że jeśli próbujesz utworzyć 0 centów, jest to możliwe bez posiadania monet. Dodanie tego warunku daje:

bool can_create_coins(int n)
{
    if (n == 0)
        return true;
    else if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

Można udowodnić, że ta funkcja zawsze powróci, używając metody zwanej nieskończonym zejściem , ale tutaj nie jest to konieczne. Możesz sobie wyobrazić, że f (n) wywołuje tylko niższe wartości n i zawsze ostatecznie osiągnie 0.

Aby wykorzystać te informacje do rozwiązania problemu z Wieżą Hanoi, myślę, że sztuczka polega na założeniu, że masz funkcję przenoszenia tabletów n-1 z a na b (dla dowolnego a / b), próbując przenieść n tabel z a na b .

Prosty przykład rekurencyjny w Common Lisp :

MYMAP stosuje funkcję do każdego elementu na liście.

1) pusta lista nie ma elementu, więc zwracamy pustą listę - () i NIL oba są pustą listą.

2) zastosuj funkcję do pierwszej listy, wywołaj MYMAP dla reszty listy (wywołanie rekurencyjne) i połącz oba wyniki w nową listę.

(DEFUN MYMAP (FUNCTION LIST)
  (IF (NULL LIST)
      ()
      (CONS (FUNCALL FUNCTION (FIRST LIST))
            (MYMAP FUNCTION (REST LIST)))))

Zobaczmy śledzone wykonanie. Po wejściu do funkcji argumenty są wypisywane. Po wyjściu z funkcji wynik jest drukowany. Dla każdego połączenia rekurencyjnego dane wyjściowe będą wcięte na poziomie.

Ten przykład wywołuje funkcję SIN na każdym numerze na liście (1 2 3 4).

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

To jest nasz wynik :

(0.841471 0.9092975 0.14112002 -0.75680256)

Aby wyjaśnić rekurencję sześciolatkowi, najpierw wyjaśnij pięciolatkowi, a następnie poczekaj rok.

W rzeczywistości jest to przydatny kontrprzykład, ponieważ wywołanie rekurencyjne powinno być prostsze, a nie trudniejsze. Jeszcze trudniej byłoby wytłumaczyć rekurencję pięciolatkowi i chociaż można zatrzymać rekurencję na poziomie 0, nie ma prostego rozwiązania wyjaśniającego rekurencję jednolatkowi.

Aby rozwiązać problem za pomocą rekurencji, najpierw podziel go na jeden lub więcej prostszych problemów, które możesz rozwiązać w ten sam sposób, a następnie, gdy problem jest wystarczająco prosty do rozwiązania bez dalszej rekurencji, możesz powrócić na wyższe poziomy.

W rzeczywistości była to rekurencyjna definicja sposobu rozwiązania problemu z rekurencją.

Dzieci domyślnie korzystają z rekurencji, na przykład:

Wycieczka do Disney World

Czy już tam jesteśmy? (Nie)

Czy już tam jesteśmy? (Wkrótce)

Czy już tam jesteśmy? (Prawie ...)

Czy już tam jesteśmy? (SHHHH)

Czy już dotarliśmy?(!!!!!)

W którym momencie dziecko zasypia ...

Ta funkcja odliczania jest prostym przykładem:

function countdown()
      {
      return (arguments[0] > 0 ?
        (
        console.log(arguments[0]),countdown(arguments[0] - 1)) : 
        "done"
        );
      }
countdown(10);

Istotne jest także prawo Hofstadtera stosowane w projektach oprogramowania.

Istotą ludzkiego języka jest, zdaniem Chomsky'ego, zdolność skończonych mózgów do wytwarzania tego, co uważa za nieskończoną gramatykę. Rozumie przez to nie tylko, że nie ma górnej granicy tego, co możemy powiedzieć, ale że nie ma górnej granicy liczby zdań w naszym języku, nie ma górnej granicy wielkości żadnego konkretnego zdania. Chomsky twierdził, że podstawowym narzędziem, które leży u podstaw całej tej kreatywności ludzkiego języka, jest rekurencja: zdolność jednego wyrażenia do ponownego wystąpienia w innym wyrażeniu tego samego typu. Jeśli mówię „dom brata Jana”, mam rzeczownik, „dom”, który występuje w zdaniu rzeczownikowym, „dom brata”, a to wyrażenie rzeczownikowe występuje w innym zdaniu rzeczownikowym, „domu brata Jana”. To ma wiele sensu i „

Bibliografia

• Rekurencja i ludzka myśl

Pracując z rozwiązaniami rekurencyjnymi, zawsze staram się:

• Najpierw ustal przypadek podstawowy, tj. Gdy n = 1 w rozwiązaniu silni
• Spróbuj wymyślić ogólną zasadę dla każdego innego przypadku

Istnieją również różne typy rozwiązań rekurencyjnych, istnieje podejście dziel i zwyciężaj, które jest przydatne dla fraktali i wielu innych.

Byłoby również pomocne, gdybyś mógł najpierw zająć się prostszymi problemami, aby się z tym pogodzić. Niektóre przykłady rozwiązują czynnik i generują n-tą liczbę Fibonacciego.

W celach informacyjnych gorąco polecam Algorytmy Roberta Sedgewicka.

Mam nadzieję, że to pomaga. Powodzenia.

Auć. W zeszłym roku próbowałem wymyślić Wieże Hanoi. Trudną rzeczą w TOH jest to, że nie jest to prosty przykład rekurencji - zagnieżdżono rekurencje, które również zmieniają role wież przy każdym wywołaniu. Jedynym sposobem, w jaki mogłem to zrobić, było dosłownie wizualizować ruch pierścieni w oku mojego umysłu i werbalizować, co to będzie rekurencyjne wezwanie. Zacznę od jednego pierścienia, potem dwóch, a potem trzech. Właściwie zamówiłem grę w Internecie. Zajęło mi to może dwa lub trzy dni łamanie sobie mózgu, aby je zdobyć.

Funkcja rekurencyjna jest jak sprężyna, którą nieco kompresujesz przy każdym wywołaniu. Na każdym kroku umieszczasz na stosie trochę informacji (aktualny kontekst). Po osiągnięciu ostatniego kroku sprężyna zostaje zwolniona, zbierając wszystkie wartości (konteksty) naraz!

Nie jestem pewien, czy ta metafora jest skuteczna ... :-)

W każdym razie, poza klasycznymi przykładami (silnia, która jest najgorszym przykładem, ponieważ jest nieefektywna i łatwo spłaszczona, Fibonacciego, Hanoi ...), które są nieco sztuczne (rzadko, jeśli w ogóle, używam ich w prawdziwych przypadkach programowania), jest to Ciekawe, gdzie jest naprawdę używany.

Bardzo częstym przypadkiem jest chodzenie po drzewie (lub wykresie, ale drzewa są bardziej powszechne).
Na przykład hierarchia folderów: aby wyświetlić listę plików, iterujesz je. Jeśli znajdziesz podkatalog, funkcja wyświetlająca pliki wywołuje się z nowym folderem jako argumentem. Wracając z listy tego nowego folderu (i jego podfolderów!), Wznawia kontekst, do następnego pliku (lub folderu).
Innym konkretnym przypadkiem jest rysowanie hierarchii komponentów GUI: zwykle pojemniki, takie jak panele, przechowują komponenty, które mogą być również panelami, lub komponenty złożone itp. Procedura malowania wywołuje rekurencyjnie funkcję malowania każdego komponentu, która wywołuje funkcję malowania wszystkich posiadanych elementów itp.

Nie jestem pewien, czy jestem bardzo jasny, ale lubię pokazywać wykorzystanie materiałów dydaktycznych w świecie rzeczywistym, ponieważ natrafiłem na to w przeszłości.

Pomyśl o pszczole robotniczej. Próbuje zrobić miód. Wykonuje swoją pracę i oczekuje, że inne pszczoły robotnice zrobią resztę miodu. A kiedy plaster miodu jest pełny, zatrzymuje się.

Pomyśl o tym jak o magii. Masz funkcję o tej samej nazwie co ta, którą próbujesz wdrożyć, a gdy podasz jej podproblem, rozwiązuje to dla Ciebie, a jedyne, co musisz zrobić, to zintegrować rozwiązanie swojej części z rozwiązaniem dałem ci.

Na przykład chcemy obliczyć długość listy. Nazwijmy naszą funkcję magical_length i naszego magicznego pomocnika za pomocą magical_length Wiemy, że jeśli podamy podlistę, która nie ma pierwszego elementu, da nam długość podlisty za pomocą magii. Jedyne, co musimy pomyśleć, to jak zintegrować te informacje z naszą pracą. Długość pierwszego elementu wynosi 1, a magic_counter daje nam długość podlisty n-1, dlatego całkowita długość wynosi (n-1) + 1 -> n

int magical_length( list )
  sublist = rest_of_the_list( list )
  sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
  return 1 + sublist_length

Ta odpowiedź jest jednak niepełna, ponieważ nie zastanawialiśmy się, co się stanie, jeśli podamy pustą listę. Myśleliśmy, że lista, którą zawsze mamy, zawiera co najmniej jeden element. Dlatego musimy zastanowić się, jaka powinna być odpowiedź, jeśli otrzymamy pustą listę, a odpowiedź to oczywiście 0. Dodaj więc tę informację do naszej funkcji i nazywa się to stanem bazowym / krawędziowym.

int magical_length( list )
  if ( list is empty) then
    return 0
  else
    sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
    return 1 + sublist_length