Итерация vs. Рекурсия

Забавы ради и упражнения для, решил попробовать итеративный поиск вместо рекурсивного. Для чистоты эксперимента переписал не основную функцию, а perft-тест: там кроме генерации ходов, проверки на легальность и собственно рекурсивных вызовов ничего нет. Поэтому выигрыш от замены рекурсии на итерации в реальном поиске будет заведомо ниже, чем в perft().

Результаты таковы:

Code:

из начальной позиции

depth     time-iter    time-recur
4         0.047        0.047
5         1.093        1.093
6         26.859       27.3

из другой позиции

depth     time-iter    time-recur
4         1.046        1.047
5         47.73        48.0

Предварительные выводы:

1. выигрыш по скорости составляет в моей программе в лучшем случае единицы процентов
2. затраты на рекурсивный вызов функций не являются узким местом в поиске
3. если учесть усложнение кода и процесса отладки, переход с рекурсии на итерации не является для меня целесообразным

Дополнительный фактор, который может повлиять на результаты в поиске по сравнению с perft() - количество аргументов, передаваемых при вызове функции. В perft() аргументов три, в реальном поиске их у меня - 5 или 6.
Врочем, предполагаю, что решающего значения это не имеет.

 

А ведь есть какие-то реальные итеративные программы, и довольно сильные. Названий не помню, но читал про какую-то.

 

Вспомнил. Итерация вместо рекурсии требуется при реализации поиска на SMP-системах. Так что буду иметь её в виду при переписывании Греки...