В чем принципиальная разница между вложенными циклами и рекурсией?

Question

[123qwe]

What's up, программач.
Рекурсия пришла после циклов, или циклы на замену рекурсии?
В некоторых функциональных языках циклы отсутствуют как таковые вообще, а повторение реализуется рекурсией.
Так вот, в чем разница и что в каких случаях предпочтительнее?
Слышал, что на собеседовании такие вопросы иногда проскальзывают.

Comments

[Oxoron]

Вложенные циклы ограниченно вкладываются. Два уровня вложения, три, четыре, число конечно и известно во время компиляции. Рекурсия раскручивается в теории бесконечно: её ограничивает лишь доступная память.

Answer 1

[Дмитрий Ковальский]

Для сферической задачи в вакууме и идеальной платформы - разницы никакой. Все задачи, которые можно решить иттеративно(циклом) можно реализовать рекурсивно. На практике все немного иначе. Как правило все уткнется в то как реализуюется рекурсия на конкретной платформе. К примеру если на каждом вызове в стек кладется указатель на функцию, которую надо вызывать рекурсивно - то есть риск что стек переполнится и вызовет исключение ДО того как рекурсия начнет раскручиваться. Для программиста важнее знать когда алгоритм рекурсивно выглядит красивее и прозрачнее чем итеративно. К примеру вычисление факториала по определению рекурсивно. Решать итеративно можно, но алгоритм не будет впрямую ложится на определение факториала.

Answer 2

[Alejandro Esquire]

Сначала изобрели циклы. Затем рекурсию.

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

Answer 3

[Curly Brace]

рекурсия - вызов функции из самой этой функции, со всеми вытекающими в виде забивания стека

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

Answer 4

[sivabur]

Память при рекурсии она постоянно увеличивается!