Pull to refresh

Comments 41

Нужно понимать, что итерация не всегда лучше рекурсии:


  • некоторые случаи рекурсии сам компилятор умеет оптимизировать и разворачивать в циклы
  • есть вещи, которые имеет смысл разворачивать (под смыслом я понимаю производительность/читаемость/...)
  • есть вещи, где рекурсия естественна со всех точек зрения

Абсолютно согласен с вами!


Насчёт оптимизации добавлю, что нужно чтобы Максим знал, каким требованиям должна соответствовать рекурсия, чтобы компилятор/интерпретатор мог оптимизировать её с помощью Tail Call Optimization. Если вы о ней.


Чтобы функция факториала была оптимизирована её нужно будет переписать вот так:


function factorial(n, acc = 1) {
  if (n <= 1) return acc
  return factorial(n-1, acc * n)
}

Изначальная вариант не будет оптимизирован в итерацию. Насколько я знаю, конечно.


Насчёт второго, мне больнее всего за читаемость, при таких разворотах.


Спасибо за комментарий, очень полезные примечания

В JavaScript нет Tail Call Optimization, можете проверить свой пример в консольке.

Насчет рекурсии — можно еще сделать memo, в которой запоминать результат выполнения рекурсивных функций и не проваливаться глубже в рекурсию, если результат уже есть в memo

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


В любом случае такая оптимизация предусмотрена стандартом:
https://www.ecma-international.org/ecma-262/11.0/index.html#sec-evaluatecall


Спасибо за поправку, необходимо было упомянуть, что эта оптимизация не во всех интерпретаторах/компиляторах есть, и в том числе в большинстве Javascript интерпретаторов.


Мемоизация поможет с глубиной только на последующих вызовах. Первый вызов — будет иметь полную глубину рекурсии.

Дополню:


  • бывают случаи, когда рекурсия затрудняет отладку (стек-трейс ошибки большой и неинформативный).

Да!


Не знаю насчёт развёрнутой итерации в сложных случаях будет ли она проще для дебагинга, но согласен, что когда stack-trace огромный это бывает сбивает с толку.


Спасибо за комментарий!

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

отладка может не понадобиться

Сразу будет ясно что стек переполнится?

Ну да, сразу, в отличие от внезапных бесконечных циклов.

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

Всё в статье как бы правильно… Но вот почему-то каждый раз, когда встречаю такой подход к решению задач, с тоской понимаю, что быстрых компьютеров никогда не будет — будут все более медленные программы, так как программисты перестают быть инженерами и математиками, всё больше надо оказывается абстракций и документаций и всякой функциональщины, всё менее надо думать над тем, чтобы сложное упростить…
А я считаю, что главное это борьба со сложностью… А как считаете вы?

Считаю, что если нечто можно написать просто — необходимо писать просто.


Также считаю, что если абстракция не упрощает — то необходимо доказать, зачем она нужна прежде чем добавлять её в проект.


Интересно узнать, что именно вы бы поменяли в этом решении. Хотя бы в общих чертах.


В любом случае, спасибо за комментарий!

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

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

Мои претензии конкретно к редьюксу. А концептуально структуры весьма красивы, хоть и заставляют GC постоянно приходить.
GC не бесплатен + рантайм затраты на выделение памяти + куча ФП обёрток как правило
GC не бесплатен

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


рантайм затраты на выделение памяти

Выделить память в gen 0 — сдвинуть указатель в подавляющем большинстве случаев (если не триггерится GC).


куча ФП обёрток как правило

Это я не понял.

так как программисты перестают быть инженерами и математиками, всё больше надо оказывается абстракций и документаций и всякой функциональщины

Но ведь математики и топят за функциональщину!

У меня тоже возник такой диссонанс, но мне показалось, что я просто не понял мысль комментатора и/или он имел в виду некий другой аспект математиков.

