Циклы рекурсии или пока

123

Я читал о некоторых практиках интервью для разработчиков, в частности о технических вопросах и тестах, которые задавались на собеседованиях, и я несколько раз спотыкался о высказываниях жанра: «Хорошо, вы решили проблему с помощью цикла while, теперь вы можете сделать это с помощью рекурсия ", или" каждый может решить это с помощью цикла из 100 строк, но может ли он сделать это с помощью рекурсивной функции из 5 строк? " и т.п.

Мой вопрос, является ли рекурсия вообще лучше, чем если / while / for конструкции?

Я, честно говоря, всегда думал, что рекурсия не является предпочтительной, потому что она ограничена стековой памятью, которая намного меньше, чем куча, и выполнение большого количества вызовов функций / методов является неоптимальным с точки зрения производительности, но я могу быть неправым...

Дракон Шиван
источник
73
На предмет рекурсии это выглядит довольно интересно.
dan_waterworth
4
@dan_waterworth также, это помогло бы: google.fr/…, но я всегда, кажется, скучаю по нему: P
Shivan Dragon
@ShivanDragon Я так и думал ^ _ ^ Очень уместно, что я опубликовал это вчера :-)
Нил
2
Во встроенных средах, над которыми я работал в рекурсии, в лучшем случае не одобряется, а в худшем - публично порется. Фактически ограниченное пространство стека делает его незаконным.
Фред Томсен

Ответы:

192

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

Технически, итеративные циклы лучше подходят для типичных компьютерных систем на аппаратном уровне: на уровне машинного кода цикл - это просто тест и условный переход, тогда как рекурсия (реализованная наивно) включает в себя перемещение кадра стека, переход, возврат и возврат назад. из стека. OTOH, многие случаи рекурсии (особенно те, которые тривиально эквивалентны итеративным циклам) могут быть записаны так, чтобы можно было избежать push / pop стека; это возможно, когда рекурсивный вызов функции - это последнее, что происходит в теле функции перед возвратом, и это обычно называют оптимизацией хвостового вызова (или оптимизацией хвостовой рекурсии ). Правильно оптимизированная рекурсивная функция с хвостовым вызовом в основном эквивалентна итеративному циклу на уровне машинного кода.

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

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

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

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

tdammers
источник
3
Мне больше нравится ваш ответ, потому что он касается наиболее важных аспектов, которые может иметь ответ на этот вопрос, он объясняет основные технические части, а также дает хорошее представление о том, как эта проблема вписывается в сферу программирования.
Шиван Дракон
1
Я также заметил шаблон в программировании синхронизации, где избегаются циклы в пользу рекурсивных вызовов итератора, который содержит метод .next (). Я предполагаю, что он не дает слишком долго жадному коду долго работать.
Эван Плейс,
1
Итеративная версия также включает в себя отправку и вставку значений. Вы просто должны вручную написать код, чтобы сделать это. Рекурсивная версия помещает состояние в стек в итеративном алгоритме, который обычно приходится вручную моделировать, помещая состояние в некоторую структуру. Только самые тривиальные алгоритмы не нуждаются в этом состоянии, и в этих случаях компилятор обычно может определить хвостовую рекурсию и создать итеративное решение.
Мартин Йорк,
1
@tdammers Не могли бы вы рассказать мне, где я могу прочитать упомянутое вами исследование «Опыт и исследования показывают, что между людьми существует грань ...» Мне это кажется очень интересным.
Ю Мацуо
2
Одна вещь, которую вы забыли упомянуть, итеративный код имеет тенденцию работать лучше, когда вы имеете дело с одним потоком выполнения, но рекурсивные алгоритмы, как правило, пригодны для выполнения в нескольких потоках.
GordonM
37

По-разному.

  • Некоторые проблемы очень легко поддаются рекурсивным решениям, например, быстрая сортировка
  • Некоторые языки не поддерживают рекурсию, например, ранние фортраны
  • Некоторые языки предполагают рекурсию в качестве основного средства зацикливания, например Haskell

Стоит также отметить, что поддержка хвостовой рекурсии делает хвостовые рекурсивные и итеративные циклы эквивалентными, то есть рекурсия не всегда должна тратить стек.

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

Наконец, я хотел бы отметить, что решение из пяти строк, вероятно, всегда лучше, чем решение из 100 строк (при условии, что они на самом деле эквивалентны).

JK.
источник
5
Хороший ответ (+1). «Решение из 5 строк, вероятно, всегда лучше, чем решение из 100 строк»: я думаю, что краткость - не единственное преимущество рекурсии. Использование рекурсивного вызова вынуждает вас сделать функциональные зависимости между значениями в разных итерациях явными.
Джорджио
4
Более короткие решения имеют тенденцию быть лучше, но есть такая вещь, как чрезмерно краткая.
dan_waterworth
5
@dan_waterworth по сравнению с «100 линией» довольно сложно быть слишком кратким
комнат
4
@ Джорджио, Вы можете сделать программы меньше, удалив ненужный код или сделав явные вещи неявными. Пока вы придерживаетесь первого, вы улучшаете качество.
dan_waterworth
1
@jk, я думаю, что это еще одна форма неявной информации. Информация о том, для чего используется переменная, удаляется из ее имени, где она является явной, и помещается в ее использование, которое является неявным.
dan_waterworth
17

