История Рекурсии
Какой-то процесс Давайте для начала явно отметим отличие рекурсии (в общем смысле) от процесса. Эти понятия никак не связаны. Рекурсия — просто абстрактная концепция, которую можно наблюдать в природе, которая используется в математике и в других областях. Такая же абстрактная, как, например, музыкальная гармония.
Какой-то процесс Давайте для начала явно отметим отличие рекурсии. Рекурсия используется, когда можно выделить самоподобие объекта. Приведем несколько примеров рекурсии. Рекурсия в физике. Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал. Рекурсия в языке и литературе. Всем известная притча «У попа была собака» является типичной рекурсией. В общем, гурилка из меня исключительно картонный, так что постигать Дао Рекурсии тебе, читатель, всё равно придётся самостоятельно, я лишь постараюсь выдать несколько волшебных пенделей в нужном направлении. Прикладное программирование всегда занимается решением прикладных задач путем прикладывания усилий программиста для достижения результата в неидеальных условиях.
Пример рекурсии: художник рисует картину, в которой он рисует картину, в которой он рисует картину. Теперь на секунду забудем про рекурсию, и просто подумаем про компьютеры. Для выполнения задач компьютерам нужны инструкции. Когда компьютер выполняет набор инструкций — это процесс. Ваш работающий сейчас браузер — это процесс. Простой цикл, выводящий на экран десять раз число '42' — это процесс. Некоторые задачи можно решать рекурсивно, то есть в инструкциях использовать эту концепцию, когда что-то является частью самого себя.
В частности, функция может быть частью самой себя, то есть вызывать саму себя. Есть два метода решения задач с использованием рекурсии: рекурсивный процесс и итеративный процесс. Рекурсия в них не отличается: в каждом из подходов функция вызывает саму себя, рекурсивно. Отличаются способы использования идеи рекурсии.
Если продолжить аналогию с музыкальной гармонией, то можно подумать про фортепиано. При написании музыки можно использовать эту концепцию — «гармонию звуков». И можно придумать разные способы: рассчитывать частоты звуков (ноты) математическими формулами или рассчитывать правильные расстояния между клавишами. Я в детстве научился находить правильные расстояния между клавишами на фортепиано, и получал гармоничные комбинации звуков, но понятия не имел, что это за ноты. А профессиональный музыкант знает теорию и подбирает гармонию другими методами. В любом случае, гармония есть гармония, эта концепция не меняется, меняются лишь способы ее использования.
В чем отличие итеративного процесса от рекурсивного? Главная фишка в аккумуляторе или, иными словами, в запоминании. Рекурсивный процесс постоянно говорит « я это запомню и потом посчитаю» на каждом шаге рекурсии. «Потом» наступает в самом конце.
Книга История Рекурсии
Когда рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вниз больше нельзя. Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа.
Тут прямо физически видно, как растет использование памяти: процессу нужно запоминать все больше и больше чисел Рекурсивный процесс — это процесс с отложенным вычислением. Итеративный процесс постоянно говорит « я сейчас посчитаю все что можно и продолжу» на каждом шаге рекурсии. Ему не нужно ничего запоминать вне вызова, он всегда считает все в первый возможный момент, и каждый шаг рекурсии может существовать в изоляции от прошлых, потому что вся информация передается из шага в шаг. Когда итеративный процесс считает факториал 6, то ему не нужно запоминать числа. Нужно лишь считать и передавать результат дальше, в новый вызов. Когда мы находимся в очередном вызове функции, снаружи этого вызова в памяти ничего не нужно запоминать. Тут видно, что использования памяти не растет Рекурсивный процесс это чувак, который все дела откладывает на вечер пятницы.
В течение недели у него мало работы, а в пятницу завал. Но ему так нравится:) Итеративный процесс это чувак, который все делает при первой возможности. У него работа равномерно распределена по неделе, а пятница — просто обычный день, но последний.
Также: Доказательство корректности программ В отличие от явно-циклических программ, для доказательства корректности рекурсивных нет необходимости искусственно вводить. Аналитическое доказательство корректности рекурсивной функции сводится к методу математической индукции, то есть к доказательству следующих утверждений:. Корректность рекурсивного обращения. Доказывается, что результат, вычисляемый в любой рекурсивной ветви функции, будет верным при условии, что параметры функции заданы корректно и соответствующие рекурсивные вызовы вернут верный результат.
История Рекурсии Читать
Корректность всех терминальных ветвей. Доказывается, что все терминальные ветви возвращают верные значения. Как правило, это доказательство тривиально, так как терминальные ветви обычно никаких вычислений не содержат. Достижимость терминальной ветви для любого корректного набора параметров после конечного числа рекурсивных вызовов. Доказывается, что изменение параметров вызова функции, которое производится при рекурсивном обращении, через конечное число рекурсивных вызовов приведёт к одному из наборов параметров, для которых существует терминальная ветвь.
Из суммы первого и второго утверждений следует, что в случае достижения терминальной ветви (а это значит — во всех случаях, когда вычисление функции окажется конечным) функция вернёт правильный результат. Третье положение доказывает, что конечным будет любое вычисление. Следовательно, любой вызов функции с корректными параметрами вернёт правильный результат (с очевидной «технической» оговоркой — если глубина рекурсии не окажется настолько большой, что вызовет переполнение памяти). Данные Рекурсивное определение данных возникает тогда, когда структура данных (запись, объект) содержит вложенный объект, структурно аналогичный самому себе или (что бывает чаще) ссылку на такой же объект.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение способно описать потенциально бесконечную структуру данных. Подобные структуры используются при описании.
История Рекурсии
Пример описания списка. Также: В лингвистике рекурсией называют способность языка порождать вложенные предложения и конструкции. Базовое предложение « кошка съела мышь» может быть за счёт рекурсии расширено как « Ваня догадался, что кошка съела мышь», далее как « Катя знает, что Ваня догадался, что кошка съела мышь» и так далее. Рекурсия считается одной из, то есть свойственна любому естественному языку. Однако в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии —, которое отмечает лингвист. В культуре. Рекурсивный герб России.
Рассказ из «» о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).: (GNU Not Unix), (PHP: Hypertext Preprocessor), ( Wine Is Not an Emulator) и т. д. является рекурсивно-определённым графическим объектом: в правой лапе изображённого на нём двуглавого орла зажат скипетр, который венчается уменьшенной копией герба. Инструкция на холодильник samsyng no frost 268.
Так как на этом гербе в правой лапе орла также находится скипетр, получается бесконечная рекурсия. Рассказ «Порочный круг».
Стихотворение детского поэта «Жучок». Стихотворение «Сон». Поисковая система Google при запросе «рекурсия» выводит надпись «Возможно, вы имели в виду: рекурсия» См.
Также. Примечания.