iPhone-дружественная альтернатива рекурсии по огромным древовидным структурам?

Question

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

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

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

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

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

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

Answer 2

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