Не существует общепризнанного определения «лучше», когда речь идет о программировании, но я буду понимать, что оно означает «легче поддерживать / читать».

Рекурсия обладает большей выразительной силой, чем конструкции итеративных циклов: я говорю это потому, что цикл while эквивалентен хвостовой рекурсивной функции, и рекурсивные функции не обязательно должны быть хвостовой рекурсивной. Мощные конструкции, как правило, плохо, потому что они позволяют делать вещи, которые трудно читать. Однако рекурсия дает вам возможность писать циклы без использования изменчивости, и, на мой взгляд, изменчивость гораздо более эффективна, чем рекурсия.

Итак, от низкой выразительной мощности до высокой выразительной, циклические конструкции складываются следующим образом:

  • Хвост рекурсивные функции, которые используют неизменные данные,
  • Рекурсивные функции, которые используют неизменные данные,
  • В то время как циклы, которые используют изменяемые данные,
  • Хвост рекурсивных функций, которые используют изменяемые данные,
  • Рекурсивные функции, которые используют изменяемые данные,

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

dan_waterworth
источник
1
«цикл while эквивалентен хвостовой рекурсивной функции, и рекурсивные функции не обязательно должны быть хвостовой рекурсивной»: +1. Вы можете смоделировать рекурсию с помощью цикла while + стека.
Джорджио
1
Я не уверен, что согласен на 100%, но это, безусловно, интересная перспектива, так что +1 за это.
Конрад Рудольф
+1 за отличный ответ, а также за упоминание о том, что некоторые языки (или компиляторы) не выполняют оптимизацию хвостовых вызовов.
Шиван Дракон
@ Джорджио, «Вы можете смоделировать рекурсию с помощью цикла while + стек», поэтому я сказал выразительную силу. В вычислительном отношении они одинаково мощны.
dan_waterworth
@dan_waterworth: Точно, и, как вы сказали в своем ответе, рекурсия сама по себе более выразительна, чем цикл while, потому что вам нужно добавить стек в цикл while для симуляции рекурсии.
Джорджио
7

Рекурсия часто менее очевидна. Менее очевидным труднее поддерживать.

Если вы пишете for(i=0;i<ITER_LIMIT;i++){somefunction(i);}в основном потоке, вы четко даете понять, что пишете цикл. Если ты пишешь, somefunction(ITER_LIMIT);ты не понимаешь, что произойдет. Только просмотр содержимого: эти somefunction(int x)вызовы somefunction(x-1)говорят вам, что на самом деле это цикл с использованием итераций. Кроме того, вы не можете с легкостью поместить условие escape break;где-то на полпути итераций, вы должны либо добавить условие, которое будет передано полностью назад, либо вызвать исключение. (и исключения снова добавляют сложность ...)

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

Конечно, если это сэкономит вам 98 строк, это совсем другое дело.

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

По сути, если somefunction(x-1)нужно вызывать изнутри себя более одного раза на уровень, забудьте итерации.

... Написание итеративных функций для задач, которые лучше всего выполнять с помощью рекурсии, возможно, но не приятно. Где бы вы ни использовали int, вам нужно что-то вроде stack<int>. Я сделал это один раз, больше как упражнение, чем для практических целей. Я могу заверить вас, когда вы столкнетесь с такой задачей, у вас не будет сомнений, подобных тем, которые вы высказали.

Научная фантастика
источник
10
Что очевидно, а что менее очевидно, частично зависит от того, к чему вы привыкли. Итерация чаще использовалась в языках программирования, потому что она ближе к способу работы процессора (то есть она использует меньше памяти и работает быстрее). Но если вы привыкли мыслить индуктивно, рекурсия может быть столь же интуитивной.
Джорджио
5
«Если они видят ключевое слово цикла, они знают, что это цикл. Но ключевого слова recurse нет, они могут распознать его, только увидев f (x-1) внутри f (x).»: Когда вы вызываете рекурсивную функцию, вы делаете не хочу знать, что это рекурсивно. Точно так же, когда вы вызываете функцию, содержащую цикл, вы не хотите знать, что она содержит цикл.
Джорджио
3
@SF: Да, но вы можете увидеть это, только если посмотрите на тело функции. В случае цикла вы видите цикл, в случае рекурсии вы видите, что функция вызывает себя.
Джорджио
5
@SF: Для меня это похоже на круговые рассуждения: «Если в моей интуиции это цикл, то это цикл». mapможет быть определена как рекурсивная функция (см., например, haskell.org/tutorial/functions.html ), даже если интуитивно понятно, что она пересекает список и применяет функцию к каждому члену списка.
Джорджио
5
@SF, mapэто не ключевое слово, это обычная функция, но это не имеет значения. Когда функциональные программисты используют рекурсию, обычно это происходит не потому, что они хотят выполнить последовательность действий, а потому, что решаемая проблема может быть выражена в виде функции и списка аргументов. Затем проблема может быть сведена к другой функции и другому списку аргументов. В конце концов, у вас есть проблема, которая может быть решена тривиально.
dan_waterworth
6

