Блог

У меня есть график объектов того же типа. Каждый объект связан с 0, 1 или многими другими. Мне нужно пройти по всем возможным путям на графике.

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

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

Как выглядят альтернативы?

Что-то вроде:

(давайте предположим, что TreeNode содержит свойство NSArray * children)

 -(void)iterateOverTree:(TreeNode *)node
{
    NSMutableArray * elements = [NSMutableArray array];
    [elements addObject:node];

    while([elements count])
    {
        TreeNode * current = [elements objectAtIndex:0];
        [self doStuffWithNode:current];
        for(TreeNode * child in current.children)
        {
            [elements addObject:child];
        }

        [elements removeObjectAtIndex:0];
    }
}
  

Осторожно, непроверенный код 🙂

Вы можете «имитировать» стек самостоятельно, сохраняя текущее состояние в NSArray. Это позволит использовать кучу вместо стековой памяти и, возможно, решить проблему переполнения стека.