Как определить,в каких случаях эффективнее использовать рекурсию,а когда цикл?

#рекурсия #циклы #псевдокод

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

Ответы

Ответ 1

По-своему опыту могу порекомендовать следующее:

Ответьте себе на вопрос: знаете ли вы уровень вложенности? 

Если да, и уровень вложенности небольшой (например 3 цикла) - то смысла заморачиваться
с рекурсией нет.

Если нет, и уровень вложенности может быть динамическим, то ответ очевиден - без
рекурсии не обойтись

В любом случае,

Начинайте писать код без рекурсии, просто используйте вложенные циклы. Не обязательно
с полной вложенностью, достаточно 2-3 вложенных цикла, отшлифуйте их, чтобы они работали
корректно. Как только Вы это сделаете, переделать их в рекурсию или продолжить работать
во вложенных циклах не вызовет никаких проблем в обоих случаях. 

Начиная писать нерекурсивно, Вы с самого начала лучше разберетесь, как работает код,
а впоследствие и сама рекурсия.


Ответ 2

Любая рекурсия может быть сведена к циклу, по сути это следует из тезиса Черча-Тьюринга


  любая функция, которая может быть вычислена физическим устройством, может быть
вычислена машиной Тьюринга; 


Принципиальное отличие рекурсии от цикла состоит в наличии стека вызова - все локальные
переменные и аргументы складываются в стек при каждом вызове рекурсивной функции, а
в цикле локальные переменные остаются "на месте".

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

Слабость рекурсии там же: за это надо платить - проталкивание локальных переменных
и аргументов в стек чего то да стоит и размер стека тоже не бесконечен.

Есть еще одно преимущество рекурсии: красота и простота

Теперь когда и что использовать:

Набор некоторых правил, которые могут и будут противоречить друг-другу:


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


Как оценить хватит ли стека?

Допустим, если речь идет о Java, то в стандартной 32-х разрядной JVM размер стека
выделяемой на приложение по умолчанию равен 64k, если глубина рекурсии 100, то получается,
что на одну рекурсию максимум 650 байт или ~160 локальных переменных и аргументов типа
int или ~10 типа double