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

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

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

Циклы могут повысить производительность вашей программы. Рекурсия может повысить производительность вашего программиста. Выберите, что важнее в вашей ситуации!

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

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

Кроме того, некоторые рекурсивные алгоритмы используют «Ленивая оценка», что делает их более эффективными, чем их итеративные братья. Это означает, что они выполняют дорогостоящие вычисления только в то время, когда они необходимы, а не при каждом запуске цикла.

Этого должно быть достаточно, чтобы вы начали. Я выкопаю несколько статей и примеров для вас тоже.

Ссылка 1: Haskel против PHP (рекурсия против итерации)

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

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

Ссылка 2: Освоение рекурсии

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

«Рекурсивное программирование дает программисту лучший способ организации кода таким образом, чтобы его можно было поддерживать и логически согласовывать».

https://developer.ibm.com/articles/l-recurs/

Ссылка 3: Является ли рекурсия быстрее, чем зацикливание? (Ответ)

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

Является ли рекурсия быстрее, чем зацикливание?

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

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

Как правило, можно ожидать ухудшения производительности в другом направлении. Рекурсивные вызовы могут привести к созданию дополнительных кадров стека; штраф за это варьируется. Кроме того, в некоторых языках, таких как 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.

http://lambda-the-ultimate.org/node/1333

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

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

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 вы должны использовать циклы. Функциональные языки оптимизируют рекурсию.

Если вы просто перебираете список, то, конечно же, перебирайте.

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

Проверьте методы поиска здесь: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

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

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

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

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

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

при разработке алгоритма min-max для анализа позиции в игре в шахматы, который будет анализировать последующие N ходов, можно реализовать рекурсию по «глубине анализа» (как я делаю ^ _ ^)

Рекурсия? С чего начать, вики расскажет вам «это процесс повторения предметов самоподобным способом»

В те времена, когда я занимался Си, рекурсия на С ++ была хорошей идеей, наподобие «Хвостовой рекурсии». Вы также найдете много алгоритмов сортировки, использующих рекурсию. Пример быстрой сортировки: http://alienryderflex.com/quicksort/

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

В C ++, если рекурсивная функция является шаблонной, тогда у компилятора больше шансов оптимизировать ее, так как все дедукции типов и реализации функций будут происходить во время компиляции. Современные компиляторы также могут встроить функцию, если это возможно. Таким образом, если использовать флаги оптимизации, такие как -O3или -O2in g++, то рекурсии могут иметь шанс быть быстрее, чем итерации. В итерационных кодах компилятор получает меньше возможностей для его оптимизации, поскольку он уже находится в более или менее оптимальном состоянии (если он написан достаточно хорошо).

В моем случае я пытался реализовать возведение в матрицу путем возведения в квадрат с использованием матричных объектов Armadillo как рекурсивным, так и итерационным способом. Алгоритм можно найти здесь ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Мои функции были шаблонными, и я рассчитал 1,000,000 12x12матрицы, возведенные в степень 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 flag ( -std=c++11) и Armadillo 6.1 с Intel mkl. Компилятор Intel также показывает аналогичные результаты.

Майк прав. Хвостовая рекурсия не оптимизируется компилятором Java или JVM. Вы всегда получите переполнение стека чем-то вроде этого:

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}

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

Недостатком рекурсии является то, что алгоритм, который вы пишете с использованием рекурсии, имеет O (n) пространственную сложность. Хотя итеративный подход имеет пространственную сложность O (1). Это преимущество использования итерации над рекурсией. Тогда почему мы используем рекурсию?

Увидеть ниже.

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

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

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

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

Насколько я знаю, Perl не оптимизирует хвостовые рекурсивные вызовы, но вы можете это подделать.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

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

Обратите внимание, что нет " my @_;" или " local @_;", если вы сделали это, больше не будет работать.

Используя только 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 циклах на тест

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

Вкратце: 1) итеративный обход по порядку не прост - это делает DFT более сложным 2) проверка циклов легче с помощью рекурсии

Подробности:

В рекурсивном случае легко создать обходы до и после:

