Блог

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

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

 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);
    }
}
  

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

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

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

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

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

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