Я читал о некоторых практиках интервью для разработчиков, в частности о технических вопросах и тестах, которые задавались на собеседованиях, и я несколько раз спотыкался о высказываниях жанра: «Хорошо, вы решили проблему с помощью цикла while, теперь вы можете сделать это с помощью рекурсия ", или" каждый может решить это с помощью цикла из 100 строк, но может ли он сделать это с помощью рекурсивной функции из 5 строк? " и т.п.
Мой вопрос, является ли рекурсия вообще лучше, чем если / while / for конструкции?
Я, честно говоря, всегда думал, что рекурсия не является предпочтительной, потому что она ограничена стековой памятью, которая намного меньше, чем куча, и выполнение большого количества вызовов функций / методов является неоптимальным с точки зрения производительности, но я могу быть неправым...
источник
Ответы:
Рекурсия по сути не лучше и не хуже циклов - у каждого есть свои преимущества и недостатки, и они даже зависят от языка программирования (и реализации).
Технически, итеративные циклы лучше подходят для типичных компьютерных систем на аппаратном уровне: на уровне машинного кода цикл - это просто тест и условный переход, тогда как рекурсия (реализованная наивно) включает в себя перемещение кадра стека, переход, возврат и возврат назад. из стека. OTOH, многие случаи рекурсии (особенно те, которые тривиально эквивалентны итеративным циклам) могут быть записаны так, чтобы можно было избежать push / pop стека; это возможно, когда рекурсивный вызов функции - это последнее, что происходит в теле функции перед возвратом, и это обычно называют оптимизацией хвостового вызова (или оптимизацией хвостовой рекурсии ). Правильно оптимизированная рекурсивная функция с хвостовым вызовом в основном эквивалентна итеративному циклу на уровне машинного кода.
Другое соображение заключается в том, что итеративные циклы требуют деструктивных обновлений состояния, что делает их несовместимыми с чистой (без побочных эффектов) семантикой языка. Это причина того, что чистые языки, такие как Haskell, вообще не имеют циклических конструкций, а во многих других языках функционального программирования их либо нет, либо они избегают их в максимально возможной степени.
Однако причина, по которой эти вопросы так часто встречаются в интервью, заключается в том, что для того, чтобы ответить на них, вам необходимо глубокое понимание многих жизненно важных концепций программирования - переменных, вызовов функций, области видимости и, конечно, циклов и рекурсии - и у вас есть привнести умственную гибкость в таблицу, которая позволяет подойти к проблеме с двух радикально разных точек зрения и перемещаться между различными проявлениями одной и той же концепции.
Опыт и исследования показывают, что существует грань между людьми, которые способны понимать переменные, указатели и рекурсии, и теми, кто этого не знает. Почти все остальное в программировании, включая фреймворки, API, языки программирования и их крайние примеры, может быть получено путем изучения и опыта, но если вы не в состоянии развить интуицию для этих трех основных концепций, вы не годитесь для программиста. Перевод простого итеративного цикла в рекурсивную версию - это самый быстрый способ отфильтровать непрограммистов - обычно даже неопытный программист может сделать это за 15 минут, и это очень не зависит от языка, поэтому кандидат может выбрать язык по своему выбору вместо того, чтобы спотыкаться об идиосинкразиях.
Если во время интервью вы получите такой вопрос, это хороший знак: это означает, что потенциальный работодатель ищет людей, которые могут программировать, а не людей, которые запомнили руководство по инструменту программирования.
источник
По-разному.
Стоит также отметить, что поддержка хвостовой рекурсии делает хвостовые рекурсивные и итеративные циклы эквивалентными, то есть рекурсия не всегда должна тратить стек.
Кроме того, рекурсивный алгоритм всегда может быть реализован итеративно с использованием явного стека .
Наконец, я хотел бы отметить, что решение из пяти строк, вероятно, всегда лучше, чем решение из 100 строк (при условии, что они на самом деле эквивалентны).
источник
Не существует общепризнанного определения «лучше», когда речь идет о программировании, но я буду понимать, что оно означает «легче поддерживать / читать».
Рекурсия обладает большей выразительной силой, чем конструкции итеративных циклов: я говорю это потому, что цикл while эквивалентен хвостовой рекурсивной функции, и рекурсивные функции не обязательно должны быть хвостовой рекурсивной. Мощные конструкции, как правило, плохо, потому что они позволяют делать вещи, которые трудно читать. Однако рекурсия дает вам возможность писать циклы без использования изменчивости, и, на мой взгляд, изменчивость гораздо более эффективна, чем рекурсия.
Итак, от низкой выразительной мощности до высокой выразительной, циклические конструкции складываются следующим образом:
В идеале вы должны использовать наименее выразительные конструкции, какие только можете. Конечно, если ваш язык не поддерживает оптимизацию хвостовых вызовов, то это также может повлиять на ваш выбор конструкции цикла.
источник
Рекурсия часто менее очевидна. Менее очевидным труднее поддерживать.
Если вы пишете
for(i=0;i<ITER_LIMIT;i++){somefunction(i);}в основном потоке, вы четко даете понять, что пишете цикл. Если ты пишешь,somefunction(ITER_LIMIT);ты не понимаешь, что произойдет. Только просмотр содержимого: этиsomefunction(int x)вызовыsomefunction(x-1)говорят вам, что на самом деле это цикл с использованием итераций. Кроме того, вы не можете с легкостью поместить условие escapebreak;где-то на полпути итераций, вы должны либо добавить условие, которое будет передано полностью назад, либо вызвать исключение. (и исключения снова добавляют сложность ...)По сути, если это очевидный выбор между итерацией и рекурсией, сделайте интуитивно понятное дело. Если итерация делает работу легко, сохранение двух строк редко стоит головной боли, которую она может создать в долгосрочной перспективе.
Конечно, если это сэкономит вам 98 строк, это совсем другое дело.
Существуют ситуации, для которых рекурсия просто идеально подходит, и они не являются чем-то необычным. Обход древовидных структур, многосвязных сетей, структур, которые могут содержать свой собственный тип, многомерных зубчатых массивов, по существу всего, что не является простым вектором или массивом фиксированных измерений. Если вы пересекаете известный прямой путь, повторите. Если вы погрузитесь в неизвестность, вернитесь.
По сути, если
somefunction(x-1)нужно вызывать изнутри себя более одного раза на уровень, забудьте итерации.... Написание итеративных функций для задач, которые лучше всего выполнять с помощью рекурсии, возможно, но не приятно. Где бы вы ни использовали
int, вам нужно что-то вродеstack<int>. Я сделал это один раз, больше как упражнение, чем для практических целей. Я могу заверить вас, когда вы столкнетесь с такой задачей, у вас не будет сомнений, подобных тем, которые вы высказали.источник
mapможет быть определена как рекурсивная функция (см., например, haskell.org/tutorial/functions.html ), даже если интуитивно понятно, что она пересекает список и применяет функцию к каждому члену списка.mapэто не ключевое слово, это обычная функция, но это не имеет значения. Когда функциональные программисты используют рекурсию, обычно это происходит не потому, что они хотят выполнить последовательность действий, а потому, что решаемая проблема может быть выражена в виде функции и списка аргументов. Затем проблема может быть сведена к другой функции и другому списку аргументов. В конце концов, у вас есть проблема, которая может быть решена тривиально.Как обычно, это вообще не подлежит объяснению, потому что существуют дополнительные факторы, которые на практике широко неравны между случаями и не равны друг другу в рамках варианта использования. Вот некоторые из нагрузок.
источник
Рекурсия - это повторение вызова функции, цикл - это повторение перехода в память.
Следует также упомянуть о переполнении стека - http://en.wikipedia.org/wiki/Stack_overflow
источник
Это действительно зависит от удобства или требования:
Если вы берете язык программирования Python , он поддерживает рекурсию, но по умолчанию существует ограничение на глубину рекурсии (1000). Если он превысит лимит, мы получим ошибку или исключение. Это ограничение можно изменить, но если мы сделаем это, у нас могут возникнуть ненормальные ситуации в языке.
В настоящее время (количество вызовов больше глубины рекурсии) нам нужно отдать предпочтение конструкциям цикла. Я имею в виду, что если размера стека недостаточно, мы должны предпочесть конструкции цикла.
источник
Используйте шаблон дизайна стратегии.
В зависимости от вашей нагрузки (и / или других условий) выберите один.
источник