я имел в виду всё-же инженерами и математиками — ну то есть не все математики имеют инженерный склад ума, но вот именно они-то тут и имелись в виду, прикладные математики (как я..).
Даже и не знаю — если вы про модельную задачу с факториалом, то я бы использовал в зависимости от условий или приближенную формулу или цикл, конечно не рекурсию. В плане модельного примера я бы взял, например, функцию Аккермана — там нет (совсем) итеративного решения и это отличный пример для рекурсии.
А на практике вот недавно пришлось писать итеративное решение со стеком для обратного обхода леса деревьев — вот могу привести кусок кода
int stack_ptr = 0;
stack[stack_ptr] = k;
while (stack_ptr >= 0) {
      int first = stack[stack_ptr];
      int prev = -1;
      if (first > 0)
          for (int s = first - 1; A[s].var2 >= last; prev = s, s =  A[s].var2)
          if (A[s].index_to == first) {
                       ...
                      stack[++stack_ptr] = s;
                      if (prev > 0)
                          A[prev].var2 = A[s].var2;
                      goto next;
         }
        stack_ptr--;
       next: continue;
}

Изначально код был у меня на Прологе и, естественно, рекурсивный. Но при переносе на С стек стало очень жалко и после профилирования выяснилось, что так быстрее

Да, функция Аккермана была бы очень в тему для модельного примера, спасибо за ответ!


Люблю пролог. Самое необычное из того на чем приходилось писать.


Интересно в какой области у вас возникли такие задачи?

