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