Представьте себе довольно стандартный вопрос: «напечатать все задачи, которые должны быть выполнены для выполнения задачи 5, когда задачи зависят от других задач»

Пример:

    //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!
    }
}

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

Не так просто с итеративным подходом! При итеративном подходе (один стек) вы можете выполнять только предварительный порядок обхода, поэтому в конце вы должны обратить массив результатов:

    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;
}

Выглядит просто, нет?

Но это ловушка в некоторых интервью.

Это означает следующее: при рекурсивном подходе вы можете внедрить метод Depth First Traversal, а затем выбрать, какой порядок вам нужен до или после публикации (просто изменив местоположение «print», в нашем случае «добавление в список результатов»). ). С помощью итеративного подхода (один стек) вы можете легко выполнять только обход по предварительному заказу, и поэтому в ситуации, когда дочерние элементы должны быть напечатаны первыми (почти во всех ситуациях, когда вам нужно начать печать с нижних узлов, идущих вверх), вы находитесь в проблема. Если у вас возникли проблемы, вы можете вернуться позже, но это будет дополнение к вашему алгоритму. И если интервьюер смотрит на часы, это может стать для вас проблемой. Существуют сложные способы итеративного обхода после заказа, они существуют, но они не просты . Пример:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

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

Я бы использовал рекурсию и затем сказал бы: «Хорошо, но итеративный может предоставить мне более прямой контроль над используемой памятью, я могу легко измерить размер стека и предотвратить некоторые опасные переполнения ...»

Еще один плюс рекурсии - проще избегать / замечать циклы в графе.

Пример (преудокод):

dft(n){
    mark(n)
    for(child: n.children){
        if(marked(child)) 
            explode - cycle found!!!
        dft(child)
    }
    unmark(n)
}

Может быть интересно написать это как рекурсию или как практику.

Однако, если код будет использоваться в производстве, вам необходимо учитывать возможность переполнения стека.

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

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

Если вы уменьшаете размер данных или nвдвое каждый раз, когда выполняете рекурсию, то в общем случае вам не нужно беспокоиться о переполнении стека. Скажем, если для переполнения стека программа должна быть глубиной 4000 или глубиной 10000, размер вашей программы должен быть примерно 2 ^000, чтобы переполнение стека вашей программой. Для сравнения: в последнее время самое большое устройство хранения может содержать 2 ⁶¹ байт, и если у вас есть 2 ⁶¹ таких устройств, вы имеете дело только с 2 ¹²² размерами данных. Если вы смотрите на все атомы во вселенной, то, по оценкам, это может быть менее 2 ⁸⁴, Если вам нужно иметь дело со всеми данными во вселенной и их состояниями за каждую миллисекунду с момента рождения вселенной, которая оценивается в 14 миллиардов лет назад, это может быть только 2 ¹⁵³ . Таким образом, если ваша программа может обрабатывать 2 ⁰⁰⁰ единиц данных или nвы можете обрабатывать все данные в юниверсе, и программа не будет переполняться стеком. Если вам не нужно иметь дело с числами размером до 2 ⁰⁰⁰ (4000-битное целое число), то в общем случае вам не нужно беспокоиться о переполнении стека.

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

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

Я собираюсь ответить на ваш вопрос, спроектировав структуру данных на 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

Переполнение стека произойдет, только если вы программируете на языке, который не имеет встроенного управления памятью ... В противном случае, убедитесь, что у вас есть что-то в вашей функции (или вызов функции, STDLbs и т. Д.). Без рекурсии было бы просто невозможно иметь такие вещи, как ... Google или SQL, или любое другое место, где нужно эффективно сортировать большие структуры данных (классы) или базы данных.

Рекурсия - это то, что нужно, если вы хотите перебирать файлы, почти наверняка вот так: 'find * | ? grep * 'работает. Вроде бы двойная рекурсия, особенно с конвейером (но не делайте кучу системных вызовов, как многие любят делать, если вы собираетесь что-то делать для других).

Языки более высокого уровня и даже clang / cpp могут реализовать то же самое в фоновом режиме.