{"draftJsState":{"blocks":[{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"В этой статье я расскажу о рекурсии и о том как грамотно работать с ней на языке PHP.","type":"unstyled","key":"ojm3"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":194,"offset":0,"style":"ITALIC"}],"text":"PHP расшифровывается как PHP: Hypertext Preprocessor. Это смущает многих людей, потому что первое слово аббревиатуры это аббревиатура. Этот тип аббревиатуры называется рекурсивной аббревиатурой.\nПеревод Google из официальной документации по PHP","type":"blockquote","key":"6pij2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":16,"offset":0,"style":"BOLD"}],"text":"Понятие рекурсии","type":"header-two","key":"14a3e"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":53,"offset":58,"style":"BOLD"},{"length":53,"offset":58,"style":"ITALIC"}],"text":"Для начала разберёмся с понятием рекурсии. В общем смысле рекурсия это отображение чего-либо внутри самого себя. Рекурсивные алгоритмы используют рекурсивные функции, обладающие данным свойством.","type":"unstyled","key":"5fq6"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":74,"offset":0,"style":"ITALIC"}],"text":"Существует два варианта реализации рекурсивных функций: простой и сложный. В простом случае рекурсивная функция вызывает саму себя. В сложном — функция вызывает другую функцию, которая вызывает исходную функцию, с которой всё начиналось.","type":"unstyled","key":"8flm1"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":23,"offset":263,"style":"ITALIC"}],"text":"Рассмотрим пример из жизни. Если взять два больших зеркала и поставить их друг напротив друга, то можно увидеть бесконечный коридор из изображений зеркал. Каждое зеркало несёт в себе функцию отражения пространства расположенного перед ним. Поэтому здесь мы имеем пример сложной рекурсии (функция вызывает другую функцию, которая вызывает исходную).","type":"unstyled","key":"etuqk"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Другим примером можно взять всем хорошо известное детское стихотворение:","type":"unstyled","key":"a1de"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":32,"offset":0,"style":"ITALIC"},{"length":34,"offset":33,"style":"ITALIC"},{"length":16,"offset":68,"style":"ITALIC"},{"length":29,"offset":85,"style":"ITALIC"}],"text":"У попа была собака, он её любил,\nОна съела кусок мяса, поп её убил,\nВ землю закопал,\nИ надпись написал о том, что:","type":"unstyled","key":"9figo"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":32,"offset":0,"style":"ITALIC"},{"length":34,"offset":33,"style":"ITALIC"},{"length":16,"offset":68,"style":"ITALIC"},{"length":29,"offset":85,"style":"ITALIC"}],"text":"У попа была собака, он её любил,\nОна съела кусок мяса, поп её убил,\nВ землю закопал,\nИ надпись написал о том, что:","type":"unstyled","key":"ag4ls"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"…","type":"unstyled","key":"26m1a"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":23,"offset":39,"style":"ITALIC"}],"text":"Эта докучная сказка представляет собой пример простой рекурсии (здесь функция вызывает саму себя).","type":"unstyled","key":"ckkds"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":16,"offset":0,"style":"BOLD"}],"text":"Глубина рекурсии","type":"header-two","key":"8a3f8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":60,"offset":46,"style":"ITALIC"},{"length":47,"offset":261,"style":"ITALIC"},{"length":60,"offset":46,"style":"BOLD"}],"text":"В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.","type":"unstyled","key":"5ngcu"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":104,"offset":50,"style":"ITALIC"}],"text":"Два примера выше иллюстрируют именно этот случай. Правда в реальном мире, в отличие от мира математических абстракций, всегда есть какие-либо ограничения. Нельзя например бесконечно пересказывать одно и то же стихотворение, так как мы ограничены во времени.","type":"unstyled","key":"53htd"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":54,"offset":59,"style":"ITALIC"}],"text":"Для нас важно, что ограничениям подвержен и сам компьютер. Память компьютера, производительность — не бесконечны. Поэтому применяя рекурсию, нужно понимать её опасности и подводные камни.","type":"unstyled","key":"75nki"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":36,"offset":0,"style":"BOLD"}],"text":"Опасности и подводные камни рекурсии","type":"header-two","key":"e80dj"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Рассмотрим простой пример.","type":"unstyled","key":"o9vf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"}],"text":"","type":"unstyled","key":"c5qjr"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":18,"offset":113,"style":"BOLD"}],"text":"Здесь функция foo() должна вызывать самое себя до бесконечности. В реальных условиях запуск программы приведёт к Segmentation fault, так как произойдёт переполнение стека вызова в силу ограничений на выделенную под него память. Понимая это следует избегать таких конструкций при разработке.","type":"unstyled","key":"771hi"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"То же самое касается и примера со сложной рекурсией.","type":"unstyled","key":"5on6m"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"}],"text":"","type":"unstyled","key":"brr53"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"В PHP две функции не могут вызывать друг друга бесконечно, так как это неизбежно\nприведёт к падению программы.","type":"unstyled","key":"dg27u"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Теперь вернёмся к понятию глубины рекурсии. И рассмотрим следующий пример.","type":"unstyled","key":"eodi1"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"4f91k"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":134,"offset":192,"style":"ITALIC"}],"text":"Здесь рекурсивный вызов должен завершиться по достижении степени вложенности n.\nНа практике при запуске этой программы для больших значений n произойдёт та же самая ошибка переполнения стека. Это так же следует учитывать при обработке больших списков и других структур данных, в которых глубина рекурсии зависит от их размера.","type":"unstyled","key":"252d4"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":28,"offset":0,"style":"BOLD"}],"text":"Рекурсивные алгоритмы на PHP","type":"header-two","key":"a8bog"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Теперь мы можем приступить к исследованию алгоритмов основанных на рекурсии.","type":"unstyled","key":"6bv2p"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Существует множество таких алгоритмов:","type":"unstyled","key":"esb2e"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Нахождение факториала","type":"unordered-list-item","key":"c2po0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Вычисление последовательности Фибоначчи","type":"unordered-list-item","key":"cnfqr"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Поиск максимального элемента в массиве","type":"unordered-list-item","key":"dmbh5"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Вычисление перестановок Ханойских башен","type":"unordered-list-item","key":"5b22e"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Рассчёт вариантов размена суммы монетами","type":"unordered-list-item","key":"3msjt"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Рекурсивный обход дерева","type":"unordered-list-item","key":"79g06"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"и т.д.","type":"unordered-list-item","key":"cgk19"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Рассмотрим некоторые из них.","type":"unstyled","key":"2cccj"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":39,"offset":0,"style":"BOLD"}],"text":"Вычисление последовательности Фибоначчи","type":"header-three","key":"d25l8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Следует сделать лирическое отступление, которое касается истории открытия данной последовательности…","type":"unstyled","key":"m6f9"},{"data":{"image":{"id":"5e8751e18274cd4de9210746"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"akbfd"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Вернёмся к нашему алгоритму. Знание рекуррентного соотношения позволяет нам с лёгкостью реализовать этот алгоритм на PHP:","type":"unstyled","key":"5hc3f"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"}],"text":"","type":"unstyled","key":"5l265"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"С точки зрения программирования нам интересно знать насколько быстро он выполняется по сравнению с его реализацией на основе итераций, например этой:","type":"unstyled","key":"eh6ap"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"}],"text":"","type":"unstyled","key":"cukc0"},{"data":{},"depth":0,"entityRanges":[{"key":0,"length":9,"offset":65}],"inlineStyleRanges":[{"length":87,"offset":96,"style":"ITALIC"}],"text":"Если сделать тест выполнения с замером времени с помощью функции microtime, то обнаружится, что итеративная версия алгоритма выполняется гораздо быстрее, нежели его рекурсивный аналог. Почему это происходит?","type":"unstyled","key":"f74ch"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Дело в том, что реализация рекурсивного алгоритма «в лоб» обладает одним существенным недостатком. А именно при такой реализации вызов функции для одного и того же аргумента производится многократно. Чтобы это увидеть, нужно внимательно рассмотреть само рекуррентное соотношение.","type":"unstyled","key":"cirpb"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":81,"offset":0,"style":"ITALIC"},{"length":49,"offset":115,"style":"ITALIC"}],"text":"Повторные вызовы функции с одинаковыми аргументами занимает дополнительное время. Чтобы избежать этого, используют подход восходящего динамического программирования, который состоит в том, что задача разбивается на подзадачи и каждая подзадача решается только один раз. В нашем примере это можно реализовать в виде :","type":"unstyled","key":"7as7u"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"}],"text":"","type":"unstyled","key":"fjb92"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Таким образом вызов функций над одним и тем же аргументом производится лишь однажды, в случае повторных вызовов производится обращение к памяти к уже вычисленным значениям. Такой алгоритм выполняется гораздо быстрее, чем его простая реализация. Но всё же при этом он значительно уступает итеративной версии. Вы спросите в чём же дело?","type":"unstyled","key":"2rns9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":147,"offset":17,"style":"ITALIC"},{"length":58,"offset":209,"style":"ITALIC"}],"text":"Оказывается, что при рекурсивном вызове функций создаются копии её аргументов в стеке и следовательно дополнительные затраты на время выполнения операций копирования.\nЧтобы обойти это, может быть использована парадигма Объектно-Ориентированного Программирования (ООП). К примеру мы можем создать массив внутри объекта, который будет иметь рекурсивный метод, внутри которого будет доступ к этому массиву так, что не потребуется передавать этот массив в качестве параметра для каждого вызова этого метода:","type":"unstyled","key":"pfov"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"}],"text":"K[$n] == 0) {","type":"unstyled","key":"ajh1l"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":86,"offset":0,"style":"BOLD"}],"text":" \t$this->K[$n]=$this->F_recursive($n-1,$this->K) + $this->F_recursive($n-2,$this->K);","type":"unstyled","key":"b8tip"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":3,"offset":0,"style":"BOLD"}],"text":" }","type":"unstyled","key":"9rddv"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":22,"offset":0,"style":"BOLD"}],"text":" return $this->K[$n];","type":"unstyled","key":"7d23o"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":3,"offset":0,"style":"BOLD"}],"text":" }","type":"unstyled","key":"5vc15"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":21,"offset":0,"style":"BOLD"}],"text":" // Интерфейс класса","type":"unstyled","key":"cj7s7"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":39,"offset":0,"style":"BOLD"}],"text":" public function getNumberByIndex($n){","type":"unstyled","key":"6f8b5"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":34,"offset":0,"style":"BOLD"}],"text":" $this->K=array_fill(0,$n+1,0);","type":"unstyled","key":"19lu2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":34,"offset":0,"style":"BOLD"}],"text":" return $this->F_recursive($n);","type":"unstyled","key":"a4r3l"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":3,"offset":0,"style":"BOLD"}],"text":" }","type":"unstyled","key":"bsmni"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":0,"style":"BOLD"}],"text":"}","type":"unstyled","key":"aj383"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":15,"offset":0,"style":"BOLD"}],"text":"function F($n){","type":"unstyled","key":"ukl0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":31,"offset":0,"style":"BOLD"}],"text":" $Fibonachi = new Fibonachi();","type":"unstyled","key":"pua4"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":42,"offset":0,"style":"BOLD"}],"text":" return $Fibonachi->getNumberByIndex($n);","type":"unstyled","key":"6rkni"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":0,"style":"BOLD"}],"text":"}","type":"unstyled","key":"cm1gp"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":2,"offset":0,"style":"BOLD"}],"text":"?>","type":"unstyled","key":"f506u"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Время выполнения этой программы уже приближается к времени выполнения программы основанной на итерациях. Но всё же для достаточно больших значений n мы будем иметь отставание рекурсивной версии от его итеративного эквивалента, которое может быть значительным в практическом плане. Тогда же в чём смысл рекурсии спросите вы?","type":"unstyled","key":"ajhvn"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Предлагаю вам пока самостоятельно поразмышлять на эту тему. Мы начнём с этого в следующей части.","type":"unstyled","key":"9tf8u"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":" ","type":"unstyled","key":"amg22"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":43,"offset":0,"style":"ITALIC"}],"text":"Можно ли стать программистом за год с нуля?","type":"blockquote","key":"39b29"},{"data":{},"depth":0,"entityRanges":[{"key":1,"length":23,"offset":60}],"inlineStyleRanges":[{"length":59,"offset":0,"style":"ITALIC"},{"length":23,"offset":60,"style":"ITALIC"}],"text":"Читайте в моей бесплатной мини-книге «Путь в программисты». Скачать её можно здесь.","type":"blockquote","key":"f40rn"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"marker","key":"9njK2jSQBsYqxfw77ndv"}],"entityMap":{"0":{"data":{"href":"https://www.php.net/manual/en/function.microtime.php","url":"https://www.php.net/manual/en/function.microtime.php"},"mutability":"MUTABLE","type":"LINK"},"1":{"data":{"href":"https://sheremetev.aoserver.ru/?r=ac&id=8818&lg=ru","url":"https://sheremetev.aoserver.ru/?r=ac&id=8818&lg=ru"},"mutability":"MUTABLE","type":"LINK"}}},"mentions":[]}