Blog #recursion

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

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

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