Циклы рекурсии или while

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

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

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

119 голосов | спросил Shivan Dragon 11 Jpm1000000pmFri, 11 Jan 2013 14:42:31 +040013 2013, 14:42:31

8 ответов


187

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

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

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

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

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

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

ответил tdammers 11 Jpm1000000pmFri, 11 Jan 2013 17:20:00 +040013 2013, 17:20:00
36

Это зависит.

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

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

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

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

ответил jk. 11 Jpm1000000pmFri, 11 Jan 2013 14:52:18 +040013 2013, 14:52:18
17

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

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

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

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

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

ответил dan_waterworth 11 Jpm1000000pmFri, 11 Jan 2013 15:06:29 +040013 2013, 15:06:29
6

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

  • Короткий, элегантный код в целом превосходит длинный, сложный код.
  • Однако последний момент несколько недействителен, если ваша база разработчиков не знакома с рекурсией и не желает /не может учиться. Он может даже стать небольшим отрицательным , а не положительным.
  • Рекурсия может быть плохой для эффективности , если вам понадобятся глубоко вложенные вызовы на практике и , вы не можете использовать хвостовую рекурсию (или ваша среда не может оптимизировать хвост рекурсия).
  • Рекурсия также плохо во многих случаях, если вы не можете должным образом кэшировать промежуточные результаты. Например, общий пример использования рекурсии дерева для вычисления чисел Фибоначчи выполняет horribly плохо, если вы не кешируете. Если вы делаете кеш, это просто, быстро, элегантно и в целом замечательно.
  • Рекурсия не применима к некоторым случаям, так же хороша, как итерация в других, и абсолютно необходима в других. Рецидивирование через длинные цепи бизнес-правил обычно не сопровождается рекурсией. Итерацию через потоки данных можно с пользой сделать с помощью рекурсии. Итерация над многомерными динамическими структурами данных (например, лабиринты, деревья объектов ...) практически невозможна без рекурсии, явной или неявной. Обратите внимание, что в этих случаях явная рекурсия much лучше, чем неявная - ничего более болезненного, чем чтение кода, где кто-то реализовал свой собственный ad-hoc, неполный, глючный стек внутри языка, чтобы избежать страшного R -слово.
ответил Kilian Foth 11 Jpm1000000pmFri, 11 Jan 2013 14:57:58 +040013 2013, 14:57:58
6

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

Если вы пишете 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>. Я делал это один раз, больше как упражнение, чем для практических целей. Я могу заверить вас, как только вы столкнетесь с такой задачей, у вас не будет сомнений, как те, которые вы выразили.

ответил SF. 11 Jpm1000000pmFri, 11 Jan 2013 15:18:03 +040013 2013, 15:18:03
1

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

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

ответил okobaka 11 Jpm1000000pmFri, 11 Jan 2013 21:20:18 +040013 2013, 21:20:18
1

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

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

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

ответил usernaveen 11 Jpm1000000pmFri, 11 Jan 2013 17:24:55 +040013 2013, 17:24:55
-1

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

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

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

ответил Pravin Sonawane 11 Jpm1000000pmFri, 11 Jan 2013 15:08:56 +040013 2013, 15:08:56

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132