Трансляция рекурсии в итерацию

stm8823636

Существует ли алгоритм перевода рекурсии любой сложности(прямая, косвенная, параллельная) в итерацию?

rosali

Если использовать динамическую память, то можно самому сделать стек. По другому нельзя. Рекурсия _принципиально_ выразительнее цикла, поскольку у цикла конечное число состояний (конечное число переменных * конечное число значений каждой).

vook

Только "хвостовую" (tail recursion).

stm8823636

Я так пологаю что не только ххвостовую, но и некоторое количество частных случаев рекурсии.

stm8823636

Я чем отличается рекурсия и цикл на уровне грамматик? Я чет так, с ходу, понять не могу.

a10063

у цикла конечное число состояний (конечное число переменных * конечное число значений каждой .

а это почему?
если же опираться на конечность значений каждой переменной в силу машинного представления, то рекурсия тоже имеет конечное кол-во состояний

p_serge

Только "хвостовую" (tail recursion).

а разве это доказано?

bleyman

> Только "хвостовую" (tail recursion).
Только фиг определишь, что данная конкретная рекурсия может быть переписана как хвостовая. Или нет?