Rekursja vs iteracja w odniesieniu do użycia pamięci

Question

Załóżmy, że mam rozwiązanie rekursywne, a także iteracyjne (używając stosu) do jakiegoś problemu, np. preorder traversal drzewa binarnego. Z obecnymi komputerami, pod kątem pamięci, czy istnieje korzyść z zastosowania rozwiązania rekursywnego w iteracyjnej wersji lub odwrotnie dla bardzo dużych drzew?

Jestem świadomy, że w przypadku niektórych rozwiązań rekursywnych, w których powtarzają się problemy podrzędne, dodatkowe koszty związane z pamięcią i pamięcią mają miejsce w przypadku rekursji. Załóżmy, że tak nie jest w tym przypadku. Na przykład,

preOrder(Node n){ 
    if (n == null) return; 
    print(n); 
    preOrder(n.left); 
    preOrder(n.right); 
} 

vs

preOrder(Node n){ 
    stack s; 
    s.push(n); 
    while(!s.empty()){ 
     Node node = s.pop(); 
     print(node); 
     s.push(node.right); 
     s.push(node.left); 
    } 
} 

Answer 1

Jeżeli istnieje ryzyko jego przepełnienia (w tym przypadku, ponieważ drzewa nie są gwarantowane jeszcze częściowo zrównoważone), a następnie solidny program będzie unikaj rekursji i używaj jawnego stosu.

Stos jawny może zużywać mniej pamięci, ponieważ ramki stosów są zwykle większe niż jest to absolutnie konieczne, aby utrzymać kontekst wywołań rekursywnych. (Na przykład ramka stosu będzie zawierała przynajmniej adres zwrotny, a także zmienne lokalne.)

Jeśli jednak wiadomo, że głębokość rekursji jest ograniczona, to brak konieczności dynamicznego przydzielania może zaoszczędzić miejsce i czas, jak również czas programisty. Na przykład chodzenie w zbalansowanym drzewie binarnym wymaga rekursji tylko do głębokości drzewa, co jest logiczną liczbą węzłów; to nie może być bardzo duża liczba.

Zgodnie z sugestią komentatora, jednym z możliwych scenariuszy jest to, że drzewo jest skosowane z prawej strony. W takim przypadku możesz powrócić do lewej gałęzi bez martwienia się o przepełnienie stosu (o ile masz całkowitą pewność, że drzewo jest przekrzywione w prawo). Ponieważ drugi rekurencyjne połączenia znajduje się w położeniu tylnego, może po prostu być zapisane jako pętla:

void preOrder(Node n) { 
    for (; n; n = n.right) { 
     print(n); 
     preOrder(n.left); 
     n = n.right; 
} 

Podobna technika jest często (i zawsze powinny być) stosowane do quicksort Po podziału funkcja recurses na mniejszej partycji, a następnie pętle do obsługi większej partycji. Ponieważ mniejsza partycja musi być mniejsza niż połowa rozmiaru oryginalnej tablicy, co zagwarantuje, że głębokość rekurencji będzie mniejsza niż log oryginalnego rozmiaru tablicy, która z pewnością jest mniejsza niż 50 klatek stosu i prawdopodobnie o wiele mniej .