Можно ли кодировать все рекурсивные функции с помощью итераций? [закрыто]

10

Каковы преимущества рекурсии?

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

Возможно ли иметь итеративную версию некоторой рекурсивной функции?

OscarRyz
источник

Ответы:

10

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

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

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


источник
Я понял Итак, какое преимущество будет иметь рекурсия? Простота?
OscarRyz
2
@OscarRyz: Да, и это более элегантно.
Майкл К
@OscarRyz, как я описал это рекурсия. Это просто не сделано с родными инструкциями CPU. Делая это вручную, вы можете выполнять такие вещи, как распараллеливание, которые плохо отображаются на нативные инструкции.
15

Рекурсия часто является более естественным взглядом на вещи, чем итерация. Например, рассмотрим обход по порядку двоичного дерева: inorder(left); process(); inorder(right);это намного проще, чем явное ведение стека.

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

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

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

Дэвид Торнли
источник
8
Я бы сказал, что право всегда лучше, чем быстро. Код, который делает неправильно очень быстро, никому не нужен.
Мейсон Уилер
1
Но что, если вы сможете сделать это неправильно очень быстро ?!
RationalGeek
1
@jkohlhepp - я могу решить любую проблему мгновенно. Ответ 0.
Примечание для себя - придумайте имя
2
Использование рекурсии, а не явного стека, может быть более эффективным, избегая необходимости выделения кучи, возможной фрагментации памяти и возможных проблем с локальностью. Однако, «справа обычно лучше, чем быстро», переполнение стека в случаях, когда ваше программное обеспечение должно обрабатывать, означает, что ваш код не работает. Обычно проблемные случаи довольно легко обнаружить - рекурсия в (разумно) сбалансированном дереве - это хорошо, но рекурсия в дереве, которое может быть очень несбалансированным, или в связанном списке, может быть серьезной ошибкой в ​​языке, подобном C. Хуже Он может выдержать простое тестирование и потерпеть крах, только если развернется по-настоящему.
Steve314
1
Я думаю, что вы все понимаете, что имел в виду Мейсон, и просто шутите ради удовольствия. Конечно, медленная правильная программа более полезна, чем быстрая неправильная программа.
Джорджио
4

Каковы преимущества рекурсии?

Попробуйте решить проблему башен Ханоя итеративно. Как только вы сдадитесь, посмотрите на итеративное решение и сравните его с рекурсивным. Какой из них проще?

Возможно ли иметь итеративную версию некоторой рекурсивной функции?

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

Дима
источник
3

Каковы преимущества рекурсии?

Простота. Без оптимизации хвостового вызова это, конечно, требует больше ресурсов (стека), но как бы вы реализовали, скажем, deltreeв Java без рекурсии? Суть в том, что delete()можно удалять каталоги, только если они пусты; вот это с рекурсией:

deltree(File fileOrDirectory) {
    if (fileOrDirectory.isDirectory()) {
        for (File subFileOrDirectory : fileOrDirectory.listFiles()) {
            deltree(subFileOrDirectory);
        }
    }
    fileOrDirectory.delete();
}
Joonas Pulakka
источник
1
Со стеком, как уже упоминалось в других ответах.
Николь
Да, но насколько это просто? -)
Joonas Pulakka
О, рекурсия определенно лучше. Я думал, ты говорил, что это невозможно.
Николь
0

Я считаю, что рекурсия - это один из тех инструментов, которым должен жить программист. С помощью рекурсии вы можете «думать» о своих алгоритмах и решать их так, как вы об этом думаете. Но я должен предупредить вас, что все говорят о том, насколько хороша рекурсия и насколько прост в коде, в связи с этим я хочу сказать несколько вещей:

  1. Прежде всего, подумать о «рекурсивном пути» алгоритма нелегко. Создание такой функции, как факториал (n!) Или что-то вроде Ханойских башен, является лишь верхушкой айсберга, а для достижения дна требуется много времени.
  2. Не думайте, что рекурсия вносит простоту только в ваш код, иногда итеративный путь уродлив и неопрятен, но экономичен (посмотрите на рекурсивное решение проблемы Фибоначчи)

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

Удачи!

Дэвид Конде
источник