Здравствуйте, mik1, Вы писали:

M> Всё бы хорошо с создаваемым кодом, но есть одна проблема — РЕКУРСИИ. Функциональные языки, как известно, построены, главным образом, на рекурсивных функциях. Но как быть с рекурсией, если при даже небольших глубинах рекурсии (~1000 уровней) получается переполнение стека?

Прочитайте про CPS-преобразование. Если компилируете, например, в Си, то промежуточный код с применением этого
преобразования всегда легко привести к последовательности функций с хвостовыми вызовами. Стек в таких случаях
надо иметь свой, а не использовать Сишный (так надо — GC можно более эффективный реализовать). Получается очень быстро, эффективно, и никакого растущего стека.

M>В интерпретаторах это лечится просто — вызвали первую функцию, интерпретируем ее код, встретили в нем вызов другой функции, выполнение первой функции приостановили, стали выполнять вторую функцию и т.д. Рекурсии как таковой нет.

???

И как ваш интерпретатор отличит хвостовой вызов от обычного? Так же точно, как и компилятор, смею вас уверить.
Так к чему тогда заморачиваться?