Из твоего описания, вроде, всё понятно.
Вот есть рекурсивная процедура (мне лично ближе название функция). Она рекурсивная по определению – потому что прямо или опосредованно вызывает сама себя.
А вот процесс выполнения этой функции может пойти двумя разными путями, в зависимости от того, как написана функция, и поддерживает ли реализация языка оптимизацию хвостовой рекурсии(TСO, Tail call optimization).
Если ТСО нет, то процесс выполнения такой функции будет рекурсивным, то есть будут создаваться фреймы на стеке, и всё это может привести к stack overflow(нехватке стековой памяти при вызове функции).
В лиспе и его диалектах ТСО есть. Значит, если функция написана правильно(а это значит, что рекурсивный вызов является последним действием перед выходом из функции), то её можно оптимизировать в итерацию, и таким образом сэкономить на выделениях стека.
Следовательно, процесс выполнения такой функции будет итеративным. Хвостовая рекурсия может выполняться бесконечно долго без stack overflow.
Если же функция рекурсивная, но рекурсия не хвостовая, то и процесс её выполнения будет рекурсивным со всеми вытекающими.
