Тут вышла статья на хабре [1], где написано:
"Хвостовая рекурсия это частный случай рекурсии, когда рекурсивный вызов может быть заменен итерацией."
Я почему-то всегда считал, что хвостовая рекурсия сложнее. Применительно к F# можно взять такой контр-пример.
Возьмем реализацию оператора while для F# Async. В исходниках F# это будет функция whileA. Если считать, что bindA - это монадическая связка для Async, то видим, что:
1) функция whileA вызывает bindA и передает последней вызов на саму себя, т.е. whileA определяется рекурсивно;
2) функции whileA и bindA используют хвостовые вызовы.
Отсюда можно заключить, что имеем случай хвостовой рекурсии (я прав в терминах?). При этом очевидно, что ни о какой замене whileA итерацией не может быть и речи, как минимум, в терминах .NET. Нужна соответствующая поддержка со стороны виртуальной машины.
В данном случае все хвостовые вызовы внутри whileA и bindA будут помечены в IL специальным тегом, который опознается виртуальной машиной .NET. Это ощутимо замедляет выполнение кода, но стек вызовов не увеличивается, что и требуется.
Так вот, имеем случай хвостовой рекурсии, несводимой к простой итерации в рамках .NET. Может быть, виртуальная машина и использует итерации, но это уже совсем другой внешний уровень.
[1] http://habrahabr.ru/post/143690/