Рекурсии хвостовая и традиционная?

207

23 декабря 2017, 06:10

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

Answer 1

Я бы сказал, что хвостовая (оконечная) рекурсия - это просто частный случай рекурсии вообще, и уж говорить о том, что обычная рекурсия может зациклиться, а хвостовая - нет, или что стек переполняется в одном случае, и не переполняется в другом - ерунда.

Просто хвостовая рекурсия - когда единственный рекурсивный вызов находится в самом конце, перед выходом их функции, и такая рекурсия легко преобразуется в итерацию. Часто просто самим компилятором...