Jak działa rekurencja wewnątrz pętli

Question

Jestem nowy w rekursji i próbuję zrozumieć ten fragment kodu. Uczę się na egzamin, a to jest "recenzent", którego znalazłem w Standford CIS Education Library (From Binary Trees, Nick Parlante).

Rozumiem koncepcję, ale kiedy recytujemy W PĘTLI, to wszystko wieje! Proszę pomóż mi. Dziękuję Ci.

countTrees() rozwiązanie (C/C++)

/* 
For the key values 1...numKeys, how many structurally unique 
binary search trees are possible that store those keys. 
Strategy: consider that each value could be the root. 
Recursively find the size of the left and right subtrees. 
*/ 

int countTrees(int numKeys) { 
    if (numKeys <=1) { 
     return(1); 
    } 

    // there will be one value at the root, with whatever remains 
    // on the left and right each forming their own subtrees. 
    // Iterate through all the values that could be the root... 

    int sum = 0; 
    int left, right, root; 

    for (root=1; root<=numKeys; root++) { 
     left = countTrees(root - 1); 
     right = countTrees(numKeys - root); 
     // number of possible trees with this root == left*right 
     sum += left*right; 
    } 

    return(sum); 
} 

Answer 1

Wyobraź pętla mogą być wprowadzane "na przerwie", natomiast udać się do wywołania funkcji.

Tylko dlatego, że funkcja jest wywołaniem rekursywnym, działa tak samo, jak każda funkcja wywoływana w pętli.

Nowe wywołanie cykliczne rozpoczyna się od pętli for i ponownie zatrzymuje się podczas ponownego wywoływania funkcji i tak dalej.

Answer 2

Możesz myśleć o tym ze skrzynki bazowej, pracując w górę.

Tak, dla przypadku podstawowego masz 1 (lub mniej) węzłów. Jest tylko 1 strukturalnie unikalne drzewo, które jest możliwe z 1 węzłem - to jest sam węzeł. Tak więc, jeśli numKeys jest mniejsze lub równe 1, po prostu zwróć 1.

Załóżmy teraz, że masz więcej niż 1 klucz. Cóż, jednym z tych kluczy jest root, niektóre elementy znajdują się w lewej gałęzi, a niektóre przedmioty znajdują się w prawej gałęzi.

Jak duże są lewe i prawe gałęzie? To zależy od tego, co jest elementem głównym. Ponieważ musisz wziąć pod uwagę całkowitą liczbę możliwych drzew, musimy wziąć pod uwagę wszystkie konfiguracje (wszystkie możliwe wartości root) - więc sprawdzamy wszystkie możliwe wartości.

Dla każdej iteracji wiemy, że ja znajduje się w katalogu głównym, i - 1 węzły znajdują się na lewej gałęzi, a numKeys - węzły są na prawej gałęzi. Ale, oczywiście, mamy już funkcję, która zlicza całkowitą liczbę konfiguracji drzew, biorąc pod uwagę liczbę węzłów! To funkcja, którą piszemy. Tak więc, rekurencyjne wywołanie funkcji, aby uzyskać liczbę możliwych konfiguracji drzewa lewej i prawej poddrzewi. Całkowita liczba drzew możliwych przy pomocy i w katalogu głównym jest wtedy iloczynem tych dwóch liczb (dla każdej konfiguracji lewego poddrzewa, mogą się zdarzyć wszystkie możliwe prawe poddrzewa).

Po podsumowaniu wszystkiego gotowe.

Tak więc, jeśli w pewnym sensie to ułożysz, nie ma nic nadzwyczajnego w wywołaniu funkcji rekursywnie z pętli - to tylko narzędzie, którego potrzebujemy do naszego algorytmu. Poleciłbym (tak jak Grammin) uruchomić go za pomocą debuggera i zobaczyć, co dzieje się na każdym etapie.

Answer 3

spojrzeć na to w ten sposób: Jest 3 możliwe przypadki dla początkowego połączenia:

numKeys = 0 
numKeys = 1 
numKeys > 1 

W 0 i 1 przypadki są proste - po prostu funkcja zwraca 1 i gotowe. Dla numkeys 2, możesz skończyć z:

sum = 0 
loop(root = 1 -> 2) 
    root = 1: 
     left = countTrees(1 - 1) -> countTrees(0) -> 1 
     right = countTrees(2 - 1) -> countTrees(1) -> 1 
     sum = sum + 1*1 = 0 + 1 = 1 
    root = 2: 
     left = countTrees(2 - 1) -> countTrees(1) -> 1 
     right = countTrees(2 - 2) -> countTrees(0) -> 1 
     sum = sum + 1*1 = 1 + 1 = 2 

output: 2 

dla numKeys = 3:

