Что представляет собой практическое различие между циклом и рекурсией

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

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

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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

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

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

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

Answer 8

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

Answer 9

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

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