Рекурсия или итерация?
Есть ли снижение производительности, если мы используем цикл вместо рекурсии или наоборот в алгоритмах, где оба могут служить одной и той же цели? Например: проверьте, является ли данная строка палиндромом. Я видел много программистов, использующих рекурсию как способ показать себя, когда простой итерационный алгоритм может соответствовать всем требованиям. Играет ли компилятор жизненно важную роль при принятии решения, что использовать?
31 ответ
Возможно, что рекурсия будет более дорогой, в зависимости от того, является ли рекурсивная функция хвостовой рекурсивной (последняя строка - рекурсивный вызов). Хвостовая рекурсия должна распознаваться компилятором и оптимизироваться для его итеративного аналога (при сохранении краткой и ясной реализации, которую вы имеете в своем коде).
Я бы написал алгоритм таким образом, чтобы он был наиболее понятным и наиболее понятным для бедного лоха (будь то вы или кто-то еще), который должен поддерживать код в течение нескольких месяцев или лет. Если вы столкнетесь с проблемами производительности, то профилируйте свой код, а затем и только потом посмотрите на оптимизацию, перейдя к итеративной реализации. Возможно, вы захотите изучить запоминание и динамическое программирование.
Циклы могут повысить производительность вашей программы. Рекурсия может повысить производительность вашего программиста. Выберите, что важнее в вашей ситуации!
Сравнение рекурсии с итерацией аналогично сравнению отвертки с крестообразной головкой с отверткой с плоской головкой. По большей части вы можете удалить любой винт с крестообразным шлицем с плоской головкой, но было бы проще, если бы вы использовали отвертку, предназначенную для этого винта, верно?
Некоторые алгоритмы просто поддаются рекурсии из-за того, как они спроектированы (последовательности Фибоначчи, обход древовидной структуры и т. Д.). Рекурсия делает алгоритм более лаконичным и простым для понимания (следовательно, разделяемым и многократно используемым).
Кроме того, некоторые рекурсивные алгоритмы используют "Ленивая оценка", что делает их более эффективными, чем их итеративные братья. Это означает, что они выполняют дорогостоящие вычисления только в то время, когда они необходимы, а не при каждом запуске цикла.
Этого должно быть достаточно, чтобы вы начали. Я выкопаю несколько статей и примеров для вас тоже.
Ссылка 1: Haskel против PHP (рекурсия против итерации)
Вот пример, где программист должен был обрабатывать большой набор данных с использованием PHP. Он показывает, как легко было бы работать в Haskel с помощью рекурсии, но, поскольку у PHP не было простого способа выполнить тот же метод, он был вынужден использовать итерацию, чтобы получить результат.
http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html
Ссылка 2: Освоение рекурсии
Большая часть плохой репутации рекурсии происходит из-за высокой стоимости и неэффективности в императивных языках. Автор этой статьи рассказывает о том, как оптимизировать рекурсивные алгоритмы, чтобы сделать их быстрее и эффективнее. Он также рассказывает о том, как преобразовать традиционный цикл в рекурсивную функцию, и о преимуществах использования хвостовой рекурсии. Его заключительные слова действительно суммировали некоторые из моих ключевых моментов, я думаю:
"Рекурсивное программирование дает программисту лучший способ организации кода таким образом, чтобы его можно было поддерживать и логически согласовывать".
http://www.ibm.com/developerworks/linux/library/l-recurs/index.html
Ссылка 3: Является ли рекурсия когда-либо быстрее, чем зацикливание? (Ответ)
Вот ссылка на ответ на вопрос stackru, который похож на ваш. Автор указывает, что многие тесты, связанные либо с рекурсивными, либо с циклическими, очень специфичны для каждого языка. Императивные языки обычно быстрее с использованием цикла и медленнее с рекурсией и наоборот для функциональных языков. Я полагаю, что основной смысл этой ссылки заключается в том, что очень трудно ответить на вопрос в не зависящем от языка / ситуации слепом смысле.
Рекурсия обходится дороже в памяти, поскольку каждый рекурсивный вызов обычно требует, чтобы адрес памяти был помещен в стек, чтобы впоследствии программа могла вернуться к этой точке.
Тем не менее, во многих случаях рекурсия намного более естественна и удобочитаема, чем циклы - как при работе с деревьями. В этих случаях я бы рекомендовал придерживаться рекурсии.
Как правило, можно ожидать ухудшения производительности в другом направлении. Рекурсивные вызовы могут привести к созданию дополнительных кадров стека; штраф за это варьируется. Кроме того, в некоторых языках, таких как Python (точнее, в некоторых реализациях некоторых языков...), вы можете довольно легко работать с ограничениями стека для задач, которые вы можете задавать рекурсивно, например, для поиска максимального значения в древовидной структуре данных. В этих случаях вы действительно хотите придерживаться петель.
Написание хороших рекурсивных функций может несколько снизить потери производительности, при условии, что у вас есть компилятор, который оптимизирует хвостовые рекурсии и т. Д. (Также дважды проверьте, чтобы убедиться, что функция действительно является хвостовой рекурсивной - это одна из тех ошибок, которые делают многие люди на.)
Помимо "крайних" случаев (высокопроизводительные вычисления, очень большая глубина рекурсии и т. Д.), Предпочтительно использовать подход, который наиболее четко выражает ваши намерения, хорошо спроектирован и удобен в обслуживании. Оптимизировать только после выявления необходимости.
Рекурсия лучше, чем итерация, для задач, которые можно разбить на несколько меньших частей.
Например, чтобы создать рекурсивный алгоритм Фибоначчи, вы разбиваете fib (n) на fib (n-1) и fib (n-2) и вычисляете обе части. Итерация позволяет вам повторять одну и ту же функцию снова и снова.
Тем не менее, Фибоначчи на самом деле является ошибочным примером, и я думаю, что итерация на самом деле более эффективна. Обратите внимание, что fib (n) = fib (n-1) + fib (n-2) и fib (n-1) = fib (n-2) + fib (n-3). FIB (N-1) рассчитывается дважды!
Лучшим примером является рекурсивный алгоритм для дерева. Проблема анализа родительского узла может быть разбита на несколько меньших задач анализа каждого дочернего узла. В отличие от примера Фибоначчи, меньшие проблемы не зависят друг от друга.
Так что да - рекурсия лучше, чем итерация, для задач, которые можно разбить на несколько меньших, независимых, похожих задач.
Ваша производительность ухудшается при использовании рекурсии, потому что вызов метода на любом языке требует большой подготовки: вызывающий код отправляет адрес возврата, параметры вызова, некоторая другая контекстная информация, такая как регистры процессора, может быть где-то сохранена, а во время возврата Вызванный метод отправляет возвращаемое значение, которое затем извлекается вызывающей стороной, и любая ранее сохраненная контекстная информация будет восстановлена. разница в производительности между итеративным и рекурсивным подходом заключается во времени, которое занимают эти операции.
С точки зрения реализации вы действительно начинаете замечать разницу, когда время, необходимое для обработки вызывающего контекста, сопоставимо со временем, которое требуется для выполнения вашего метода. Если ваш рекурсивный метод выполняется дольше, чем вызывающая часть управления контекстом, идите рекурсивным путем, так как код, как правило, более читабелен и прост для понимания, и вы не заметите потери производительности. В противном случае идите итеративно по соображениям эффективности.
Я считаю, что рекурсия хвоста в Java в настоящее время не оптимизирована. Детали разбросаны по всему обсуждению LtU и связанных ссылок. Это может быть функция в следующей версии 7, но, по-видимому, она представляет определенные трудности в сочетании с проверкой стека, поскольку некоторые кадры будут отсутствовать. Проверка стека используется для реализации их детальной модели безопасности начиная с Java 2.
Рекурсия очень полезна в некоторых ситуациях. Например, рассмотрим код для поиска факториала
int factorial ( int input )
{
int x, fact = 1;
for ( x = input; x > 1; x--)
fact *= x;
return fact;
}
Теперь рассмотрим это с помощью рекурсивной функции
int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}
Наблюдая за этими двумя, мы видим, что рекурсию легко понять. Но если он не используется с осторожностью, он также может быть очень подвержен ошибкам. Предположим, если мы пропустим if (input == 0), затем код будет выполняться некоторое время и заканчивается, как правило, переполнением стека.
Во многих случаях рекурсия происходит быстрее из-за кэширования, что повышает производительность. Например, вот итерационная версия сортировки слиянием с использованием традиционной процедуры слияния. Он будет работать медленнее, чем рекурсивная реализация из-за улучшенной производительности кэширования.
Итеративная реализация
public static void sort(Comparable[] a)
{
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
Рекурсивная реализация
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
PS - это то, что рассказал профессор Кевин Уэйн (Принстонский университет) на курсе об алгоритмах, представленных на Coursera.
Во многих случаях это дает намного более элегантное решение по сравнению с итеративным методом, распространенным примером является обход двоичного дерева, поэтому его не обязательно сложнее поддерживать. В общем, итеративные версии обычно немного быстрее (и во время оптимизации вполне могут заменить рекурсивную версию), но рекурсивные версии проще понять и правильно реализовать.
Это зависит от языка. В Java вы должны использовать циклы. Функциональные языки оптимизируют рекурсию.
Недостаток рекурсии состоит в том, что алгоритм, который вы пишете с использованием рекурсии, имеет O(n) пространственную сложность. В то время как итеративный подход имеет пространственную сложность O(1). Это преимущество использования итерации над рекурсией. Тогда почему мы используем рекурсию?
Увидеть ниже.
Иногда проще написать алгоритм с использованием рекурсии, в то время как немного сложнее написать тот же алгоритм с использованием итерации. В этом случае, если вы решите следовать итерационному подходу, вам придется работать со стеком самостоятельно.
Используя рекурсию, вы несете стоимость вызова функции с каждой "итерацией", тогда как с циклом единственное, что вы обычно платите, это увеличение / уменьшение. Таким образом, если код для цикла не намного сложнее, чем код для рекурсивного решения, цикл обычно будет лучше, чем рекурсия.
Рекурсия и итерация зависит от бизнес-логики, которую вы хотите реализовать, хотя в большинстве случаев она может использоваться взаимозаменяемо. Большинство разработчиков идут на рекурсию, потому что это легче понять.
Если вы просто перебираете список, то, конечно же, перебираете.
Несколько других ответов упомянули (в первую очередь) обход дерева. Это действительно прекрасный пример, потому что это очень распространенная вещь для очень распространенной структуры данных. Рекурсия чрезвычайно интуитивно понятна для этой проблемы.
Проверьте методы поиска здесь: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
Рекурсия является более простой (и, следовательно, более фундаментальной), чем любое возможное определение итерации. Вы можете определить полную по Тьюрингу систему только с парой комбинаторов (да, даже рекурсия сама по себе является производным понятием в такой системе). Лямбда- исчисление - это не менее мощная фундаментальная система с рекурсивными функциями. Но если вы хотите правильно определить итерацию, для начала вам понадобится гораздо больше примитивов.
Что касается кода - нет, рекурсивный код на самом деле гораздо легче понять и поддерживать, чем чисто итеративный, поскольку большинство структур данных являются рекурсивными. Конечно, чтобы сделать это правильно, нужен язык с поддержкой функций и замыканий высшего порядка, по крайней мере - для аккуратного получения всех стандартных комбинаторов и итераторов. В C++, конечно, сложные рекурсивные решения могут выглядеть немного безобразно, если только вы не хардкорный пользователь FC++ и тому подобное.
В C++, если рекурсивная функция является шаблонной, тогда у компилятора больше шансов оптимизировать ее, так как все дедукции типов и реализации функций будут происходить во время компиляции. Современные компиляторы также могут встроить функцию, если это возможно. Так что, если использовать флаги оптимизации, такие как -O3 или же -O2 в g++тогда рекурсии могут иметь шанс быть быстрее, чем итерации. В итерационных кодах компилятор получает меньше возможностей для его оптимизации, поскольку он уже находится в более или менее оптимальном состоянии (если он написан достаточно хорошо).
В моем случае я пытался реализовать возведение в степень матрицы путем возведения в квадрат с использованием матричных объектов Armadillo как рекурсивным, так и итерационным способом. Алгоритм можно найти здесь... https://en.wikipedia.org/wiki/Exponentiation_by_squaring. Мои функции были шаблонными, и я рассчитал 1,000,00012x12 матрицы, возведенные во власть 10, Я получил следующий результат:
iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec
iterative + No-optimisation flag -> 2.83.. sec
recursive + No-optimisation flag -> 4.15.. sec
Этот результат был получен при использовании gcc-4.8 с флагом C++11 (-std=c++11) и броненосец 6.1 с интел мкл. Компилятор Intel также показывает аналогичные результаты.
Это зависит от "глубины рекурсии". это зависит от того, насколько накладные расходы на вызов функции будут влиять на общее время выполнения.
Например, вычисление классического факториала рекурсивным способом очень неэффективно из-за: - риска переполнения данных - риска переполнения стека - издержки вызова функции занимают 80% времени выполнения
в то время как разработка алгоритма min-max для анализа позиции в игре в шахматы, которая будет анализировать последующие N ходов, может быть реализована в рекурсии по "глубине анализа" (как я делаю ^_^)
Я бы подумал, что в (не хвостовой) рекурсии будет происходить снижение производительности при выделении нового стека и т. Д. Каждый раз, когда вызывается функция (конечно, зависит от языка).
Рекурсия? С чего начать, вики скажет вам: "Это процесс повторения предметов самоподобным способом"
Когда-то, когда я занимался Си, рекурсия на С ++ была хорошей идеей, наподобие "Хвостовой рекурсии". Вы также найдете много алгоритмов сортировки, использующих рекурсию. Пример быстрой сортировки: http://alienryderflex.com/quicksort/
Рекурсия подобна любому другому алгоритму, полезному для конкретной задачи. Возможно, вы не сможете найти применение сразу или часто, но возникнет проблема, вы будете рады, что она доступна.
Используя только Chrome 45.0.2454.85 м, рекурсия кажется намного быстрее.
Вот код:
(function recursionVsForLoop(global) {
"use strict";
// Perf test
function perfTest() {}
perfTest.prototype.do = function(ns, fn) {
console.time(ns);
fn();
console.timeEnd(ns);
};
// Recursion method
(function recur() {
var count = 0;
global.recurFn = function recurFn(fn, cycles) {
fn();
count = count + 1;
if (count !== cycles) recurFn(fn, cycles);
};
})();
// Looped method
function loopFn(fn, cycles) {
for (var i = 0; i < cycles; i++) {
fn();
}
}
// Tests
var curTest = new perfTest(),
testsToRun = 100;
curTest.do('recursion', function() {
recurFn(function() {
console.log('a recur run.');
}, testsToRun);
});
curTest.do('loop', function() {
loopFn(function() {
console.log('a loop run.');
}, testsToRun);
});
})(window);
РЕЗУЛЬТАТЫ
// 100 прогонов, используя стандартный цикл for
100x для цикла. Время для завершения: 7.683мс
// 100 прогонов с использованием функционально-рекурсивного подхода с хвостовой рекурсией
100-кратный рекурсивный прогон. Время для завершения: 4.841мс
На скриншоте ниже, рекурсия побеждает снова с большим отрывом, когда выполняется при 300 циклах на тест
Вы должны иметь в виду, что при использовании слишком глубокой рекурсии вы столкнетесь с переполнением стека, в зависимости от допустимого размера стека. Чтобы предотвратить это, обязательно предоставьте базовый сценарий, который завершает вашу рекурсию.
Майк прав. Хвостовая рекурсия не оптимизируется компилятором Java или JVM. Вы всегда получите переполнение стека чем-то вроде этого:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
I found another differences between those approaches. It looks simple and unimportant, but it has a very important role while you prepare for interviews and this subject arises, so look closely.
In short: 1) iterative post-order traversal is not easy - that makes DFT more complex 2) cycles check easier with recursion
Details:
In the recursive case, it is easy to create pre and post traversals:
Imagine a pretty standard question: "print all tasks that should be executed to execute the task 5, when tasks depend on other tasks"
Example:
//key-task, value-list of tasks the key task depends on
//"adjacency map":
Map<Integer, List<Integer>> tasksMap = new HashMap<>();
tasksMap.put(0, new ArrayList<>());
tasksMap.put(1, new ArrayList<>());
List<Integer> t2 = new ArrayList<>();
t2.add(0);
t2.add(1);
tasksMap.put(2, t2);
List<Integer> t3 = new ArrayList<>();
t3.add(2);
t3.add(10);
tasksMap.put(3, t3);
List<Integer> t4 = new ArrayList<>();
t4.add(3);
tasksMap.put(4, t4);
List<Integer> t5 = new ArrayList<>();
t5.add(3);
tasksMap.put(5, t5);
tasksMap.put(6, new ArrayList<>());
tasksMap.put(7, new ArrayList<>());
List<Integer> t8 = new ArrayList<>();
t8.add(5);
tasksMap.put(8, t8);
List<Integer> t9 = new ArrayList<>();
t9.add(4);
tasksMap.put(9, t9);
tasksMap.put(10, new ArrayList<>());
//task to analyze:
int task = 5;
List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
System.out.println(res11);**//note, no reverse required**
List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
Collections.reverse(res12);//note reverse!
System.out.println(res12);
private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
List<Integer> result = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
reqPreOrder(tasksMap,task,result, visited);
return result;
}
private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
if(!visited.contains(task)) {
visited.add(task);
result.add(task);//pre order!
List<Integer> children = tasksMap.get(task);
if (children != null && children.size() > 0) {
for (Integer child : children) {
reqPreOrder(tasksMap,child,result, visited);
}
}
}
}
private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
List<Integer> result = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
reqPostOrder(tasksMap,task,result, visited);
return result;
}
private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
if(!visited.contains(task)) {
visited.add(task);
List<Integer> children = tasksMap.get(task);
if (children != null && children.size() > 0) {
for (Integer child : children) {
reqPostOrder(tasksMap,child,result, visited);
}
}
result.add(task);//post order!
}
}
Note that the recursive post-order-traversal does not require a subsequent reversal of the result. Children printed first and your task in the question printed last. Everything is fine. You can do a recursive pre-order-traversal (also shown above) and that one will require a reversal of the result list.
Not that simple with iterative approach! In iterative (one stack) approach you can only do a pre-ordering-traversal, so you obliged to reverse the result array at the end:
List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
Collections.reverse(res1);//note reverse!
System.out.println(res1);
private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
List<Integer> result = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
Stack<Integer> st = new Stack<>();
st.add(task);
visited.add(task);
while(!st.isEmpty()){
Integer node = st.pop();
List<Integer> children = tasksMap.get(node);
result.add(node);
if(children!=null && children.size() > 0){
for(Integer child:children){
if(!visited.contains(child)){
st.add(child);
visited.add(child);
}
}
}
//If you put it here - it does not matter - it is anyway a pre-order
//result.add(node);
}
return result;
}
Looks simple, no?
But it is a trap in some interviews.
It means the following: with the recursive approach, you can implement Depth First Traversal and then select what order you need pre or post(simply by changing the location of the "print", in our case of the "adding to the result list"). With the iterative (one stack) approach you can easily do only pre-order traversal and so in the situation when children need be printed first(pretty much all situations when you need start print from the bottom nodes, going upwards) - you are in the trouble. If you have that trouble you can reverse later, but it will be an addition to your algorithm. And if an interviewer is looking at his watch it may be a problem for you. There are complex ways to do an iterative post-order traversal, they exist, but they are not simple. Example:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/
Thus, the bottom line: I would use recursion during interviews, it is simpler to manage and to explain. You have an easy way to go from pre to post-order traversal in any urgent case. With iterative you are not that flexible.
I would use recursion and then tell: "Ok, but iterative can provide me more direct control on used memory, I can easily measure the stack size and disallow some dangerous overflow.."
Another plus of recursion - it is simpler to avoid / notice cycles in a graph.
Example (preudocode):
dft(n){
mark(n)
for(child: n.children){
if(marked(child))
explode - cycle found!!!
dft(child)
}
unmark(n)
}
Может быть интересно написать это как рекурсию или как практику.
Однако, если код будет использоваться в производственной среде, вам необходимо учитывать возможность переполнения стека.
Оптимизация хвостовой рекурсии может устранить переполнение стека, но хотите ли вы справиться с этим, и вам нужно знать, что вы можете рассчитывать на оптимизацию в вашей среде.
Каждый раз, когда алгоритм рекурсивно повторяется, каков размер данных или n сократился на?
Если вы уменьшаете размер данных или nвдвое каждый раз, когда вы выполняете рекурсию, тогда вам не нужно беспокоиться о переполнении стека. Скажем, если для переполнения стека программа должна быть глубиной 4000 или 10000 уровней, тогда размер ваших данных должен быть примерно 24000, чтобы ваша программа могла переполниться. Чтобы представить это в перспективе, самое большое запоминающее устройство в последнее время может содержать 261 байт, и если у вас есть 261 таких устройств, вы имеете дело только с размером данных 2122. Если вы посмотрите на все атомы во Вселенной, по оценкам, это может быть меньше 284. Если вам нужно иметь дело со всеми данными во Вселенной и их состояниями за каждую миллисекунду с момента рождения Вселенной, по оценкам, 14 миллиардов лет назад, это может быть только 2153. Итак, если ваша программа может обрабатывать 24000 единиц данных илиn, вы можете обрабатывать все данные во вселенной, и программа не будет переполняться. Если вам не нужно иметь дело с числами размером до 24000 (4000-битное целое число), то в целом вам не нужно беспокоиться о переполнении стека.
Однако, если вы уменьшите размер данных или n на постоянную величину каждый раз, когда вы выполняете рекурсию, тогда вы можете столкнуться с переполнением стека, когда ваша программа работает хорошо, когда n является 1000 но в какой-то ситуации, когда n становится просто 20000.
Поэтому, если у вас есть возможность переполнения стека, попробуйте сделать это итеративным решением.
Если итерации атомарны и на порядки дороже, чем проталкивание нового фрейма стека и создание нового потока, и у вас есть несколько ядер, и ваша среда выполнения может использовать все из них, то рекурсивный подход может привести к значительному увеличению производительности в сочетании с многопоточность. Если среднее число итераций непредсказуемо, то было бы неплохо использовать пул потоков, который будет контролировать распределение потоков и не позволит вашему процессу создавать слишком много потоков и перегружать систему.
Например, в некоторых языках существуют рекурсивные реализации многопоточной сортировки слиянием.
Но опять же, многопоточность может использоваться с циклическим, а не с рекурсивным, поэтому насколько хорошо эта комбинация будет работать, зависит от большего количества факторов, включая ОС и механизм распределения потоков.
Насколько я знаю, Perl не оптимизирует хвостовые рекурсивные вызовы, но вы можете это подделать.
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
При первом вызове он выделит место в стеке. Затем он изменит свои аргументы и перезапустит подпрограмму, не добавляя ничего в стек. Поэтому он сделает вид, что никогда не называл себя, превращая его в итеративный процесс.
Обратите внимание, что нет " my @_; " или же " local @_; ", если бы ты это сделал, это больше не сработало.
«Снижается ли производительность, если мы используем цикл вместо рекурсии или наоборот в алгоритмах, где оба могут служить одной и той же цели?»
Обычно да, если вы пишете на императивном языке, итерация будет выполняться быстрее, чем рекурсия, снижение производительности сводится к минимуму в задачах, где итеративное решение требует манипулирования стеками и извлечения элементов из стека из-за рекурсивного характера проблемы. Во многих случаях рекурсивную реализацию намного легче читать, потому что код намного короче, поэтому вам нужно учитывать удобство сопровождения. Особенно в тех случаях, когда проблема имеет рекурсивный характер. Так возьмем, например:
Рекурсивная реализация Ханойской башни:
def TowerOfHanoi(n , source, destination, auxiliary):
if n==1:
print ("Move disk 1 from source",source,"to destination",destination)
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print ("Move disk",n,"from source",source,"to destination",destination)
TowerOfHanoi(n-1, auxiliary, destination, source)
Достаточно короткая и довольно легко читается. Сравните это с итеративным аналогом TowerOfHanoi:
# Python3 program for iterative Tower of Hanoi
import sys
# A structure to represent a stack
class Stack:
# Constructor to set the data of
# the newly created tree node
def __init__(self, capacity):
self.capacity = capacity
self.top = -1
self.array = [0]*capacity
# function to create a stack of given capacity.
def createStack(capacity):
stack = Stack(capacity)
return stack
# Stack is full when top is equal to the last index
def isFull(stack):
return (stack.top == (stack.capacity - 1))
# Stack is empty when top is equal to -1
def isEmpty(stack):
return (stack.top == -1)
# Function to add an item to stack.
# It increases top by 1
def push(stack, item):
if(isFull(stack)):
return
stack.top+=1
stack.array[stack.top] = item
# Function to remove an item from stack.
# It decreases top by 1
def Pop(stack):
if(isEmpty(stack)):
return -sys.maxsize
Top = stack.top
stack.top-=1
return stack.array[Top]
# Function to implement legal
# movement between two poles
def moveDisksBetweenTwoPoles(src, dest, s, d):
pole1TopDisk = Pop(src)
pole2TopDisk = Pop(dest)
# When pole 1 is empty
if (pole1TopDisk == -sys.maxsize):
push(src, pole2TopDisk)
moveDisk(d, s, pole2TopDisk)
# When pole2 pole is empty
else if (pole2TopDisk == -sys.maxsize):
push(dest, pole1TopDisk)
moveDisk(s, d, pole1TopDisk)
# When top disk of pole1 > top disk of pole2
else if (pole1TopDisk > pole2TopDisk):
push(src, pole1TopDisk)
push(src, pole2TopDisk)
moveDisk(d, s, pole2TopDisk)
# When top disk of pole1 < top disk of pole2
else:
push(dest, pole2TopDisk)
push(dest, pole1TopDisk)
moveDisk(s, d, pole1TopDisk)
# Function to show the movement of disks
def moveDisk(fromPeg, toPeg, disk):
print("Move the disk", disk, "from '", fromPeg, "' to '", toPeg, "'")
# Function to implement TOH puzzle
def tohIterative(num_of_disks, src, aux, dest):
s, d, a = 'S', 'D', 'A'
# If number of disks is even, then interchange
# destination pole and auxiliary pole
if (num_of_disks % 2 == 0):
temp = d
d = a
a = temp
total_num_of_moves = int(pow(2, num_of_disks) - 1)
# Larger disks will be pushed first
for i in range(num_of_disks, 0, -1):
push(src, i)
for i in range(1, total_num_of_moves + 1):
if (i % 3 == 1):
moveDisksBetweenTwoPoles(src, dest, s, d)
else if (i % 3 == 2):
moveDisksBetweenTwoPoles(src, aux, s, a)
else if (i % 3 == 0):
moveDisksBetweenTwoPoles(aux, dest, a, d)
# Input: number of disks
num_of_disks = 3
# Create three stacks of size 'num_of_disks'
# to hold the disks
src = createStack(num_of_disks)
dest = createStack(num_of_disks)
aux = createStack(num_of_disks)
tohIterative(num_of_disks, src, aux, dest)
Теперь первый намного легче читать, потому что более короткий код обычно легче понять, чем код, который в 10 раз длиннее. Иногда вы хотите спросить себя, действительно ли дополнительный прирост производительности того стоит? Количество часов, потраченных на отладку кода. Является ли итеративная TowerOfHanoi быстрее, чем рекурсивная TowerOfHanoi? Возможно, но не с большим отрывом. Хотел бы я программировать рекурсивные задачи, такие как TowerOfHanoi, используя итерацию? Конечно нет. Далее у нас есть еще одна рекурсивная функция, функция Аккермана: Использование рекурсии:
if m == 0:
# BASE CASE
return n + 1
elif m > 0 and n == 0:
# RECURSIVE CASE
return ackermann(m - 1, 1)
elif m > 0 and n > 0:
# RECURSIVE CASE
return ackermann(m - 1, ackermann(m, n - 1))
Использование итерации:
callStack = [{'m': 2, 'n': 3, 'indentation': 0, 'instrPtr': 'start'}]
returnValue = None
while len(callStack) != 0:
m = callStack[-1]['m']
n = callStack[-1]['n']
indentation = callStack[-1]['indentation']
instrPtr = callStack[-1]['instrPtr']
if instrPtr == 'start':
print('%sackermann(%s, %s)' % (' ' * indentation, m, n))
if m == 0:
# BASE CASE
returnValue = n + 1
callStack.pop()
continue
elif m > 0 and n == 0:
# RECURSIVE CASE
callStack[-1]['instrPtr'] = 'after first recursive case'
callStack.append({'m': m - 1, 'n': 1, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif m > 0 and n > 0:
# RECURSIVE CASE
callStack[-1]['instrPtr'] = 'after second recursive case, inner call'
callStack.append({'m': m, 'n': n - 1, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif instrPtr == 'after first recursive case':
returnValue = returnValue
callStack.pop()
continue
elif instrPtr == 'after second recursive case, inner call':
callStack[-1]['innerCallResult'] = returnValue
callStack[-1]['instrPtr'] = 'after second recursive case, outer call'
callStack.append({'m': m - 1, 'n': returnValue, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif instrPtr == 'after second recursive case, outer call':
returnValue = returnValue
callStack.pop()
continue
print(returnValue)
И еще раз утверждаю, что рекурсивная реализация намного проще для понимания. Итак, мой вывод: используйте рекурсию, если проблема по своей природе рекурсивна и требует манипулирования элементами в стеке.
Я собираюсь ответить на ваш вопрос, спроектировав структуру данных на Haskell с помощью "индукции", которая является своего рода "двойственной" рекурсии. И тогда я покажу, как эта двойственность приводит к хорошим вещам.
Введем тип для простого дерева:
data Tree a = Branch (Tree a) (Tree a)
| Leaf a
deriving (Eq)
Мы можем прочитать это определение как "Дерево - это ветвь (которая содержит два дерева) или лист (который содержит значение данных)". Так что лист - это своего рода минимальный случай. Если дерево не является листом, то это должно быть составное дерево, содержащее два дерева. Это единственные случаи.
Давайте сделаем дерево:
example :: Tree Int
example = Branch (Leaf 1)
(Branch (Leaf 2)
(Leaf 3))
Теперь предположим, что мы хотим добавить 1 к каждому значению в дереве. Мы можем сделать это, позвонив:
addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a) = Leaf (a + 1)
Во-первых, обратите внимание, что это на самом деле рекурсивное определение. В качестве случаев используются конструкторы данных Branch и Leaf (а так как Leaf минимален и это единственно возможные случаи), мы уверены, что функция завершится.
Что нужно, чтобы написать addOne в итеративном стиле? Как будет выглядеть цикл в произвольном количестве ветвей?
Кроме того, этот тип рекурсии часто может быть учтен в терминах "функтора". Мы можем превратить деревья в функторы, определив:
instance Functor Tree where fmap f (Leaf a) = Leaf (f a)
fmap f (Branch a b) = Branch (fmap f a) (fmap f b)
и определяя:
addOne' = fmap (+1)
Мы можем выделить другие схемы рекурсии, такие как катаморфизм (или сложение) для алгебраического типа данных. Используя катаморфизм, мы можем написать:
addOne'' = cata go where
go (Leaf a) = Leaf (a + 1)
go (Branch a b) = Branch a b