В чем практическая разница между циклом и рекурсией

Question

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

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

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

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

Пожалуйста, прости меня за любые ошибки кодирования

Цикл:

printnumbers(1,10);

public function printnumbers($start,$stop)
{
    for($i=$start;$i<=$stop;$i++)
    {
        echo $i;
    }
}

Теперь приведенный выше код просто выводит цифры.

Теперь давайте сделаем этос рекурсией:

printnumbers(1,10);

public function printnumbers($start,$stop)
{
    $i = $start;
    if($i <= $stop)
    {
        echo $i;
        printnumbers($start+1,$stop);
    }
}

Этот метод выше будет делать то же самое, что и цикл, но только с рекурсией.

Может кто-нибудь объяснить мне, что отличает использование одного изэти методы.

Answer 1

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

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

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

Answer 2

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

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

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

Особенно функциональные языки хорошо справляются с «бесконечной» рекурсией. Императивные языки ориентированы на итерационные циклы.

Answer 3

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

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

Answer 4

Цикл будет быстрее, поскольку при выполнении дополнительного вызова функции всегда есть издержки.

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

Где возможно, придерживайтесь петли, если вам не нужно делать что-то другое. Хорошим примером использования рекурсии является цикл по каждому узлу в дереве с несколькими уровнями дочерних узлов.

Answer 5

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

Я не уверен, относится ли это к интерпретируемому языку, такому как PHP, хотя, возможно, что интерпретатор справится с этим лучше.

Answer 6

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

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

Answer 7

Переполнение стека.

И нет, я не имею в виду веб-сайт или что-то в этом роде. Я имею в виду «переполнение стека».

Answer 8

Вам не нужна рекурсия для такой плоской структуры.Первый код, который я когда-либо использовал для рекурсии, включал управление физическими контейнерами.Каждый контейнер может содержать вещи (список из них, каждый с весами) и / или несколько контейнеров, которые имеют вес.Мне нужен был общий вес контейнера и все, что он вмещал.(Я использовал его, чтобы предсказать вес больших рюкзаков, заполненных туристическим снаряжением, без упаковки и взвешивания.) Это было легко сделать с помощью рекурсии и было бы намного сложнее с петлями.Но многие виды проблем, которые естественно подходят для одного подхода, можно решать и с другим.

Answer 9

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

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