Каковы преимущества рекурсии?
Некоторые языки программирования могут оптимизировать хвостовую рекурсию, но, в общих чертах, рекурсия потребляет больше ресурсов, чем обычные циклы.
Возможно ли иметь итеративную версию некоторой рекурсивной функции?
recursion
advantages
OscarRyz
источник
источник
Ответы:
Да, вы можете кодировать рекурсивные функции как итерации. По сути, это требует от вас вести информацию вручную, которая в противном случае была бы учтена кодом вызова метода, сгенерированным компилятором.
Другими словами, вам нужен стек, где каждая запись является структурой, содержащей переданные параметры и все локальные переменные. Вы всегда работаете с самой верхней записью в стеке. Если вам нужно позвонить себе, создайте новую запись и поместите ее поверх стека. Когда закончите, возьмите самую верхнюю запись в стеке, открывая следующую, и используйте ранее самую верхнюю запись, чтобы извлечь возвращаемые значения и соответственно обновить новую самую верхнюю запись.
Я предлагаю вам изучить книгу компиляторов, чтобы увидеть, как это обычно реализуется в машинном коде.
источник
Рекурсия часто является более естественным взглядом на вещи, чем итерация. Например, рассмотрим обход по порядку двоичного дерева:
inorder(left); process(); inorder(right);
это намного проще, чем явное ведение стека.До тех пор, пока вы не зайдете слишком глубоко (взорвав стек), разница в использовании ресурсов обычно тривиальна. Не беспокойся об этом вообще. Простой код обычно лучше, чем оптимизированный вручную, хотя бывают и исключения. Право обычно лучше, чем быстро.
Любой рекурсивный алгоритм может быть выражен как итеративный алгоритм, но вам может потребоваться сохранить явный стек (соответствующий стеку вызовов, который обрабатывается неявно). В конце концов, если вы скомпилируете рекурсивную функцию, вы получите что-то, что зависит от манипулирования стеком и циклического перемещения по функции, и это итеративно.
Хвостово-рекурсивные функции могут быть легко преобразованы в циклы и не нуждаются в стеке, но это особый случай.
источник
Попробуйте решить проблему башен Ханоя итеративно. Как только вы сдадитесь, посмотрите на итеративное решение и сравните его с рекурсивным. Какой из них проще?
Да в принципе. Однако для многих задач, включая очень распространенные задачи, такие как обход дерева, рекурсивные решения намного проще и элегантнее, чем итеративные.
источник
Простота. Без оптимизации хвостового вызова это, конечно, требует больше ресурсов (стека), но как бы вы реализовали, скажем,
deltree
в Java без рекурсии? Суть в том, чтоdelete()
можно удалять каталоги, только если они пусты; вот это с рекурсией:источник
Я считаю, что рекурсия - это один из тех инструментов, которым должен жить программист. С помощью рекурсии вы можете «думать» о своих алгоритмах и решать их так, как вы об этом думаете. Но я должен предупредить вас, что все говорят о том, насколько хороша рекурсия и насколько прост в коде, в связи с этим я хочу сказать несколько вещей:
Имея это в виду, учитесь рекурсии! это смешно, сложно, и это разобьет ваш мозг! Но вам понравится.
Удачи!
источник