sum = 0 
loop(root = 1 -> 3): 
    root = 1: 
     left = countTrees(1 - 1) -> countTrees(0) -> 1 
     right = countTrees(3 - 1) -> countTrees(2) -> 2 
     sum = sum + 1*2 = 0 + 2 = 2 
    root = 2: 
     left = countTrees(2 - 1) -> countTrees(1) -> 1 
     right = countTrees(3 - 2) -> countTrees(1) -> 1 
     sum = sum + 1*1 = 2 + 1 = 3 
    root = 3: 
     left = countTrees(3 - 1) -> countTrees(2) -> 2 
     right = countTrees(3 - 3) -> countTrees(0) -> 1 
     sum = sum + 2*1 = 3 + 2 = 5 

output 5 

i tak dalej.Ta funkcja jest najprawdopodobniej O (n^2), ponieważ dla każdego n kluczy uruchamiane są 2 * n-1 wywołania rekursywne, co oznacza, że ​​jego środowisko wykonawcze będzie rosło bardzo szybko.

Answer 4

Każde połączenie ma własną przestrzeń zmiennych, jak można się spodziewać. Złożoność wynika z faktu, że wykonanie funkcji jest "przerywane" w celu wykonania -again- tej samej funkcji. ten kod:

for (root=1; root<=numKeys; root++) { 
     left = countTrees(root - 1); 
     right = countTrees(numKeys - root); 
     // number of possible trees with this root == left*right 
     sum += left*right; 
    } 

mógłby zostać przepisany w ten sposób w czystym C:

root = 1; 
Loop: 
    if (!(root <= numkeys)) { 
     goto EndLoop; 
    } 

    left = countTrees(root -1); 
    right = countTrees (numkeys - root); 
    sum += left * right 

    ++root; 
    goto Loop; 
EndLoop: 
// more things... 

To jest rzeczywiście tłumaczone przez kompilator do czegoś takiego, ale w asemblerze. Jak widać pętla jest kontrolowana przez parę zmiennych, numkeys i root, a ich wartości nie są modyfikowane z powodu wykonania innej instancji z tej samej procedury. Gdy wywołanie zwróci, wywołujący wznawia wykonywanie, z tymi samymi wartościami dla wszystkich wartości, które miał przed wywołaniem rekursywnym.

Answer 5

Wystarczy pamiętać, że wszystkie zmienne lokalne, takie jak numKeys, sum, left, right, root są w pamięci stosu. Po przejściu do głębokości funkcji rekursywnej n-th, będą dostępne kopie tych zmiennych lokalnych n. Kiedy zakończy wykonywanie jednej głębokości, jedna kopia tej zmiennej zostanie wyskoczona ze stosu.

W ten sposób zrozumiesz, że głębokość następnego poziomu NIE wpłynie na lokalne zmienne głębokości poziomu bieżącego (JEŻELI używasz referencji, ale NIE jesteśmy w tym konkretnym problemie).

Dla tego konkretnego problemu należy zwrócić szczególną uwagę na złożoność czasową. Oto moje rozwiązania:

/* Q: For the key values 1...n, how many structurally unique binary search 
     trees (BST) are possible that store those keys. 
     Strategy: consider that each value could be the root. Recursively 
     find the size of the left and right subtrees. 
     http://stackoverflow.com/questions/4795527/ 
      how-recursion-works-inside-a-for-loop */ 
/* A: It seems that it's the Catalan numbers: 
     http://en.wikipedia.org/wiki/Catalan_number */ 
#include <iostream> 
#include <vector> 
using namespace std; 

// Time Complexity: ~O(2^n) 
int CountBST(int n) 
{ 
    if (n <= 1) 
     return 1; 

    int c = 0; 
    for (int i = 0; i < n; ++i) 
    { 
     int lc = CountBST(i); 
     int rc = CountBST(n-1-i); 
     c += lc*rc; 
    } 

    return c; 
} 

// Time Complexity: O(n^2) 
int CountBST_DP(int n) 
{ 
    vector<int> v(n+1, 0); 
    v[0] = 1; 

    for (int k = 1; k <= n; ++k) 
    { 
     for (int i = 0; i < k; ++i) 
      v[k] += v[i]*v[k-1-i]; 
    } 

    return v[n]; 
} 

/* Catalan numbers: 
      C(n, 2n) 
    f(n) = -------- 
      (n+1) 
       2*(2n+1) 
    f(n+1) = -------- * f(n) 
       (n+2) 

    Time Complexity: O(n) 
    Space Complexity: O(n) - but can be easily reduced to O(1). */ 
int CountBST_Math(int n) 
{ 
    vector<int> v(n+1, 0); 
    v[0] = 1; 

    for (int k = 0; k < n; ++k) 
     v[k+1] = v[k]*2*(2*k+1)/(k+2); 

    return v[n]; 
} 

int main() 
{ 
    for (int n = 1; n <= 10; ++n) 
     cout << CountBST(n) << '\t' << CountBST_DP(n) << 
           '\t' << CountBST_Math(n) << endl; 

    return 0; 
} 
/* Output: 
1  1  1 
2  2  2 
5  5  5 
14  14  14 
42  42  42 
132  132  132 
429  429  429 
1430 1430 1430 
4862 4862 4862 
16796 16796 16796 
*/