Какова практическая разница между циклом и рекурсией
В настоящее время я работаю в 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);
}
}
Этот метод выше будет делать то же самое, что и цикл, но только с рекурсией.
Может ли кто-нибудь объяснить мне, что в нем используется один из этих методов.
Ответы
Ответ 1
Циклы и рекурсии во многом эквивалентны. Нет программ, которые нужны тем или иным, в принципе вы всегда можете переводить из циклов в рекурсию или наоборот.
Рекурсии более мощные в том смысле, что для перевода рекурсии в цикл может потребоваться стек, который вы должны манипулировать собой. (Попробуйте пересечь двоичное дерево, используя цикл, и вы почувствуете боль.)
С другой стороны, многие языки (и реализации), например Java, не реализуют хвостовую рекурсию должным образом. Рекурсия хвоста - это когда последнее, что вы делаете в функции, - это называть себя (как в вашем примере). Такая рекурсия не должна потреблять какой-либо стек, но на многих языках, что означает, что вы не всегда можете использовать рекурсию.
Ответ 2
Часто проблема легче выражается с помощью рекурсии. Это особенно актуально, когда вы говорите о древовидных структурах данных (например, каталоги, деревья решений...).
Эти структуры данных носят конечный характер, поэтому большая часть времени их обработки более ясна с рекурсией.
Когда глубина стека часто ограничена, и для каждого вызова функции требуется кусок стека, а когда речь идет о возможно бесконечной структуре данных, вам придется отказаться от рекурсии и перевести ее на итерацию.
Особенно функциональные языки хороши при обработке "бесконечной" рекурсии. Императивные языки сосредоточены на итерационных циклах.
Ответ 3
В общем случае рекурсивная функция будет потреблять больше пространства стека (поскольку это действительно большой набор вызовов функций), в то время как итерационное решение не будет. Это также означает, что итеративное решение, в общем, будет быстрее, потому что.
Я не уверен, что это применимо к интерпретируемому языку, например PHP, возможно, что интерпретатор может справиться с этим лучше.
Ответ 4
Цикл будет быстрее, потому что при выполнении дополнительного вызова функции всегда накладные расходы.
Проблема с изучением рекурсии - это много примеров (например, факториалов) - плохие примеры использования рекурсии.
По возможности, придерживайтесь петли, если вам не нужно делать что-то другое. Хорошим примером использования рекурсии является цикл по каждому node в дереве с несколькими уровнями дочерних узлов.
Ответ 5
Рекурсия немного медленнее (поскольку вызовы функций медленнее, чем установка переменной), и использует больше места для стеков вызовов большинства языков. Если вы попытались printnumbers(1, 1000000000), рекурсивная версия, скорее всего, произвела бы фатальную ошибку PHP или даже ошибку 500.
Есть некоторые случаи, когда рекурсия имеет смысл, например, делать что-то с каждой частью дерева (получать все файлы в каталоге и его подкаталогах или, может быть, возиться с XML-документом), но имеет свою цену - в скорости, размер стека и время, потраченное на то, чтобы убедиться, что он не застревает, называя себя снова и снова, пока он не падает. Если цикл имеет больше смысла, это определенно способ пойти.
Ответ 6
Ну, я не знаю о PHP, но большинство языков генерирует вызов функции (на уровне машины) для каждой рекурсии. Таким образом, у них есть потенциал для использования большого количества пространства стека, если только компилятор не выполняет оптимизацию хвостового вызова (если это позволяет ваш код).
В этом смысле петли более "эффективны", потому что они не увеличивают стек. Преимущество рекурсии состоит в том, что она может выражать некоторые задачи более естественным образом.
В этом конкретном случае, с концептуальной (а не реалистической) точки зрения, эти два решения полностью эквивалентны.
Ответ 7
Переполнение стека.
И нет, я не имею в виду сайт или что-то еще. Я ЗНАЧУ "переполнение стека".
Ответ 8
По сравнению с циклами вызов функции имеет свои собственные служебные данные, такие как выделение стека и т.д. И в большинстве случаев циклы более понятны, чем их рекурсивные копии.
Кроме того, вы в конечном итоге будете использовать больше памяти и даже можете выходить из пространства стека, если разница между стартом и остановкой высока, и слишком много экземпляров этого кода работают одновременно (что может случиться, когда вы получите больше трафика).
Ответ 9
Вам не нужна рекурсия для такой плоской структуры. В первом коде, который я когда-либо использовал, рекурсия включала управление физическими контейнерами. Каждый контейнер может содержать материал (список из них, каждый с весами) и/или больше контейнеров, которые имеют вес. Мне нужен общий вес контейнера и все, что он держал. (Я использовал его, чтобы предсказать вес больших рюкзаков, полный снаряжения для кемпинга, без упаковки и взвешивания.) Это было легко сделать с рекурсией и было бы намного сложнее с петлями. Но многие проблемы, которые, естественно, подходят для одного подхода, также могут быть решены с другой.
