Так чем рекурсия отличается от бесконечного цикла? Можно с примерами из жизни?
Аноним 29/08/22 Пнд 13:11:41 #1 №2449128
Так чем рекурсия отличается от бесконечного цикла? Можно с примерами из жизни?
рекурсия самовоспроизводится+повторяется, цикл только повторяется
>с примерами из жизни
Конвеер по сборке игрушечных машинок это бесконечный цикл, в конвеер по сборке матрёшки это рекурсия. очевидно имеется ввиду одной бесконечной матрёшки
Нужно обойти дерево, например.
Рекурсивный вариант - пишешь функцию, обрабатывающую один элемент. Внутри нее для каждрго дочернего элемента вызываешь эту же функцию. Вызываешь функцию на корневом элементе. Готово.
Плюсы - максимально просто, минусы - опасность переполнения стека при большой вложенности.
Вариант с циклом - создаешь очередь, в нее кладешь корневой элемент. Запускаешь цикл "пока не опустеет очередь", в нем вынимаешь из очереди элементы, обрабатываешь их, кладешь в очередь их дочерние элементы.
Плюсы - нет переполнения стека, минусы - накладные расходы на очередь, легче ввстрелить в ногу.
Данный пост - просто иллюстрация этой разницы, не воспринимайте это как руководство как обходить деревья в реальных проектах.
Рекурсивный вариант - пишешь функцию, обрабатывающую один элемент. Внутри нее для каждрго дочернего элемента вызываешь эту же функцию. Вызываешь функцию на корневом элементе. Готово.
Плюсы - максимально просто, минусы - опасность переполнения стека при большой вложенности.
Вариант с циклом - создаешь очередь, в нее кладешь корневой элемент. Запускаешь цикл "пока не опустеет очередь", в нем вынимаешь из очереди элементы, обрабатываешь их, кладешь в очередь их дочерние элементы.
Плюсы - нет переполнения стека, минусы - накладные расходы на очередь, легче ввстрелить в ногу.
Данный пост - просто иллюстрация этой разницы, не воспринимайте это как руководство как обходить деревья в реальных проектах.
рекурсия при каждой итерации увеличивает стек, потому бесконечная рекурсия невозможна
Бесконечный цикл тоже когда-нибудь завершится
Есть примеры программ, работающих исключительно на бесконечном цикле и завершающихся вместе с ним. Любой игровой движок, веб-сервера, и т.п.
Примеры программ, работающих целиком на рекурсии... Ну наверное можно найти, но ни одна из них бесконечно работать не сможет.
Как не программисту объяснить на примерах из жизни их отличие?
Грузчик кидает лопату песка в контейнер и зовёт другого грузчика, тот тоже кидает в контейнер и зовёт, и так далее - это рекурсия.
Грузчик кидает лопату песка в контейнер, второй эту лопату выкидывает, и так далее - это бесконечный цикл.
В первом случае контейнер может переполнится, если только какой то из грузчиков не остановиться, во втором нет.
Покажи ему бесконечный цикл, который не является рекурсией. Он сразу поймёт, что эти понятия не эквивалентны.
В абстрактном понимании бесконечная рекурсия возможна. То, что на реальном пк переполнится стек это уже совсем другое дело. Компьютер на котором выполняется бесконечный цикл тоже рано или поздно выйдет из строя и программа остановится.
Неправильно.
Грузчик кидает лопатой песок - это цикл.
Грузчик напрягает грузчика помладше перекидать весь песок, а тот в свою очередь напрягает другого помладше и т.д. - это рекурсия.
Нахуй ты петросяна врубаешь
О, теоретики компутер саенса в треде. Очень ждали ваших коней в вакууме, так полезных на практике, без них бы ни за что не разобрались бы.
Рекурсия - это вообще не цикл.
Хотя и может быть представлена в виде цикла, при желании.
Но, принципиальное отличие в том, что рекурсия, по идее, всегда конечна.
Потому, что смысл рекурсивного алгоритма - найти решение проблемы. И всегда есть проверка на завершение.
Т.е., бесконечная рекурсия - бессмысленна.
А бесконечный цикл - вполне осмысленная вещь, и встречается повсеместно.
Можно ли придумать анализатор, проверяющий любой рекурсивный алгоритм на завершение?Память стека считаем бесконечной.
>что такое хвостовая рекурсия
На завершение чего-либо в Тьюринг-полном программировании вообще проверить нельзя если я правильно помню. Это называется проблема остановки.
Это не рекурсивная программа, а уебанский язык не умеющий в циклы. В результате приходится такой ненужной рекурсией эмулировать цикл.
В проблеме остановки говорится, что нельзя придумать анализатор для всех программ. Для каких-то подмножеств множества всех алгоритмов вполне себе можно, например для всех алгоритмов вида while(true) (вместо true подставить любое булево выражение) легко можно определить такой анализатор, просто смотрим, чему равно выражение в скобках.
А вот можно ли определить анализатор для множества рекурсивных алгоритмов? Интуитивно кажется, что нельзя, но чето хуй его знает как это доказать.
>чем рекурсия отличается от бесконечного цикла?
Почему именно бесконечного? Рекурсия может иметь ограничение глубины.
В бесконечном цикле каждая итерация заканчивается перед тем, как начинается следующая
в рекурсии функция вызывает саму себя, причем новый вызов не завершает предыдущий и тоже вызывает себя. так идет до какого-нибудь "условия завершения", после чего из самого недавнего вызова программу возвращает в предыдущий вызов и так до самого начального который потом тоже завершается
