Помню дали задачку, вывести ряд Фибоначи. Нарисовал рекурсию. Не понравилось. Видать не поняли.

[mazzy]

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

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

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