whiteand Dec 14 2020 at 19:13

Превращаем рекурсию в цикл

6 min

26K

JavaScript*Algorithms*

Comments 41

fougasse Dec 14 2020 at 21:31

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

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

whiteand Dec 14 2020 at 21:44

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

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

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

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

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

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

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

pfodox Dec 16 2020 at 11:39

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

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

whiteand Dec 16 2020 at 11:47

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

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

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

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

Zenitchik Dec 14 2020 at 21:51

Дополню:

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

whiteand Dec 14 2020 at 21:56

Да!

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

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

UFO just landed and posted this here

red75prim Dec 15 2020 at 03:13

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

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

UFO just landed and posted this here

Zenitchik Dec 15 2020 at 07:09

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

UFO just landed and posted this here

whiteand Dec 14 2020 at 21:50

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

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

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

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

Zibx Dec 14 2020 at 23:16

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

-1

UFO just landed and posted this here

Zibx Dec 15 2020 at 09:52

Мои претензии конкретно к редьюксу. А концептуально структуры весьма красивы, хоть и заставляют GC постоянно приходить.

JSmitty Dec 21 2020 at 20:23

GC не бесплатен + рантайм затраты на выделение памяти + куча ФП обёрток как правило

UFO just landed and posted this here

whiteand Dec 15 2020 at 00:10

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

UFO just landed and posted this here

whiteand Dec 14 2020 at 22:22

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

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

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

UFO just landed and posted this here

uvelichitel Dec 14 2020 at 23:04

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

whiteand Dec 14 2020 at 23:09

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

uvelichitel Dec 14 2020 at 23:12

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

whiteand Dec 15 2020 at 00:03

Пример итерации по дереву на 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).

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

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

uvelichitel Dec 15 2020 at 00:10

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

whiteand Dec 15 2020 at 00:57

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

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
}

whiteand Dec 15 2020 at 00:59

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

klvov Dec 14 2020 at 23:59

В первом примере у вас ручная реализация абстракции 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.

whiteand Dec 15 2020 at 00:22

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

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

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

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

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

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

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

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

john_samilin Dec 15 2020 at 10:17

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

whiteand Dec 15 2020 at 11:02

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

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

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

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

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

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

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

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

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

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

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

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

john_samilin Dec 15 2020 at 11:07

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