Можно ли считать функцию F # хвостовой рекурсивной, она использует код операции TailCall .net

Question

Поскольку .net имеет код операции TailCall , это можно использовать для определения, если функция F # действительно хвостовая рекурсивная?

Если это правда, кто-нибудь сделал надстройку VS, которая идентифицирует функции хвоста и не хвоста?

Answer 1

См. в этом блоге в блоге команды F #, чтобы узнать, как F # компилирует хвостовые вызовы.

Короче говоря,

1. Прямые рекурсивные хвостовые вызовы обычно преобразуются в циклы.
2. Взаимная рекурсия и косвенные нерекурсивные оконечные вызовы обычно превращаются в оконечные вызовы .NET.

но смотрите полный пост для всех кровавых подробностей.

Answer 2

Да, если компилятор отправляет инструкцию вызова tail, этот вызов будет хвостовым рекурсивным (по состоянию на CLR 4, но есть некоторые исключения, где он на самом деле не будет хвостовым рекурсивным). Но это не обязательно означает, что вся функция является хвостовой рекурсивной. Например, я могу представить, что функция QuickSort скомпилирована так, что первый рекурсивный вызов не является хвостовым рекурсивным, а второй -

.

Кроме того, просто потому, что некоторая функция не содержит инструкцию tail, это не обязательно означает, что она не является хвостовой рекурсией. JIT-компилятор может распознавать хвостовой вызов даже без инструкции tail и оптимизировать его как таковой.

Более того, компилятор F # иногда компилирует рекурсивные функции нерекурсивным способом. Это несколько отличается от обычной оптимизации хвостового вызова, и инструкция tail не используется, но общий эффект аналогичен.