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