Рекурсия против итерации в отношении использования памяти

Question

Предположим, что у меня есть рекурсивное, а также итеративное решение (с использованием стека) с некоторой проблемой, например. предварительный обход бинарного дерева. С текущими компьютерами с памятью есть ли преимущество использования рекурсивного решения над итеративной версией или наоборот для очень больших деревьев?

Я знаю, что для некоторых рекурсивных решений, в которых повторяются подзапросы, при использовании рекурсии есть дополнительные затраты времени и памяти. Предположим, что это не так. Например,

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

против

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

Если существует опасность переполнения стека (в данном случае, потому что деревья не гарантированно даже полу-сбалансированный), то надежная программа будет избежать рекурсии и использовать явный стек.

Явный стек может использовать меньше памяти, поскольку фреймы стека имеют тенденцию быть больше, чем это необходимо для поддержания контекста рекурсивных вызовов. (Например, кадр стека будет содержать, по крайней мере, адрес возврата, а также локальные переменные.)

Однако, если известно, что глубина рекурсии ограничена, то не требуется динамическое распределение, это может сэкономить пространство и время, а также время программиста. Например, для перехода к сбалансированному двоичному дереву требуется только рекурсия на глубину дерева, то есть log количества узлов; это не может быть очень большим числом.

Как было предложено комментатором, один из возможных сценариев состоит в том, что дерево, как известно, правильно перекошено. В этом случае вы можете перезаписывать левые ветви, не беспокоясь о переполнении стека (если вы абсолютно уверены, что дерево правильно перекошено). Так как второй рекурсивный вызов находится в положении хвоста, он просто может быть переписан в виде петли:

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

Подобный метод часто (и всегда должен быть) применяется для сортировки: после разделения, функция рекурсивен на меньшем разделе, а затем петли для обработки большего раздела. Поскольку меньший раздел должен быть меньше половины размера исходного массива, это гарантирует, что глубина рекурсии будет меньше, чем log исходного размера массива, который, конечно, меньше 50 кадров стека и, вероятно, намного меньше ,