Берегись рекурсии смолоду (Часть 1)

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

Давайте предположим, что мы должны написать программу для обхода файловой системы. Для упрощения не будем рассматривать случаи сканирования удаленных файловых систем, ftp сайтов и прочих «утяжеленных» случаев. Допустим, что нас интересует именно обход локальной файловой системы.

Для новичка самым простым способом является привлечь рекурсию:

typedef std::vector < Node* >::iterator NodeIterator;

TraverseDir(Dir* currDir) {
    Node* subNodes = GetChildren(currDir);
    for(NodeIterator i=subNodes->begin(); i != subNodes->end(); i++)
    {
        if(currDir->isDir())
        {
            TraverseDir(currDir);
        }
    }
}

Что происходит когда вызывается в очередной раз TraverseDir(currDir)? Если не вдаваться в детали, то расходуется стек. Расходуется на то, чтобы сохранить все переменные текущей области видимости, например. Т.е. в том случае если наша файловая система очень «глубока», то мы рискуем получить переполнение стека. Прикладной программист обычно не утруждает себя заботой о размере стека вызовов. Это именно та причина, по которой ему стоит избегать рекурсии.

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

Рекурсия противоестественна по своей природе императивному программированию. Предсказать сколько инструкций получится из того или иного рекурсивного выражения невозможно, а парадигма императивного программирования заставляет нас акцентироваться свое внимание именно на инструкциях, которые изменяют состояние программной системы. Кстати, если принять копию локальных переменных (в самом простом и грубом случае) за состояние, то и количество состояний, которое одновременно должна «содержать» получается равно грубине рекурсии. Главное, что я хочу сказать — рекурсия не для императивного программирования.

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

static int Fact(int n)
{
    if (n <= 1) return 1;
        return n * Fact(n - 1);
}

Коротко и емко, но плохо. Особенно если учесть, что у этой функции есть итеративный аналог:

static int Fact(int n)
{
    int sum = 1;
    if (n <= 1) return sum;
    while (n > 1)
    {
        sum *= n;
        n--;
    }

    return sum;
}

Немного непривычно, но я думаю, что вы поняли общий ход мысли. Нерекурсивная реализации рекурсивной функции обычно называется замкнутой формой в математике. В программировании я придерживаюсь термина «итеративная функция» в качестве антонима «рекурсивной функции». Итеративная реализация обычно использует меньшее количество «условных тактов» (базовых операций) при работе.

Если есть возможность не использовать рекурсию — не используйте ее. Это главная мысль, которую я пытаюсь до вас донести.  Случаев, когда рекурсия действительно необходима очень мало. Одним из примеров является функция Аккермана.

Как же все-таки уйти от рекурсии в нашем первом примере, т.е. при обходе файловой системы в частности и иерархической системы в общем? Об этом — во второй части этой статьи. В качестве бонуса предлагаю вам посмотреть на «финскую рекурсию» (с) RSDN.ru