Как обычно, это вообще не подлежит объяснению, потому что существуют дополнительные факторы, которые на практике широко неравны между случаями и не равны друг другу в рамках варианта использования. Вот некоторые из нагрузок.

  • Короткий, элегантный код в целом превосходит длинный, сложный код.
  • Однако последний пункт несколько недействителен, если ваша база разработчиков не знакома с рекурсией и не желает / не может учиться. Это может даже стать небольшим отрицательным, а не положительным.
  • Рекурсия может отрицательно сказаться на эффективности, если на практике вам потребуются глубоко вложенные вызовы, и вы не можете использовать хвостовую рекурсию (или ваша среда не может оптимизировать хвостовую рекурсию).
  • Рекурсия также плоха во многих случаях, если вы не можете правильно кэшировать промежуточные результаты. Например, общий пример использования рекурсии дерева для вычисления чисел Фибоначчи работает ужасно плохо, если вы не кешируете. Если вы делаете кеш, это просто, быстро, элегантно и в целом замечательно.
  • Рекурсия неприменима в некоторых случаях, так же хороша, как итерация в других, и абсолютно необходима в других. Пробираться по длинным цепочкам бизнес-правил обычно не помогает рекурсия. Итерация по потокам данных может быть полезна с помощью рекурсии. Итерирование по многомерным динамическим структурам данных (например, лабиринты, деревья объектов ...) практически невозможно без рекурсии, явной или неявной. Обратите внимание, что в этих случаях явная рекурсия намного лучше, чем неявная - нет ничего более болезненного, чем чтение кода, где кто-то реализовал свой собственный, неполный, неполный, глючный стек в языке, просто чтобы избежать страшного R-слова.
Килиан Фот
источник
Что вы подразумеваете под кэшированием по отношению к рекурсии?
Джорджио
@ Джорджио предположительно памятка
JK.
Фэ. Если ваша среда не оптимизирует хвостовые вызовы, вы должны найти лучшую среду, а если ваши разработчики не знакомы с рекурсией, вы должны найти лучших разработчиков. Есть некоторые стандарты, люди!
CA McCann
1

Рекурсия - это повторение вызова функции, цикл - это повторение перехода в память.

Следует также упомянуть о переполнении стека - http://en.wikipedia.org/wiki/Stack_overflow

okobaka
источник
1
Рекурсия означает функцию, определение которой влечет за собой сам вызов.
hardmath
1
Хотя ваше простое определение не совсем точно на 100%, вы единственный, кто упомянул переполнение стека.
Qix
1

Это действительно зависит от удобства или требования:

Если вы берете язык программирования Python , он поддерживает рекурсию, но по умолчанию существует ограничение на глубину рекурсии (1000). Если он превысит лимит, мы получим ошибку или исключение. Это ограничение можно изменить, но если мы сделаем это, у нас могут возникнуть ненормальные ситуации в языке.

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

usernaveen
источник
3
Вот блог Гвидо ван Россума о том, почему он не хочет оптимизации хвостовой рекурсии в Python (поддерживая идею, что разные языки используют разные тактические подходы).
hardthth
-1

Используйте шаблон дизайна стратегии.

  • Рекурсия чистая
  • Петли (возможно) эффективны

В зависимости от вашей нагрузки (и / или других условий) выберите один.

Правин Сонавейн
источник
5
Чего ждать? Как шаблон стратегии вписывается здесь? И второе предложение звучит как пустая фраза.
Конрад Рудольф
@KonradRudolph Я бы пошел на рекурсию. Для очень больших наборов данных я бы переключился на циклы. Это то, что я имел в виду. Я прошу прощения, если это не было ясно.
Правин Сонавэйн
3
Ах. Ну, я все еще не уверен, что это можно назвать «шаблоном разработки стратегии», который имеет очень фиксированное значение, и вы используете его метафорически. Но теперь, по крайней мере, я вижу, куда ты идешь.
Конрад Рудольф
@KonradRudolph выучил важный урок. Глубоко объясните, что вы хотите сказать .. Спасибо .., что помогло .. :)
Pravin Sonawane
2
@Pravin Sonawane: Если вы можете использовать оптимизацию хвостовой рекурсии, вы можете использовать рекурсию также для больших массивов данных.
Джорджио