Рекурсивный метод можно представить в виде цикла.

Допустим, у нас есть простой метод для перебора чего-либо:


class Node {
public int value;
public Node[] children;
}

Node FindRecursively(Node root, int value) {
if (root.value == value) return root;
for (int i = 0; i < root.children.Length; ++i) {
var node = FindRecursively(root.children[i], value);
if (node != null) return node;
}
return null;
}


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

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

Что же делать?
Давайте избавимся от рекурсивного вызова метода. Самый простой вариант это сделать - использовать Stack или Queue:


Node Find(Node root, int value) {
var queue = new Queue<Node>();
queue.Enqueue(root);
while (queue.Count > 0) {
var node = queue.Dequeue();
if (node.value == value) return node;
for (int i = 0; i < node.children.Length; ++i) {
queue.Enqueue(node.children[i]);
}
}
return null;
}


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

#recursion #code #algorithms