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