это из области автоматизированной системы планирования…
Я пишу на типизированных, языках с ссылочными типами(pointer/reference/*type). В таких языках некоторые типы естественным образом определяются рекурсивно. Например дерево это узел и две ссылки на левое и правое дерево — ветви. Поскольку дерево в алгоритмистике традиционно рекурсивная структура то и классические алгоритмы на нем прописаны рекурсивно и они тривиально переводятся в код. Однако, когда в целях оптимизации пытаешься рекурсивный код на рекурсивных структурах развернуть в последовательный/цикл — выходит туго. Интересно было бы посмотреть как это делается на JavaScript — просто поиск по дереву без рекурсии.

В глубину или в ширину?

Просто найти и удалить или заменить узел, BFS или DFS как вам удобней(собственно стек или очередь)

Пример итерации по дереву на Typescript. На Javascript было бы точно так, только без типов.


type Tree<T> = INode<T> | null

interface INode<T> {
    value: T,
    left: Tree<T>,
    right: Tree<T>
}

function breadthFirstIterate<T>(tree: Tree<T>, callback: (value: T) => void) {
    if (!tree) return
    const nodes: INode<T>[] = [tree]

    while (nodes.length > 0) {
        const node = nodes.shift() as INode<T>
        callback(node.value)
        if (node.left) {
            nodes.push(node.left)
        }
        if (node.right) {
            nodes.push(node.right)
        }
    }
}

function depthFirstIterate<T>(tree: Tree<T>, callback: (value: T) => void) {
    if (!tree) return
    const nodes: INode<T>[] = [tree]
    while (nodes.length > 0) {
        const node = nodes.pop() as INode<T>
        callback(node.value)
        if (node.right) {
            nodes.push(node.right)
        }
        if (node.left) {
            nodes.push(node.left)
        }
    }
}

Здесь итерация в ширину и в длину. Итерация в ширину не оптимально быстрая так как массив в JS не очень хорош для организации очереди. Лучше создать односвязный список, чтобы получение очередной ноды была операция за O(1). А не О(n).


Насчёт удаления или замены. Тут зависит от того, хочу ли я на выходе получить то же дерево что изначально с изменениями, или построить новое дерево с применёнными измениями.


Такого раньше не писал итеративно, но сейчас попробую

Спасибо. Интересно. Не хотите добавить в основной текст?

Удаление с мутацией основного дерева без рекурсии. Очень сложный но вроде работает:


function findMostRightNodeWithParent<T>(tree: INode<T>): [INode<T>, INode<T> | null] {
    let parent: INode<T> | null = null
    let currentNode = tree
    while (currentNode.right) {
        parent = currentNode
        currentNode = currentNode.right
    }

    return [currentNode, parent]
}

function mutableRemove<T>(tree: Tree<T>, value: T): Tree<T> {
    if (!tree) return null
    const nodesWithParent: [INode<T>, INode<T> | null][] = [[tree, null]]
    let foundTree: INode<T> | null = null
    let foundTreeParent: INode<T> | null = null
    while (nodesWithParent.length > 0) {
        const [node, nodeParent] = nodesWithParent.pop() as [INode<T>, INode<T> | null]
        if (node.value === value) {
            foundTree = node
            foundTreeParent = nodeParent
            break
        }
        if (node.right) {
            nodesWithParent.push([node.right, node])
        }
        if (node.left) {
            nodesWithParent.push([node.left, node])
        }
    }
    // Такого элемента нет в дереве
    if (!foundTree) return tree
    // Такой элемент это корень дерева
    if (!foundTreeParent) {
        // если нет левого поддерева возвращаем правое поддерево
        if (!foundTree.left) return foundTree.right
        // если нет правого поддерева возвращаем левое поддерево
        if (!foundTree.right) return foundTree.left
        // Если есть и правое и левое, то ищем самый правый элемент левого поддерева, и ставим его в голову дерева. Удаляем его снизу
        const [mostRight, mostRightParent] = findMostRightNodeWithParent(foundTree.left)
        if (mostRightParent) {
            mostRightParent.right = mostRight.left
        }
        foundTree.value = mostRight.value
        return foundTree
    }

    const direction = foundTreeParent.left === foundTree ? 'left' : 'right'
    // Если это лист - удаляем его
    if (!foundTree.left && !foundTree.right) {
        foundTreeParent[direction] = null
        return tree
    }
    // Если это элемент - не содержит одной из ветвей - то ту ветвь которая есть присвоить родителю найденой ветви
    if (!foundTree.left) {

        foundTreeParent[direction] = foundTree.right
        return tree
    }
    if (!foundTree.right) {
        foundTreeParent[direction] = foundTree.left
        return tree
    }
    let [mostRightChild, mostRightChildParent] = findMostRightNodeWithParent(foundTree.left)
    // если есть промежуточный родитель до самого правого слева
    if (mostRightChildParent) {
        mostRightChildParent.right = mostRightChild.left
    } else {
        // промежуточного родителя слева нет
        foundTree.left = mostRightChild.left
    }
    foundTree.value = mostRightChild.value
    return tree
}

Добавлю ссылку на эту ветку комментариев в конец, спасибо за ваши комментарии! Я так мозгом давно не воротил)

В первом примере у вас ручная реализация абстракции call stack, которую обычно делегируют операционной системе или виртуальной машине. Если добавить примитивную трассировку, то видно, что в вашем стэке (который todoStack) будет столько же кадров, сколько было бы в стэке потока ОС, исполняющего «наивный» рекурсивный алгоритм с таким же входным значением. Вот смотрите,
добавляем трассировку в вашу функцию
function factorial(n) {
  if (n <= 1) return 1;

  let result = 0;
  const todoStack = [];

  todoStack.push({ type: "multiplyBy", multiplier: n });
  todoStack.push({ type: "calculateFactorial", value: n - 1 });

  while (todoStack.length > 0) {
    const task = todoStack.pop();
    console.log('stack size after pop: ' + todoStack.length);

    if (task.type === "multiplyBy") {
      const { multiplier } = task;
      result *= multiplier;
      continue;
    }

    if (task.type === "calculateFactorial") {
      const { value } = task;

      // «Тривиальный» случай
      if (value <= 1) {
        result = 1;
        continue;
      }

      // Не «тривиальный», планируем новые задачи.
      todoStack.push({ type: "multiplyBy", multiplier: value });
      console.log('pushing multiplyBy, value: ' + value, 'stack size after first push: ' + todoStack.length);
      todoStack.push({ type: "calculateFactorial", value: value - 1 });
      console.log('pushing calculateFactorial, value: ' + (value - 1), 'stack size after second push: ' + todoStack.length);
      continue;
    }
  }
  return result;
}



и даем ей на вход 100
factorial(100)
stack size after pop: 1
pushing multiplyBy, value: 99 stack size after first push: 2
pushing calculateFactorial, value: 98 stack size after second push: 3
stack size after pop: 2
pushing multiplyBy, value: 98 stack size after first push: 3
pushing calculateFactorial, value: 97 stack size after second push: 4
stack size after pop: 3
pushing multiplyBy, value: 97 stack size after first push: 4
pushing calculateFactorial, value: 96 stack size after second push: 5
stack size after pop: 4
pushing multiplyBy, value: 96 stack size after first push: 5
pushing calculateFactorial, value: 95 stack size after second push: 6
stack size after pop: 5
pushing multiplyBy, value: 95 stack size after first push: 6
pushing calculateFactorial, value: 94 stack size after second push: 7
stack size after pop: 6
pushing multiplyBy, value: 94 stack size after first push: 7
pushing calculateFactorial, value: 93 stack size after second push: 8
stack size after pop: 7
pushing multiplyBy, value: 93 stack size after first push: 8
pushing calculateFactorial, value: 92 stack size after second push: 9
stack size after pop: 8
pushing multiplyBy, value: 92 stack size after first push: 9
pushing calculateFactorial, value: 91 stack size after second push: 10
stack size after pop: 9
pushing multiplyBy, value: 91 stack size after first push: 10
pushing calculateFactorial, value: 90 stack size after second push: 11
stack size after pop: 10
pushing multiplyBy, value: 90 stack size after first push: 11
pushing calculateFactorial, value: 89 stack size after second push: 12
stack size after pop: 11
pushing multiplyBy, value: 89 stack size after first push: 12
pushing calculateFactorial, value: 88 stack size after second push: 13
stack size after pop: 12
pushing multiplyBy, value: 88 stack size after first push: 13
pushing calculateFactorial, value: 87 stack size after second push: 14
stack size after pop: 13
pushing multiplyBy, value: 87 stack size after first push: 14
pushing calculateFactorial, value: 86 stack size after second push: 15
stack size after pop: 14
pushing multiplyBy, value: 86 stack size after first push: 15
pushing calculateFactorial, value: 85 stack size after second push: 16
stack size after pop: 15
pushing multiplyBy, value: 85 stack size after first push: 16
pushing calculateFactorial, value: 84 stack size after second push: 17
stack size after pop: 16
pushing multiplyBy, value: 84 stack size after first push: 17
pushing calculateFactorial, value: 83 stack size after second push: 18
stack size after pop: 17
pushing multiplyBy, value: 83 stack size after first push: 18
pushing calculateFactorial, value: 82 stack size after second push: 19
stack size after pop: 18
pushing multiplyBy, value: 82 stack size after first push: 19
pushing calculateFactorial, value: 81 stack size after second push: 20
stack size after pop: 19
pushing multiplyBy, value: 81 stack size after first push: 20
pushing calculateFactorial, value: 80 stack size after second push: 21
stack size after pop: 20
pushing multiplyBy, value: 80 stack size after first push: 21
pushing calculateFactorial, value: 79 stack size after second push: 22
stack size after pop: 21
pushing multiplyBy, value: 79 stack size after first push: 22
pushing calculateFactorial, value: 78 stack size after second push: 23
stack size after pop: 22
pushing multiplyBy, value: 78 stack size after first push: 23
pushing calculateFactorial, value: 77 stack size after second push: 24
stack size after pop: 23
pushing multiplyBy, value: 77 stack size after first push: 24
pushing calculateFactorial, value: 76 stack size after second push: 25
stack size after pop: 24
pushing multiplyBy, value: 76 stack size after first push: 25
pushing calculateFactorial, value: 75 stack size after second push: 26
stack size after pop: 25
pushing multiplyBy, value: 75 stack size after first push: 26
pushing calculateFactorial, value: 74 stack size after second push: 27
stack size after pop: 26
pushing multiplyBy, value: 74 stack size after first push: 27
pushing calculateFactorial, value: 73 stack size after second push: 28
stack size after pop: 27
pushing multiplyBy, value: 73 stack size after first push: 28
pushing calculateFactorial, value: 72 stack size after second push: 29
stack size after pop: 28
pushing multiplyBy, value: 72 stack size after first push: 29
pushing calculateFactorial, value: 71 stack size after second push: 30
stack size after pop: 29
pushing multiplyBy, value: 71 stack size after first push: 30
pushing calculateFactorial, value: 70 stack size after second push: 31
stack size after pop: 30
pushing multiplyBy, value: 70 stack size after first push: 31
pushing calculateFactorial, value: 69 stack size after second push: 32
stack size after pop: 31
pushing multiplyBy, value: 69 stack size after first push: 32
pushing calculateFactorial, value: 68 stack size after second push: 33
stack size after pop: 32
pushing multiplyBy, value: 68 stack size after first push: 33
pushing calculateFactorial, value: 67 stack size after second push: 34
stack size after pop: 33
pushing multiplyBy, value: 67 stack size after first push: 34
pushing calculateFactorial, value: 66 stack size after second push: 35
stack size after pop: 34
pushing multiplyBy, value: 66 stack size after first push: 35
pushing calculateFactorial, value: 65 stack size after second push: 36
stack size after pop: 35
pushing multiplyBy, value: 65 stack size after first push: 36
pushing calculateFactorial, value: 64 stack size after second push: 37
stack size after pop: 36
pushing multiplyBy, value: 64 stack size after first push: 37
pushing calculateFactorial, value: 63 stack size after second push: 38
stack size after pop: 37
pushing multiplyBy, value: 63 stack size after first push: 38
pushing calculateFactorial, value: 62 stack size after second push: 39
stack size after pop: 38
pushing multiplyBy, value: 62 stack size after first push: 39
pushing calculateFactorial, value: 61 stack size after second push: 40
stack size after pop: 39
pushing multiplyBy, value: 61 stack size after first push: 40
pushing calculateFactorial, value: 60 stack size after second push: 41
stack size after pop: 40
pushing multiplyBy, value: 60 stack size after first push: 41
pushing calculateFactorial, value: 59 stack size after second push: 42
stack size after pop: 41
pushing multiplyBy, value: 59 stack size after first push: 42
pushing calculateFactorial, value: 58 stack size after second push: 43
stack size after pop: 42
pushing multiplyBy, value: 58 stack size after first push: 43
pushing calculateFactorial, value: 57 stack size after second push: 44
stack size after pop: 43
pushing multiplyBy, value: 57 stack size after first push: 44
pushing calculateFactorial, value: 56 stack size after second push: 45
stack size after pop: 44
pushing multiplyBy, value: 56 stack size after first push: 45
pushing calculateFactorial, value: 55 stack size after second push: 46
stack size after pop: 45
pushing multiplyBy, value: 55 stack size after first push: 46
pushing calculateFactorial, value: 54 stack size after second push: 47
stack size after pop: 46
pushing multiplyBy, value: 54 stack size after first push: 47
pushing calculateFactorial, value: 53 stack size after second push: 48
stack size after pop: 47
pushing multiplyBy, value: 53 stack size after first push: 48
pushing calculateFactorial, value: 52 stack size after second push: 49
stack size after pop: 48
pushing multiplyBy, value: 52 stack size after first push: 49
pushing calculateFactorial, value: 51 stack size after second push: 50
stack size after pop: 49
pushing multiplyBy, value: 51 stack size after first push: 50
pushing calculateFactorial, value: 50 stack size after second push: 51
stack size after pop: 50
pushing multiplyBy, value: 50 stack size after first push: 51
pushing calculateFactorial, value: 49 stack size after second push: 52
stack size after pop: 51
pushing multiplyBy, value: 49 stack size after first push: 52
pushing calculateFactorial, value: 48 stack size after second push: 53
stack size after pop: 52
pushing multiplyBy, value: 48 stack size after first push: 53
pushing calculateFactorial, value: 47 stack size after second push: 54
stack size after pop: 53
pushing multiplyBy, value: 47 stack size after first push: 54
pushing calculateFactorial, value: 46 stack size after second push: 55
stack size after pop: 54
pushing multiplyBy, value: 46 stack size after first push: 55
pushing calculateFactorial, value: 45 stack size after second push: 56
stack size after pop: 55
pushing multiplyBy, value: 45 stack size after first push: 56
pushing calculateFactorial, value: 44 stack size after second push: 57
stack size after pop: 56
pushing multiplyBy, value: 44 stack size after first push: 57
pushing calculateFactorial, value: 43 stack size after second push: 58
stack size after pop: 57
pushing multiplyBy, value: 43 stack size after first push: 58
pushing calculateFactorial, value: 42 stack size after second push: 59
stack size after pop: 58
pushing multiplyBy, value: 42 stack size after first push: 59
pushing calculateFactorial, value: 41 stack size after second push: 60
stack size after pop: 59
pushing multiplyBy, value: 41 stack size after first push: 60
pushing calculateFactorial, value: 40 stack size after second push: 61
stack size after pop: 60
pushing multiplyBy, value: 40 stack size after first push: 61
pushing calculateFactorial, value: 39 stack size after second push: 62
stack size after pop: 61
pushing multiplyBy, value: 39 stack size after first push: 62
pushing calculateFactorial, value: 38 stack size after second push: 63
stack size after pop: 62
pushing multiplyBy, value: 38 stack size after first push: 63
pushing calculateFactorial, value: 37 stack size after second push: 64
stack size after pop: 63
pushing multiplyBy, value: 37 stack size after first push: 64
pushing calculateFactorial, value: 36 stack size after second push: 65
stack size after pop: 64
pushing multiplyBy, value: 36 stack size after first push: 65
pushing calculateFactorial, value: 35 stack size after second push: 66
stack size after pop: 65
pushing multiplyBy, value: 35 stack size after first push: 66
pushing calculateFactorial, value: 34 stack size after second push: 67
stack size after pop: 66
pushing multiplyBy, value: 34 stack size after first push: 67
pushing calculateFactorial, value: 33 stack size after second push: 68
stack size after pop: 67
pushing multiplyBy, value: 33 stack size after first push: 68
pushing calculateFactorial, value: 32 stack size after second push: 69
stack size after pop: 68
pushing multiplyBy, value: 32 stack size after first push: 69
pushing calculateFactorial, value: 31 stack size after second push: 70
stack size after pop: 69
pushing multiplyBy, value: 31 stack size after first push: 70
pushing calculateFactorial, value: 30 stack size after second push: 71
stack size after pop: 70
pushing multiplyBy, value: 30 stack size after first push: 71
pushing calculateFactorial, value: 29 stack size after second push: 72
stack size after pop: 71
pushing multiplyBy, value: 29 stack size after first push: 72
pushing calculateFactorial, value: 28 stack size after second push: 73
stack size after pop: 72
pushing multiplyBy, value: 28 stack size after first push: 73
pushing calculateFactorial, value: 27 stack size after second push: 74
stack size after pop: 73
pushing multiplyBy, value: 27 stack size after first push: 74
pushing calculateFactorial, value: 26 stack size after second push: 75
stack size after pop: 74
pushing multiplyBy, value: 26 stack size after first push: 75
pushing calculateFactorial, value: 25 stack size after second push: 76
stack size after pop: 75
pushing multiplyBy, value: 25 stack size after first push: 76
pushing calculateFactorial, value: 24 stack size after second push: 77
stack size after pop: 76
pushing multiplyBy, value: 24 stack size after first push: 77
pushing calculateFactorial, value: 23 stack size after second push: 78
stack size after pop: 77
pushing multiplyBy, value: 23 stack size after first push: 78
pushing calculateFactorial, value: 22 stack size after second push: 79
stack size after pop: 78
pushing multiplyBy, value: 22 stack size after first push: 79
pushing calculateFactorial, value: 21 stack size after second push: 80
stack size after pop: 79
pushing multiplyBy, value: 21 stack size after first push: 80
pushing calculateFactorial, value: 20 stack size after second push: 81
stack size after pop: 80
pushing multiplyBy, value: 20 stack size after first push: 81
pushing calculateFactorial, value: 19 stack size after second push: 82
stack size after pop: 81
pushing multiplyBy, value: 19 stack size after first push: 82
pushing calculateFactorial, value: 18 stack size after second push: 83
stack size after pop: 82
pushing multiplyBy, value: 18 stack size after first push: 83
pushing calculateFactorial, value: 17 stack size after second push: 84
stack size after pop: 83
pushing multiplyBy, value: 17 stack size after first push: 84
pushing calculateFactorial, value: 16 stack size after second push: 85
stack size after pop: 84
pushing multiplyBy, value: 16 stack size after first push: 85
pushing calculateFactorial, value: 15 stack size after second push: 86
stack size after pop: 85
pushing multiplyBy, value: 15 stack size after first push: 86
pushing calculateFactorial, value: 14 stack size after second push: 87
stack size after pop: 86
pushing multiplyBy, value: 14 stack size after first push: 87
pushing calculateFactorial, value: 13 stack size after second push: 88
stack size after pop: 87
pushing multiplyBy, value: 13 stack size after first push: 88
pushing calculateFactorial, value: 12 stack size after second push: 89
stack size after pop: 88
pushing multiplyBy, value: 12 stack size after first push: 89
pushing calculateFactorial, value: 11 stack size after second push: 90
stack size after pop: 89
pushing multiplyBy, value: 11 stack size after first push: 90
pushing calculateFactorial, value: 10 stack size after second push: 91
stack size after pop: 90
pushing multiplyBy, value: 10 stack size after first push: 91
pushing calculateFactorial, value: 9 stack size after second push: 92
stack size after pop: 91
pushing multiplyBy, value: 9 stack size after first push: 92
pushing calculateFactorial, value: 8 stack size after second push: 93
stack size after pop: 92
pushing multiplyBy, value: 8 stack size after first push: 93
pushing calculateFactorial, value: 7 stack size after second push: 94
stack size after pop: 93
pushing multiplyBy, value: 7 stack size after first push: 94
pushing calculateFactorial, value: 6 stack size after second push: 95
stack size after pop: 94
pushing multiplyBy, value: 6 stack size after first push: 95
pushing calculateFactorial, value: 5 stack size after second push: 96
stack size after pop: 95
pushing multiplyBy, value: 5 stack size after first push: 96
pushing calculateFactorial, value: 4 stack size after second push: 97
stack size after pop: 96
pushing multiplyBy, value: 4 stack size after first push: 97
pushing calculateFactorial, value: 3 stack size after second push: 98
stack size after pop: 97
pushing multiplyBy, value: 3 stack size after first push: 98
pushing calculateFactorial, value: 2 stack size after second push: 99
stack size after pop: 98
pushing multiplyBy, value: 2 stack size after first push: 99
pushing calculateFactorial, value: 1 stack size after second push: 100
stack size after pop: 99
stack size after pop: 98
stack size after pop: 97
stack size after pop: 96
stack size after pop: 95
stack size after pop: 94
stack size after pop: 93
stack size after pop: 92
stack size after pop: 91
stack size after pop: 90
stack size after pop: 89
stack size after pop: 88
stack size after pop: 87
stack size after pop: 86
stack size after pop: 85
stack size after pop: 84
stack size after pop: 83
stack size after pop: 82
stack size after pop: 81
stack size after pop: 80
stack size after pop: 79
stack size after pop: 78
stack size after pop: 77
stack size after pop: 76
stack size after pop: 75
stack size after pop: 74
stack size after pop: 73
stack size after pop: 72
stack size after pop: 71
stack size after pop: 70
stack size after pop: 69
stack size after pop: 68
stack size after pop: 67
stack size after pop: 66
stack size after pop: 65
stack size after pop: 64
stack size after pop: 63
stack size after pop: 62
stack size after pop: 61
stack size after pop: 60
stack size after pop: 59
stack size after pop: 58
stack size after pop: 57
stack size after pop: 56
stack size after pop: 55
stack size after pop: 54
stack size after pop: 53
stack size after pop: 52
stack size after pop: 51
stack size after pop: 50
stack size after pop: 49
stack size after pop: 48
stack size after pop: 47
stack size after pop: 46
stack size after pop: 45
stack size after pop: 44
stack size after pop: 43
stack size after pop: 42
stack size after pop: 41
stack size after pop: 40
stack size after pop: 39
stack size after pop: 38
stack size after pop: 37
stack size after pop: 36
stack size after pop: 35
stack size after pop: 34
stack size after pop: 33
stack size after pop: 32
stack size after pop: 31
stack size after pop: 30
stack size after pop: 29
stack size after pop: 28
stack size after pop: 27
stack size after pop: 26
stack size after pop: 25
stack size after pop: 24
stack size after pop: 23
stack size after pop: 22
stack size after pop: 21
stack size after pop: 20
stack size after pop: 19
stack size after pop: 18
stack size after pop: 17
stack size after pop: 16
stack size after pop: 15
stack size after pop: 14
stack size after pop: 13
stack size after pop: 12
stack size after pop: 11
stack size after pop: 10
stack size after pop: 9
stack size after pop: 8
stack size after pop: 7
stack size after pop: 6
stack size after pop: 5
stack size after pop: 4
stack size after pop: 3
stack size after pop: 2
stack size after pop: 1
stack size after pop: 0
9.33262154439441e+157



Видим, что максимальный размер стэка тоже составил 100 элементов (сколько и дали на вход функции). Если бы мы вычисляли этот факториал «наивной» рекурсивной функцией, то там получились бы ровно те же 100 кадров стэка в максимуме.

В чём тогда профит? Ваш todoStack во-первых, расположен не на стэке потока, а в heap, где места сильно больше (и при переполнении ему грозит не Stack overflow error, а Out of memory error), во-вторых, размером кадра (одной записи todoStack-а) вы управляете сами, и он может быть сильно компактнее чем то, что выделяет ОС или VM.

Спасибо большое за проявленное внимания!


В первом примере у вас ручная реализация абстракции call stack

Вы заметили основную суть. Именно ручную реализацию кол стека я и написал.


В чём тогда профит?

Профит в том. что такая функция не упадёт так рано, как рекурсивная реализация. Я об этом написал в фразе "Зависит от размера задачи". Когда нужно посчитать факториал для чисел меньше 1K-10K нужно юзать рекурсию. И это будет более ефективно. Но когда размер задачи достаточно велик — рекурсивная версия может просто слишком рано упасть. В то время как размер кучи обычно гораздо выше, а значит памяти хватит на большее.


при переполнении ему грозит не Stack overflow error, а Out of memory error

Итеративную версию можно уронить, вопрос только при каких размерах входных данных.


Спасибо за комментарий и проделанный анализ, надеюсь читатель моей статьи ознакомится и с вашим комментарием, чтобы не возникало ощущение, что это серебрянная пуля и не уронимая скала.

Не первый раз замечаю, что стало модно использовать «абстрактных лирических героев», типа Максима. Это новая модная калька с англоязычных статей?

Здравствуйте, это осознанный выбор.


Эта история с ошибкой в рекурсии произошла не просто в вакууме. Значит эта ошибка была допущена некоторым агентом.


Есть три варианта кто им может быть: писатель, читатель или третье лицо («Максим»).


Если это будет писатель, то текст будет выглядеть так:


"Я написал что то и оно сломалось"


Читатель, который сталкивался с такой проблемой сразу начнет воспринимать писателя как не опытного, даже не осознанно. И это плохо для писателя, ведь он хочет поделиться опытом, который у него есть.


Предположим что этот агент — читатель. Тогда текст будет выглядеть так:


"Вот вы написали вот это, и оно сломалось"


Читатель воспримет это негативно, ведь ему вменили «преступление». И это плохо для читателя, которому станет тяжелее воспринимать описанный опыт. Это плохо и для писателя, ведь он хочет поделиться опытом, а не чувством вины или ненависти и ТД.


Таким образом, если действие имеет плохую окраску лучше использовать третье лицо. Это не будет окрашивать читателя или писателя в темные тона.


Про этот литературный прием я прочитал в книге «Пиши и сокращай» Ильяхова.


Спасибо за комментарий!

ну познакомьте тогда нас с этим Максимом, кто он, сколько ему лет и чем он увлекается. потому что у меня возникло чувство, что этот Максим чем-то известен, но я его почему-то не знаю.
на мой взгляд, не надо так много заботиться о нежной психике читателя, ему интересна суть, а не формулировки
возникло чувство, что этот Максим чем-то известен, но я его почему-то не знаю

Да, я об этом думал, но предпочёл использовать этот приём. Он принёс больше пользы, чем вреда в статью, по причинам описанным выше.


на мой взгляд, не надо так много заботиться о нежной психике читателя

Я не считаю читателя «нежным».


не надо так много заботиться о нежной психике читателя, ему интересна суть

Это ложное противопоставление. Использование этого приёма не ухудшает восприятие сути. И у меня есть основания полагать, что улучшает.

ну вот видите, у нас с вами дискуссия о Максиме, а о сути — ни слова

Ваш первый комментарий касался формы, а не содержания.


Спасибо, за критику формы подачи. Я подумаю, как это можно улучшить.


Надеюсь, что этот приём не ухудшил ваше восприятие сути. Будет интересно узнать ваше мнение и по содержанию.

да, но за Максима обидно
Only those users with full accounts are able to leave comments. Log in, please.