Рекурсия в линукс это
Обновлено: 03.07.2024
При первом знакомстве с концепцией рекурсии, она может показаться странной и отталкивающей. Это кажется почти парадоксальным: как мы можем найти решение проблемы, используя решение той же проблемы? Несмотря на это, в большинстве проектов, рекурсию используют в программировании уже на ранних стадиях производства.
Я думаю, что тем, кто пытается постигнуть концепцию рекурс и и, следует сначала понять, что рекурсия — это больше, чем просто практика в программировании. Это философия решения проблем, которые можно решать частями, не трогая основную часть проблемы, при этом, проблема упрощается или становится меньше. Рекурсия применима не только в программировании, но и в простых повседневных задачах. Например, возьмите меня, пишущего эту статью: допустим, я хочу написать около 1000 слов, и ставлю цель писать 100 слов каждый раз, когда сажусь за работу. Получается, что в первый раз я напишу 100 слов и оставляю 900 слов на потом. В следующий раз я напишу ещё 100 слов, а оставлю 800. Я буду продолжать, пока не останется 0 слов. Каждый раз, я частично решаю проблему, а оставшаяся часть проблемы уменьшается.
Работу над статьей можно представить в виде такого кода:
Также, этот алгоритм можно реализовать итеративно:
Если рассматривать вызов функции write_words(1000) в любой из этих реализаций, вы обнаружите, одинаковое поведение. На самом деле, каждую задачу, которую можно решить с помощью рекурсии, мы также можем решить с помощью итерации (циклы for и while ). Так почему же стоит использовать именно рекурсию?
Почему рекурсия?
Хотите верьте, хотите нет, но с помощью рекурсии некоторые проблемы решить легче, чем с помощью итерации. Иногда рекурсия более эффективна, иногда более читаема, а иногда просто быстрее реализуется. Некоторые структуры данных, такие как деревья ― хорошо подходят для рекурсивных алгоритмов. Существуют языки программирования, в которых вообще нет понятия цикла — это чисто функциональные языки, такие как Haskell, они полностью зависят от рекурсии для итеративного решения задач. Я хочу сказать, что программисту не обязательно понимать рекурсию, но хороший программист, просто обязан в этом разбираться. Более того, понимание рекурсии сделает вас отличным «решателем» проблем, не только в программировании!
Суть рекурсии
В общем, рекурсивный подход подразумевает разделение сложной задачи, на один простой шаг к её решению и оставшуюся часть, которая становится упрощённой версией той же задачи. Затем этот процесс повторяется. Каждый раз вы совершаете один шаг, до тех пор, пока задача упростится до одного простейшего решения (его называют «базовым случаем»). Простейшее решение нашего базового случая с шагами, которые мы предприняли, чтобы добраться до него, образуют решение нашей первоначальной задачи.
Мы каждый раз разделяем задачу «P» на шаги и оставшуюся упрощённую задачу той же формы, что и оригинал, пока не достигнем простого решения небольшой проблемы (базовый случай).Предположим, у нас есть фактические данные определённого типа, назовём их dₒ. Идея рекурсии состоит в том, чтобы предположить, что мы уже решили задачу или вычислили желаемую функцию f для всех форм этого типа данных. Каждая из этих форм проще общей сложности dₒ, которую нам нужно определить. Следовательно, если мы можем найти способ выражения f(dₒ), исходя из одной или нескольких частей f(d), где все эти d проще, чем dₒ, значит мы нашли решение для f(dₒ). Мы повторяем этот процесс, и рассчитываем, что в какой-то момент оставшиеся f(d) станут настолько простыми, что мы сможем легко реализовать фиксированное, окончательное решение для них. В итоге, решением исходной задачи станет поэтапное решение более простых задач.
В приведённом выше примере (про написание статьи), данными является текст, содержащийся в документе, который я должен написать, а степень сложности — это длина документа. Это немного надуманный пример, но если предположить, что я уже решил задачу f(900) (написать 900 слов), то все, что мне нужно сделать, чтобы решить f(1000), ― это написать 100 слов и выполнить решение для 900 слов, f(900).
Давайте рассмотрим пример получше: с числами Фибоначчи, где 1-е число равно 0, второе равно 1, а nᵗʰ число равно сумме двух предыдущих. Предположим, у нас есть функция Фибоначчи, которая сообщает нам nᵗʰ число:
Как будет выглядеть выполнение такой функции? Возьмём для примера fib(4) :
Визуализация древа рекурсии, показывающая рекурсивное вычисление, которое приводит к fib(4) = 3. Обратите внимание, что вычисление сначала выполняется в глубину.В процессе рекурсивного решения задачи полезно повторять мантру: «Притворяйся, пока это не станет правдой», то есть делай вид, что ты уже решил более простую часть задачи. Затем попытайся уменьшить большую часть задачи, чтобы использовать решение упрощённой части. Подходящая для рекурсии задача, на самом деле должна иметь небольшое количество простых частей, которые нужно решить явно. Другими словами, метод сокращения до более простой задачи может быть использован для решения любого другого случая. Это можно проиллюстрировать на примере чисел Фибоначчи, где для определения fib(n) мы действуем, как будто мы уже рассчитали fib(n-1) и fib(n-2). В тоже время мы рассчитываем, что эти каскады и упрощения приведут к более простым случаям, пока мы не достигнем fib(0) и fib(1) , которые имеют фиксированные и простые решения.
Рекурсивный подход — дело тонкое, и зависит от того, какую проблему вы пытаетесь решить. Тем не менее, есть некоторая общая стратегия, которая поможет вам двигаться в правильном направлении. Эта стратегия состоит из трёх шагов:
- Упорядочить данные
- Решить малую часть проблемы
- Решить большую часть проблемы
Упорядочивание данных
Этот шаг является ключевым для решения проблем рекурсивным способом, и все же его часто упускают из виду или выполняют неявно. Какие бы данные мы ни использовали, будь то числа, строки, списки, бинарные древа или люди, необходимо явно найти целесообразный порядок, который даст нам видение, как упростить задачу. Порядок полностью зависит от конкретной задачи, но для начала стоит подумать об очевидных вариантах. Например: числа можно упорядочить по величине, строки и списки можно упорядочить по длине, бинарные древа по глубине, а люди могут быть упорядочены бесконечным количеством разумных способов: рост, вес или должность в организации. Это упорядочивание должно соответствовать степени сложности задачи, которую мы пытаемся решить.
После того, как мы упорядочили данные, нам нужно подумать об этом, как о чём-то, что мы можем сократить. На самом деле, мы можем записать наш порядок в виде последовательности:
0, 1, 2, …, n для чисел (т.е. для int данных d, степень(d) = d)
[], [■], [■, ■], …, [■, … , ■] для списков (len = 0, len = 1, …, len = n и т.д. для списка d, степень(d) = len(d))
Двигаясь справа налево, мы идём от общего («большая часть задачи») случая, к базовым («маленьким частям») случаям. В нашем примере с функцией reverse мы работаем со строкой, и можем взять длину строки за основу, для упорядочивания или определения степени сложности задачи.
Решаем малую часть проблемы
Переходим к общим случаям
На этом этапе мы обрабатываем данные двигаясь вправо, то есть в сторону высокой степени. Как правило, мы рассматриваем данные произвольной степени, и ищем способ решения проблемы, упрощая её до выражения, представляющего ту же проблему, но в меньшей степени. Например, в случае с числами Фибоначчи мы начали с произвольного значения n и упростили fib(n) до fib(n-1) + fib(n-2) , что является выражением, содержащим два экземпляра той же задачи, но в меньшей степени (n-1 и n-2, соответственно).
Возвращаясь к алгоритму reverse , мы можем рассмотреть произвольную строку с длинной n, и предположить, что наша reverse функция работает для всех строк с длинной меньше n. Как мы можем использовать это, решая задачу для строки с длинной n? Мы могли бы сделать реверс строки, переместив всё, кроме последнего символа, а затем вставить этот последний символ в начало. В коде:
где string[-1] соответствует последнему символу, а string[:-1] соответствует строке без последнего символа (это питонизм). Последний член функции reverse(string[:-1]) , и является нашей исходной задачей, но он оперирует со строкой длины n-1. Таким образом, мы выразили нашу исходную задачу в решении той же задачи, но в уменьшенной степени.
Применив это решение к функции reverse , мы получаем следующее:
Часто бывает так, что нам нужно рассмотреть несколько рекурсивных случаев, так как данные определённого типа, могут принимать разные формы, но это полностью зависит от задачи. Например, если мы хотим сгладить список элементов, некоторые из которых сами могут быть списками, нам нужно будет различать случаи, когда элемент, который мы вытаскиваем из списка, является отдельным элементом или подсписком, что приводит по крайней мере к двум рекурсивным случаям.
Напутствие
Единственный способ улучшить свои навыки в рекурсии — это практика. В интернете можно найти тысяч примеров задач, подходящих для рекурсивного решения — испытайте себя. Однажды, вы неизбежно научитесь рекурсии, но, если у вас возникнут трудности с рекурсивным решением проблемы, попробуйте вместо этого итерацию. Рекурсия поможет вам решать проблемы не только в программировании, но и в повседневной жизни. Если проблема не подходит для рекурсии, что ж, такое бывает; со временем вы научитесь чувствовать, где следует использовать рекурсивный подход, а где итеративный.
Иногда в более сложных рекурсивных задачах, шаги 2 и 3, о которых мы говорили, принимают форму более циклического процесса. Если вы не можете быстро найти общее решение проблемы, попробуйте решить рекурсивные (большие) случаи и базовые (маленькие) случаи, которые сможете найти, а затем посмотрите, как в результате разделились разные части данных. Это должно выявить любые недостающие базовые и рекурсивные случаи или те, которые плохо взаимодействуют друг с другом и нуждаются в переосмыслении.
Наконец, помните, что выявление порядка является самым важным шагом к решению рекурсивной задачи, и ваша цель рассмотреть как правый (рекурсивный), так и левый (базовый) случаи этого порядка, чтобы решить задачу для всех данных определённого типа.
Иногда возникает путаница между опциями -r и -R, каждая из которых в разных программах может означать рекурсивную обработку файлов в найденных каталогах. А может означать нечто совершенно противоположное или работать не так, как этого ожидал пользователь. Попробуем разобраться, в каких случаях что используется.
Эпиграф
— Это новый «Гарри Поттер». Я заказал версии для детей и взрослых, чтобы проверить, что в тексте нет различий.
Морис Мосс, The IT Crowd.
chmod
Ключ -r у chmod интерпретируется как «запретить всем чтение файла», а 755 в данном случае рассматривается как название файла, у которого изменяются права. Поскольку в подавляющем большинстве случаев файла с таким названием в текущей директории отсутствует, то команда возвращает ошибку.
chown, chattr, chgrp
У вышеперечисленных команд опция -r просто отсутствует. Для рекурсивной обработки директорий необходимо использовать опцию -R. Очевидно, так сделано из солидарности с «братской» командой chmod
Несмотря на то, что в странице документации cp из GNU coreutils сказано, что опции -r и -R равнозначны и означают рекурсивную обработку встречающихся директорий, опция -r, в отличие от -R, не соответствует стандарту POSIX и ее указание может повлечь за собой неожиданные последствия в случае, если очередной копируемый объект является чем-то отличным от обычного файла или директории (например, символической ссылкой, fifo или сокетом). В таких случаях некоторые реализации cp просто копируют содержимое ссылки/fifo, тогда как при -R такие объекты пересоздаются заново. Раньше такое поведение было присуще GNU cp, о чем до сих пор имеется свидетельство в русском man cp. Что касается более правильных (чем Linux) систем, то, например, в BSD-версии cp опция -r работает в «режиме совместимости», т.е. не создает символическую ссылку заново, а копирует содержимое в файл с тем же именем.
Ключ -r команды ls означает «обратный порядок сортировки»
Правильно:
rm, grep
Зато в следующих случаях употребление -r/-R равнозначно:
Что касается grep, то, во-первых, обе опции не соответствуют POSIX (но, похоже, присутствуют во всех реализациях) Во-вторых, иногда возникает путаница между опциями -i (игнорировать регистр) и -I (пропускать двоичные файлы). Но это уже тема для другого разговора :)
Прочие команды
Поскольку команд, в том или ином виде поддерживающих рекурсивную обработку каталогов, набралось довольно много, то я попробовал свести их в одну таблицу.
| команда | -r | -R |
|---|---|---|
| chacl | рекурсия | удаление ACL только с файлов |
| setfacl | не поддерживается | рекурсия |
| cvs | номер ревизии | рекурсия |
| diff | рекурсия | не поддерживается |
| gzip/gunzip | рекурсия | не поддерживается |
| zip | рекурсия | рекурсия, начиная с текущей директории (см. man zip, там есть существенная разница в обработке -r и -R) |
| rsync | рекурсия | использование относительных путей |
| wget | рекурсия | указывает список отвергаемых шаблонов |
Заключение
Как видно, в большинстве случаев для указания рекурсии используется опция -r в нижнем регистре, в противовес стандартным утилитам, для которых характерно все же -R. Поэтому совет один: в случае сомнения смотрите в man, там все написано :)
Постскриптум
По абзацу про cp видно, что русская документация в некоторых дистрибутивах (не будем показывать пальцем на Debian и Ubuntu) не соответствует реальному положению дел. В частности, несмотря на то, что в jaunty используется GNU coreutis 6.10, русский man описывает cp версии 4.1. Желающие могут самостоятельно сравнить свою версию man 1 cp с локализованной. Другими словами, русская страница документации cp в силу своей древности вводит пользователя в заблуждение, т.е. врёт. По этой причине я рекомендую сделать apt-get remove manpages-ru.
2 комментария
-
Comment by anon :
> По этой причине я рекомендую сделать apt-get remove manpages-ru
Плюсую. Помню как потерял с час времени, из за феерично переведенного мана:
If from is not NULL, and the underlying protocol provides the source address, this source address is filled in.
scp неплохо было бы упомянуть. Нигде проблем с -r/-R не испытывал, только в scp почему-то постоянно пишу -R.
Наверное, всем известно, что у оболочки Bash есть встроенные команды, которых нет в папках /bin или /usr/bin. Они встроены в оболочку и выполняются в виде функций. В одной из предыдущих статей мы рассматривали написание скриптов на Bash. Мы обговорили там почти все, как должны выглядеть скрипты, использование условий, циклов, переменных, но не останавливались на функциях.
В сегодняшней статье мы исправим этот недостаток. Как и в любом языке программирования, в Bash есть функции их может быть очень полезно использовать. Мы рассмотрим использование функций bash, как их писать и даже как создавать библиотеки из этих функций.
Написание функций Bash
Сначала нужно понять что такое функция в нашем контексте. Функция - это набор команд, объединенных одним именем, которые выполняют определенную задачу. Функция вызывается по ее имени, может принимать параметры и возвращать результат работы. Одним словом, функции Bash работают так же, как и в других языках программирования.
Синтаксис создания функции очень прост:
Имя функции не должно совпадать ни с одной из существующих команд или функций, а все команды в теле функции пишутся с новой строки.
Простая функция
Давайте напишем небольшую функцию, которая будет выводить строку на экран:
Вызов функции bash выполняется указанием ее имени, как для любой другой команды. Запустите наш скрипт на выполнение, не забывайте, что перед этим нужно дать ему права на выполнение:
chmod u+x function.sh
Все работает, теперь усложним задачу, попробуем передать функции аргументы.
Аргументы функции
Аргументы функции нужно передавать при вызове, а читаются они точно так же, как и аргументы скрипта. Синтаксис вызова функции с параметрами bash такой:
имя_функции аргумент1 аргумент2 . аргументN
Как видите, все достаточно просто. Параметры разделяются пробелом. Теперь улучшим нашу функцию, чтобы она выводила заданную нами строку:
!/bin/bash
printstr() echo $1
>
printstr "Hello world"
Можно сделать, чтобы параметров было несколько:
!/bin/bash
printstr() echo $1
echo $2
echo $3
echo $5
>
printstr "arg1" "arg2" "arg3" "arg4" "arg5"
Есть и другой способ извлекать аргументы, как в Си, с помощью стека. Мы извлекаем первый аргумент, затем сдвигаем указатель стека аргументов на единицу и снова извлекаем первый аргумент. И так далее:
!/bin/bash
printstr() echo $1
shift
echo $1
shift
echo $1
shift
echo $1
>
printstr "arg1" "arg2" "arg3" "arg4"
Возврат результата функции
Вы можете не только использовать функции с параметрами bash, но и получить от нее результат работы. Для этого используется команда return. Она завершает функцию и возвращает числовое значение кода возврата. Он может быть от 0 до 255:
!/bin/bash
printstr() return 134;
>
printstr
echo $?
Если вам нужно применить возврат значения функции bash, а не статус код, используйте echo. Строка не сразу выводится в терминал, а возвращается в качестве результата функции и ее можно записать в переменную, а затем использовать:
!/bin/bash
printstr() echo "test"
>
VAR=$(printstr)
echo $VAR
Экспорт функций
!/bin/bash
printstr() echo "hello world"
>
declare -x -f printstr
Затем запустите скрипт с помощью команды source:
source function.sh
$ printstr
Рекурсия
Вы можете вызвать функцию из нее же самой, чтобы сделать рекурсию:
!/bin/bash
printstr() echo "hello world"
printstr
>
printstr
Вы можете поэкспериментировать с использованием рекурсии, во многих случаях это может быть полезным, только не забывайте делать первый вызов функции Bash.
Локальные переменные в функции
Если вы объявите обычную переменную в функции, то она будет доступной во всем скрипте, это удобно для возврата значения функции, но иногда может понадобиться сделать локальную переменную. Для этого существует команда local:
!/bin/bash
printstr() local VAR=$1
echo $
>
printstr "Hello World"
Библиотеки функций
Мы можем взять некоторые функции bash и объединить их в одну библиотеку, чтобы иметь возможность одной командой импортировать эти функции. Это делается похожим образом на экспорт функций. Сначала создадим файл библиотеки:
test1() echo "Hello World from 1";
>
test2() echo "Hello World from 2";
>
test3() echo "Hello World from 3";
>
Теперь создадим скрипт, который будет использовать наши функции. Импортировать библиотеку можно с помощью команды source или просто указав имя скрипта:
!/bin/bash
source lib.sh
test1
test2
test3
Выводы
В этой статье мы рассмотрели функции bash, как их писать, применять и объединять в библиотеки. Если вы часто пишете скрипты на Bash, то эта информация будет для вас полезной. Вы можете создать свой набор функций, для использования их в каждом скрипте и тем самым облегчить себе работу.
В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.
Рекурсию также можно сравнить с матрёшкой. Первая кукла самая большая, за ней идёт точно такая же кукла, но поменьше. Суть матрёшки состоит в том, что вы можете открывать её и доставать из неё точно такую же куклу, только немного меньше. Такой продолжительный процесс длится до тех пор, пока вы не дойдёте до последней куклы, которая и прервёт цикл. Так выглядит визуальная репрезентация рекурсии.
Да, такой исход вполне возможен. Однако, как и у функции for или while , рекурсию можно прервать условием break , чтобы функция перестала вызывать саму себя.
Вот пример кода того, как можно реализовать функцию обратного отсчёта с использованием рекурсии:
Как прервать рекурсию:
Допустим, у нас имеется функция CountDown , которая принимает аргумент (n) . Чтобы реализовать обратный отсчёт, нам следует повторить последовательность действий, понижающих значение параметра. Создадим условие вида:
Если (n) больше 1 , то вызвать функцию CountDown и вернуться в начало цикла, затем вычесть единицу и снова проверить, выполняется ли условие (n) > 1 .
По умолчанию нам нужно создать базовое условие функции, возвращающее значение true , чтобы предотвратить попадание в бесконечный цикл. Базовым условием функции здесь будет условие о том, что любое значение больше 1 не вызовет прерывание цикла.
Проще говоря, рекурсия делает то же, что и код ниже:
Чтобы правильно описать плюсы и минусы, давайте взглянем на производительность рекурсии.
Плюсы:
- Рекурсивный код снижает время выполнения функции.
Под этим подразумевается, что рекурсии, в сравнении с циклами, тратят меньше времени до завершения функции. Чем меньше строк кода у нас будет, тем быстрее функция будет обрабатывать вызовы внутри себя. Особенно хорошо это проявляется при буферизации данных, что позволяет оптимизировать и ускорить код.
В программировании мемоизация — это метод сохранения результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения программ. — Википедия
И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.
Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.
Минусы:
- Рекурсивные функции занимают много места.
Рекурсивные функции занимают значительный объём памяти во время своего выполнения. Это означает, что при каждом вызове функции в стек будет добавляться новый элемент, который будет занимать место до тех пор, пока функция не завершит работу, найдя ответ, либо пока не дойдёт до выполнения базового условия функции.
- Рекурсивные функции замедляют программу.
Несмотря на то, что уже было сказано про мемоизацию, наш код можно ускорить, если применить циклы for или while . Помимо того, что функция может быть попросту плохо написана, мы также рискуем переполнить стек, что в конечном итоге приведёт к снижению скорости и программным ошибкам.
Стек — это такая структура данных, которая работает по принципу «Last In, First Out» (последним пришёл — первым ушёл). Таким образом, элемент «проталкивается» в стек и добавляется в его конец, а затем «выталкивается» из стека при удалении.
Стеки замечательны тем, что они очень быстрые. Большое «О» этого алгоритма равно O(1). Такая результативность объясняется тем, что при рекурсиях не используются циклы, вместо них используются функции pop() , push() и empty() .
Оба этих метода одинаково эффективны для решения задач, однако выбор одного из них зависит от типа проблемы, поставленной перед вами.
Рекурсии эффективны тогда, когда вы работаете с данными, которые слишком сложны, чтобы пройтись по ним с помощью обычных циклов. Стоит также не забывать о ценности памяти и уменьшении времени, идущем вкупе с рекурсивной функцией, в которой накопилось слишком много элементов.
Циклы так же эффективны в плане скорости и оптимизации, они занимают меньше памяти в стеке и их легче понять, потому что в теле цикла содержится больше информации о том, что происходит внутри.
Рекурсия является одним из наиболее мощных подходов в программировании. С ее помощью можно решать чрезвычайно сложные задачи, печатая при этом невероятно малый объем кода. Тем не менее понимание данного принципа нередко вызывает сложности, поскольку для этого требуется нестандартный взгляд на процесс выполнения команд.
Сложность примеров, описанных в данной статье, будет возрастать постепенно, начиная от самых простых и заканчивая достаточно трудными. При этом каждый из них будет сопровождаться подробной диаграммой:
- Рекурсивный способ мышления.
- Рекуррентные соотношения.
- Мемоизация.
- Стратегия “разделяй и властвуй”.
Рекурсия используется для решения задач, в которых функция вызывает сама себя в рамках собственного определения. В каждой реализации рекурсии должно присутствовать два элемента:
- Заключительный базовый кейс или кейсы, в которых рекурсивный поиск ответа более не производится.
- Набор правил (рекуррентных соотношений), который инициирует очередные циклы рекурсии, сводя таким образом общие кейсы к базовому.
В качест в е примера давайте рассмотрим задачу по выводу развернутого варианта строки. В этом случае на выходе из вводного слова ‘hello’ должно получиться ‘olleh’. Итеративный метод решения этой задачи — применение цикла for и вывод каждого знака, начиная с последнего и заканчивая первым.
В рекурсивном же подходе мы сначала создаем функцию reverseString , получающую интересующую нас строку в качестве параметра. Если длина ввода не равна 0, то такой кейс является базовым или заключительным, и мы выводим последнюю букву, а затем инициируем еще один экземпляр reverseString для той же строки, исключив последнюю букву, поскольку ее мы уже вывели.
Обратите внимание: поскольку функция вызывается изнутри себя, она сама создает цикл for . Кроме того, наличие инструкции if перед вызовом другого экземпляра функции обязательно, в противном случае будет выброшена ошибка RecursionError или RuntimeError , поскольку скрипт не увидит конца бесконечного цикла. Данная ситуация аналогична бесконечному циклу While True .
Давайте посмотрим, как эта рекурсивная функция работает с ‘hello’:
Рекуррентность в более сложных задачах может вызвать трудности при определении двух ее компонентов — рекуррентного соотношения, т.е. соотношения между результатом задачи и результатом ее подзадач и базовым кейсом, представляющим кейс, который можно вычислить напрямую без дополнительных рекурсивных вызовов. Иногда базовые кейсы называются “нижними кейсами”, потому что они являются кейсами, в которых задача уменьшена до наименьшего масштаба.
Рассмотрите в качестве примера треугольник Паскаля, в котором каждое число является суммой двух, находящихся над ним, и который имеет по сторонам единицы. Как можно использовать рекурсию для нахождения значения любого значения в точке (i, j)? Каково будет рекуррентное соотношение и базовый/заключительный кейс?
Рекуррентное соотношение можно выразить следующим уравнением:
Это очевидно, когда смотришь на график треугольника. Еще более примечательно в этой формуле то, что если мы продолжим с ее помощью разбивать любую точку (i, j) на сумму двух других точек, то в итоге неизбежно получим базовый кейс — 1. Треугольник Паскаля начинается с единиц, и из их сумм строится весь сложный паттерн.
Как же нам это реализовать?
Для начала давайте найдем набор правил, чтобы определять, когда выполняется базовый кейс, при котором значение ячейки равняется 1. Обратите внимание, что 1-цы появляются при выполнении одного из двух условий: когда располагаются либо в первом столбце (j=0), либо по диагонали (i=j).
Теперь выполнить реализацию просто. Если условия для базового кейса выполнены, мы возвращаем базовое значение (1). В противном случае мы продолжаем уменьшать задачу до тех пор, пока не достигнем базового кейса, до которого, как мы определили, будет неизбежно разбит любой ввод.
Теперь рекурсия раскрылась для вас во всей красе. Здесь, с помощью всего пяти строк кода, мы, по сути, создаем саморазвивающееся дерево. При желании число строк кода можно даже уменьшить до трех. Вызывая функцию pascal дважды, мы инициируем две ветви поиска, каждая из которых также инициирует еще две, предполагая, что базовый кейс достигнут не был.
Такая эффективность рекурсии может показаться магической и даже может запутать. Давайте рассмотрим работу ее алгоритма на примере.
В соответствии с нашим рекуррентным соотношением (4, 2) разбивается на (3, 1) и (3, 2), которые являются двумя числами, стоящими над ней. Обратите внимание, что алгоритм на деле не знает, что значения этих ячеек представлены 3. Он просто учитывает их местоположение. Мы не знаем или даже не интересуемся никакими значениями, пока выполняются базовые условия. На основе базовых кейсов (1) мы можем вычислить другие не базовые точки, но для начала должны быть найдены все базовые.
Согласно нашему рекуррентному соотношению, кейсы итеративно разбиваются до тех пор, пока не достигается базовый (j = 0 или i = j). Поскольку нам известны значения этих базовых кейсов (1), мы можем заполнить и другие значения, зависимые от базового кейса.
Это, конечно же, очень, а возможно и чересчур подробное представление принципа работы рекурсивного алгоритма. В действительности ни один из этих трех шагов не нужно программировать, так как они выполняются скриптом автоматически. Все, что вам нужно, — это вызвать функцию внутри ее самой и обеспечить ее завершение в некоторых точках при достижении базового случая.
При вызове return pascal(i-1, j) + pascal(i-1, j-1) мы рассматриваем возврат не как процесс, а как число. Поскольку pascal(i-1, j) инициирует собственные процессы ветвления, а в итоге возвращает другое число (например, 3), будет правильным воспринимать его именно как число, а не как процесс, что может вызвать ненужную сложность и затруднение в понимании.
Возьмите в качестве примера последовательность Фибоначчи, в которой первые два числа представлены 0 и 1, а последующие числа являются суммой двух, им предшествующих. На основе уже сформированного знания мы понимаем, что базовыми кейсами здесь будут 0 и 1, а рекуррентное соотношение будет выглядеть как v(i) = v(i-2) + v(i-1). В таком случае мы можем построить простую рекурсивную функцию для нахождения значения последовательности Фибоначчи в любом индексе, начиная с 0.
Обратите внимание, что хоть это и грамотное применение рекурсии, оно весьма неэффективно. 8 разбивается на 3 и 5, а 5, в свою очередь, разбивается на 3 и 2. Мы вычисляем все с самого начала и строим завершенное дерево поиска со множеством повторений.
С помощью мемоизации мы можем решить эту проблему, создав кэш. Это можно реализовать, используя словарь и сохраняя значения, заданные ранее. Например, когда индекс 6 (значение 8) разбивается на индекс 4 и индекс 5 (значения 3 и 5), мы можем сохранить значение индекса 4 в кэше. При вычислении индекса 5 как индекса 3 плюс индекс 4 мы можем извлечь индекс 4 из кэша вместо того, чтобы повторно вычислять его, создавая еще одно обширное дерево, ведущее к базовым кейсам.
Чтобы включить в нашу функцию мемоизацию, мы добавим две функциональности: во-первых, если текущий индекс был сохранен в кэше, мы будем просто возвращать его сохраненное значение; во-вторых, прежде чем продолжать уменьшать значение, мы будем добавлять это значение к кэшу,чтобы ускорить дальнейшие операции. Обратите внимание, что кэш должен быть либо глобальной переменной, либо такой, которую можно извлечь и изменить независимо от области вызова команды.
После добавления мемоизации наша рекурсивная функция стала намного быстрее и мощнее.
Рекурсия занимает центральное место среди многих наибыстрейших алгоритмов сортировки. Цель этих алгоритмов — получить список чисел и вернуть их в порядке от меньшего к большему. Поскольку очень много приложений опираются на быструю сортировку, весьма важно найти такой, который сможет сортировать списки максимально быстро. При этом некоторые из самых быстрых алгоритмов используют рекурсивный подход, называемый “разделяй и властвуй”.
В стратегии “разделяй и властвуй” изначальная задача рекурсивно разбивается на несколько подзадач. После того, как каждая подзадача достигает размера единицы (аналог базового кейса), выявляются их подрешения, которые вновь рекурсивно совмещаются для формирования окончательного решения.
Рассмотрите, к примеру, QuickSort — один из наиболее быстрых алгоритмов сортировки, который при грамотной реализации может выполняться в 2–3 раза быстрее своих соперников и предшественников.
QuickSort начинает выполнение с выбора “опоры”. В простейших реализациях и для наших целей такую опору можно выбрать произвольно. Однако в более специализированных реализациях к ее выбору уже стоит подходить осторожно.
Все элементы со значениями меньше опоры переносятся левее нее, а все, чьи значения больше — правее. Выполнить это можно, пройдя по каждому элементу и переместив те, что меньше опоры, в один список, а те, что больше нее — в другой. Заметьте, что эта операция справляется с задачей только частично.
Процесс сортировки списка на основе его опорной точки называется разделением, так как опора разделяет этот список на два раздела, иначе говоря, на две стороны. Каждый их этих разделов вызывает очередную итерацию разделения сам на себя и так продолжается до тех пор, пока раздел не достигнет базового кейса (1 единицы, просто одного числа)
После достаточного числа рекурсивных вызовов исходный список будет разделен до точки, когда эти вызовы продолжить уже невозможно. В этой точке композиция подрешений выполняется простым составлением их в горизонтальном порядке. Результат такой композиции — отсортированный список.
Обратите внимание, что QuickSort следует многим из перечисленных основ рекурсии, рассмотренных нами ранее, только на более высоком уровне. Рекуррентное соотношение является разделением компонента, а базовый кейс — это разделение размера 1. Начиная с оригинального списка, те же процессы (выбор опоры и разделение) вызываются рекурсивно до тех пор, пока результат не будет состоять только из базовых кейсов.
Читайте также: