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

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

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

Ответы

Ответ 1

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

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

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

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

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

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

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


Ответ 2

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


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


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

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

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

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

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

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


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


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

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

Как писать псевдокод?

#псевдокод

Что такое псевдокод?  

Для чего он применяется?
Как должен выглядеть и какими качествами должен обладать хороший псевдокод?  
    

Ответы

Ответ 1

Что такое псевдокод?


Псевдокод - это своеобразная смесь кода и естественного языка.  


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


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


  Для чего он применяется?


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


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


Хороший псевдокод должен:  


Быть похож на хороший код и на простой язык.
Игнорировать несущественные подробности
Если вы задумываетесь, где в вашем псевдокоде поставить запятую - вы что-то делаете
не так.  
Опускать очевидное
Ни к чему, например, указывать очевидные из контекста типы переменных  
Учитывать контекст
Выражение Отсортировать массив с помощью quicksort - имеет смысл только если не написано
в описании алгоритма quicksort.
Не быть слишком абстрактным
Через ваш псевдокод должно быть возможным увидеть описываемую модель, иначе алгоритм
невозможно анализировать, он слишком абстрактен.


А самое главное, следите за результатом, за тем как ваш псевдокод работает на практике.
Если вы обнаружили, что ваш коллега не в состоянии разобрать ваш псевдокод, либо
перевести его на ЯП - возможно стоит поработать над псевдокодом.  



Пример псевдокода:  

Пузырьковая сортировка:  
для j от 1 до n-1
  для i от 1 до n-j
    если aᵢ < aᵢ₊₁ поменять их местами


На мобильных устройствах код сверху может некорректно отображаться: там написано
a[i]

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

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

Ответ

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

Как писать псевдокод?

Что такое псевдокод?
Для чего он применяется? Как должен выглядеть и какими качествами должен обладать хороший псевдокод?

Ответ

Что такое псевдокод?
Псевдокод - это своеобразная смесь кода и естественного языка.
Псевдокод - компактный (зачастую неформальный) язык описания алгоритмов, использующий ключевые слова императивных языков программирования, но опускающий несущественные подробности и специфический синтаксис Википедия
Его должно быть легко понять, но в то же время написать хороший псевдокод может быть довольно сложной задачей.
Для чего он применяется?
Псевдокод - это попытка сохранить баланс между понятностью естественного языка и точностью кода.
Когда мы описываем алгоритм на естественном языке - высокоуровневость абстракций может излишне усложнить как анализ алгоритма, так и его реализацию на конкректном языке программирования. С другой стороны, когда же мы описываем алгоритм на ЯП, нам приходится тратить много времени на описание деталей алгоритма, который возможно не будет нами реализован(ведь обычно мы анализируем алгоритмы до того, как принимаем решение о том, какой будем реализовывать)
Хороший псевдокод должен:
Быть похож на хороший код и на простой язык Игнорировать несущественные подробности Если вы задумываетесь, где в вашем псевдокоде поставить запятую - вы что-то делаете не так. Опускать очевидное Ни к чему, например, указывать очевидные из контекста типы переменных Учитывать контекст Выражение Отсортировать массив с помощью quicksort - имеет смысл только если не написано в описании алгоритма quicksort. Не быть слишком абстрактным Через ваш псевдокод должно быть возможным увидеть описываемую модель, иначе алгоритм невозможно анализировать, он слишком абстрактен.
А самое главное, следите за результатом, за тем как ваш псевдокод работает на практике. Если вы обнаружили, что ваш коллега не в состоянии разобрать ваш псевдокод, либо перевести его на ЯП - возможно стоит поработать над псевдокодом.

Пример псевдокода:
Пузырьковая сортировка: для j от 1 до n-1 для i от 1 до n-j если aᵢ < aᵢ₊₁ поменять их местами
На мобильных устройствах код сверху может некорректно отображаться: там написано a[i]