Содержание

Как работает рекурсия функции — на примере Python

Итак, сегодня у нас не самая простая, но очень важная тема для тех, кто выбрал программирование как сферу деятельности. И в частности планирует или уже работает с языком программирования Python. 

Речь идет о рекурсии функции!

Мы постараемся объяснить ее максимально простыми и понятными словами, чтобы даже новички могли на базовом уровне понять, что это, как работает и зачем используется.

Настоятельно рекомендуем статью к ознакомлению тем, кто выбрал для себя курс Wezom Академии «Основы Python с нуля до функционального проекта» и хочет глубже погрузиться в тему. Поэтому давайте без лишних предисловий приступим к рассмотрению.

Что такое рекурсия: быстрое напоминание

В программировании рекурсивной функцией называют ту функцию, которая способна вызывать себя из себя же, но с иными значениями параметров. Пока, возможно, сложно для понимания, поэтому давайте попытаемся рассмотреть эту тему на более простых и «бытовых» примерах.

Для начала предлагаем вам взглянуть на лист папоротника:

Что вы видите?

Есть одна большая ветка. По всей ее длине выходят такие же ветки, но меньшего размера. А из каждой такой ветки — еще меньшие ветки с очень похожей структурой. То есть, если представить большую ветку как функцию, мы увидим, что из нее выходят другие похожие функции, но с иными параметрами. В нашем случае — меньшего размера.

Еще один похожий пример — капуста романеско:

Вообще в природе таких примеров огромное множество. Даже ветки деревьев в некотором смысле можно сравнить с рекурсией функции. Также рекурсия нередко встречается в архитектуре, живописи, музыке и в других направлениях искусства. Рекурсия — это порядок и хаос одновременно.

Но как вообще листья папоротника или капуста романеско вяжется с программированием? Давайте разбираться!

Что такое рекурсия функции

Как мы и сказали, рекурсивная функция — это функция, которая вызывает саму себя.

Посмотрим на более «житейском» примере, как это может работать в программировании.

Представьте, что вам нужно попасть в гардеробную, которая закрыта на ключ. Рядом с гардеробной стоит коробка, на которой написано, что ключ внутри. Вы открываете коробку, а внутри лежат еще коробки. А в них — еще. Как вам действовать, чтобы максимально быстро найти нужную коробку с ключом?

По большому счету есть два алгоритма действий:

В первом случае применяется цикл while. То есть, вы берете коробку, открываете ее, затем следующую и так до того самого момента, пока не найдете нужную вам коробку с ключом. Это так называемый итерационный (пошаговый) метод. В Python он может выглядеть следующим образом:

Так как у нас стоит задача с повторяющимися действиями, но меняющимися параметрами, мы можем использовать рекурсивный метод. То есть, решить задачу, используя ее же саму:

В этом примере summa(1) — это 1, summa(2) — это 2 + summa(1) и так далее. Данный алгоритм проще будет понять на следующей схеме:

И тут необходимо указать важную деталь. По большому счету оба алгоритма выполняют одну и ту же задачу — ищут «коробку с ключом». Более того, в данном случае у рекурсивного метода не будет особенного преимущества над итерационным. Однако рекурсия функции гораздо лучше подходит для решения сложных многоуровневых задач. Это будет быстрее, проще и понятнее. Но что еще важнее — рекурсивные решения проще поддерживать.

Условия рекурсивных алгоритмов

Продолжим рассматривать наш пример с summa(n). Есть два важнейших требования, без соблюдения которых алгоритм не будет работать:

  • Базовый случай

Обязательно необходимо задать четкое стоп-условие, которое остановит процесс и не даст ему выполняться бесконечно. То есть, такое стоп-условие помогает функции завершить работу. Это и называется базовым случаем в программировании. В нашем случае функция будет вызывать себя до тех пор, пока не найдет «коробку с ключом». Чем больше функция сделает при этом вызовов, тем больше глубина рекурсии.

  • Рекурсия

Чтобы базовый случай в принципе состоялся, требуется передача измененных данных каждой новой вызванной функции. В нашем примере первый вызов n = 5, второй — 4 и так далее. И только когда n становится равным 1, рекурсия завершается.

Как работают рекурсивные алгоритмы

Что ж, теперь предлагаем немного отойти от наших бытовых примеров и переключиться непосредственно на программирование с Python. 

Итак, есть «материнская» функция и «дочерняя». В тот момент, когда функция вызывает сама себя, действие «материнской» останавливается, а вместо нее начинается выполнение «дочерней».

Рассмотрим рекурсивную функцию на примере summa(5). В компьютере хранятся данные о функции в виде блока, в котором в свою очередь установлено значение переменной n и код, который выполняется. Наглядно это выглядит следующим образом:

При выполнении функции summa(5) начинает вызывать summa(4). В это же время формируется новый блок и размещается над предыдущим: 

Так продолжается до тех пор, пока работает рекурсия функции. При этом как только начинает работать новый блок, остальные никак не задействуются и просто хранят имеющиеся данные. И так продолжается до того момента, когда рекурсия достигает базового случая:

Далее summa(1) возвращает единицу, завершает работу и выходит из стека. В верхней части остается summa(2):

Теперь уже summa(2) продолжает выполнение с того момента, на котором остановилась. За ней — summa(3) и так далее до самого завершения стека.

Вот тут, к слову, и кроется один важный недостаток (или скорее особенность) рекурсии функции в программировании. Дело в том, что пока рекурсивные функции выполняются, они хранят данные всех незавершенных функций, вследствие чего потребление памяти повышается.

И здесь важно вспомнить об особенности Python — ограничение стека в 1 000 вызовов. Если количество вызовов окажется больше, а вы попытаетесь добавить еще одну функцию, то получите соответствующую ошибку — «Переполнение стека». Об этом ограничении очень важно помнить, если вы работаете с Python в целом и с рекурсией функции в частности.

Зачем рекурсия нужна

Вот тут у вас может возникнуть логичный вопрос: «А нужно ли вообще использовать рекурсию функции в Python, если по сути того же результата можно достичь и итеративными алгоритмами?». Вопрос абсолютно резонный!

В некоторых ситуациях циклы действительно оказываются проще и даже эффективнее рекурсии. При этом они тоже вполне могут работать с рекурсивными структурами данных. Более того, часто рекурсивные функции требуют больше места и памяти, нежели итеративные, ведь они постоянно добавляют новые слои в стек памяти. Однако есть нюанс — производительность рекурсивных функций на порядок выше.

Но!

На освоение рекурсивных функций требуется время и определенные усилия. И далеко не всегда удается их правильно реализовать. А некорректная реализация часто делает рекурсию довольно медленной по причине того, что вычисления производятся чаще, чем это на самом деле необходимо. Поэтому очень важно начинать практиковаться в реализации рекурсивных функций с максимально простых и даже примитивных задач, постепенно повышая сложность и вложенность.

С другой стороны, написание итеративных функций — это в большинстве случаев более громоздкий и сложный код. Взгляните, как выглядит итеративная функция для вычисления факториала (числа, умноженного на предыдущее число):

А вот так выглядит рекурсивная функция:

Разница очевидна, не так ли?

Продвинутый взгляд на рекурсию. Подробная трактовка рекурсии и ее… | by Дмитрий ПереводIT | NOP::Nuances of Programming

Дмитрий ПереводIT

·

Follow

Published in

·

8 min read

·

Sep 19, 2020

Рекурсия является одним из наиболее мощных подходов в программировании. С ее помощью можно решать чрезвычайно сложные задачи, печатая при этом невероятно малый объем кода. Тем не менее понимание данного принципа нередко вызывает сложности, поскольку для этого требуется нестандартный взгляд на процесс выполнения команд.

Сложность примеров, описанных в данной статье, будет возрастать постепенно, начиная от самых простых и заканчивая достаточно трудными. При этом каждый из них будет сопровождаться подробной диаграммой:

  • Рекурсивный способ мышления.
  • Рекуррентные соотношения.
  • Мемоизация.
  • Стратегия “разделяй и властвуй”.

Рекурсия используется для решения задач, в которых функция вызывает сама себя в рамках собственного определения. В каждой реализации рекурсии должно присутствовать два элемента:

  • Заключительный базовый кейс или кейсы, в которых рекурсивный поиск ответа более не производится.
  • Набор правил (рекуррентных соотношений), который инициирует очередные циклы рекурсии, сводя таким образом общие кейсы к базовому.

В качестве примера давайте рассмотрим задачу по выводу развернутого варианта строки. В этом случае на выходе из вводного слова ‘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), будет правильным воспринимать его именно как число, а не как процесс, что может вызвать ненужную сложность и затруднение в понимании.

С некоторой точки зрения этот рекурсивный алгоритм можно назвать неэффективным. В конце концов ‘6′ разбивается на ‘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. Начиная с оригинального списка, те же процессы (выбор опоры и разделение) вызываются рекурсивно до тех пор, пока результат не будет состоять только из базовых кейсов.

  • Рекурсия — это подход программирования, в котором функция вызывает сама себя, допуская использование циклов и автоматическое построение дерева при минимальном количестве кода.
  • При построении рекурсивной функции нужно четко понимать два ее основных элемента: рекуррентное соотношение и базовый кейс.
  • Мемоизация — это метод, используемый для предотвращения повторения операций, работающий посредством сохранения информации в кэше с последующим ее извлечением при необходимости.
  • Стратегия “разделяй и властвуй” — это одно из многих применений рекурсии, в котором задача рекурсивно разбивается на несколько подзадач (базовых кейсов), из которых можно с легкостью извлечь подрешения и агрегировать их в полноценное решение.

Читайте также:

  • Почему в базе данных происходит взаимоблокировка?
  • Слабо контролируемое обнаружение объектов — сквозной цикл обучения
  • Выбор оптимального алгоритма поиска в Python

Читайте нас в Telegram, VK и Яндекс.Дзен

Перевод статьи Andre Ye: Advanced Concepts in Recursion Every Effective Programmer Should Know

haskell. Является ли функция, которая вызывает себя только один раз независимо от рекурсивного ввода?

спросил

Изменено 3 года, 11 месяцев назад

Просмотрено 516 раз

Рассмотрим функцию, которая выполняет операцию и вызывает себя не более одного раза (не более одного «уровня рекурсии») независимо от входных данных. Эта функция считается рекурсивной?

Пример:

 join1 :: [Возможно a] -> [a]
join1 [Просто х] = [х]
join1 [Ничего] = []
join1 (x) = concat (карта join1 (карта (\k->
 
[k]) x))

В этом случае при звонке: Join1 [ничего, только 2, всего 3,…] Функция join1 будет вызываться для каждого элемента, немедленно вводя условие завершения

  • haskell
  • recursion
10

Да, это рекурсия. Количество вызовов во время выполнения и глубина рекурсии во время выполнения не имеют значения. Определение x = выражение называется рекурсивным, если x появляется в выражении , ссылаясь на x , которое мы определяем прямо сейчас.

Короче говоря, «рекурсивность» является синтаксическим свойством определения и не учитывает поведение во время выполнения.

В качестве глупого примера, это определение является рекурсивным, даже если оно никогда не вызывает себя во время выполнения. Даже если бы его можно было банально упростить до нерекурсивного.

 тождество :: а -> а
тождество х = (\_ -> х) тождество
5

Вы недооценили допустимые входные данные для своей функции. Что, если вы назовете это так:

 join1 [Ничего, Просто [Просто 2, Ничего, Всего 3], Просто [Ничего, Всего 4]]

Или наоборот, что, если вы назовете это так:

 join1 [Ничего]

Небесконечные рекурсивные вызовы функций всегда ограничены по глубине. Вызов самого себя один или даже ноль раз для любого конкретного ввода вполне допустим. Фактически, он не завершится, если вы не разрешите ввод с нулевыми рекурсивными вызовами.

Зарегистрируйтесь или войдите в систему

Зарегистрируйтесь с помощью Google

Зарегистрироваться через Facebook

Зарегистрируйтесь, используя электронную почту и пароль

Опубликовать как гость

Электронная почта

Требуется, но не отображается

Опубликовать как гость

Электронная почта

Требуется, но не отображается

Нажимая «Опубликовать свой ответ», вы соглашаетесь с нашими условиями обслуживания и подтверждаете, что прочитали и поняли нашу политику конфиденциальности и кодекс поведения.

функция, которая вызывает сама себя, называется ___ функцией – Whyasef.stress.org.uk

Опубликовано 25 июля 2023 г.

Как вы называете функцию, которая вызывает сама себя?0005

Функции — JavaScript | MDN — MDN Web Docs

Функции — JavaScript | MDN — MDN Web Docs

developer.mozilla.org › JavaScript › GuideFunctions — JavaScript | MDN — MDN Web Docs developer.mozilla.org › JavaScript › Guide CachedОпределение функций. Объявления функций. Определение функции (также называемое объявлением функции или оператором функции) состоит из ключевого слова function, за которым следует Calling functions. Определение функции не выполняет ее. Его определение дает имя функции и указывает, что делать при вызове функции. Вызов функции фактически выполняет указанные действия с указанными параметрами. Объем функции. К переменным, определенным внутри функции, нельзя получить доступ откуда-либо за пределами функции, потому что переменная определена только в области действия функции. Область видимости и стек функций. Рекурсия. Функция может ссылаться и вызывать себя. Функция может ссылаться на себя тремя способами. Имя функции. Продолжить чтение…

C-функции MCQ (вопросы с несколькими вариантами ответов) – Algbly

Просмотреть ответ 3. Функция, которая вызывает сама себя, называется ___ функцией. a) Автофункция b) Автофункция c) Рекурсивная функция d) Представление статической функции Ответ 4. Ключевое слово, используемое для передачи управления от функции обратно к вызывающей функции, — int **a; a) switch b) goto c) вернуться d) return Просмотреть ответ 5. Продолжить чтение…

C++ — Вызов функции внутри того же определения функции

Функция, вызывающая саму себя, известна как рекурсивная функция. Это работает, потому что компилятору нужно только объявление функции, а не ее определение, чтобы вы могли ее вызвать. Первая строка определения также служит объявлением. (Подробности см. в § 8.4.1.2 стандарта C++11.) Рекурсия хорошо подходит для решения многих проблем. Продолжить чтение…

Карточки с викторинами по Разделу 13 | Quizlet

алгоритм. Пошаговая серия операций, используемых для выполнения вычислений, обработки данных или автоматизации задач рассуждения, известна как. отложенное действие. Каждый вызов рекурсивной функции известен как. добавляет вызов функции в стек. Каждый раз, когда функция вызывает себя Python. Продолжить чтение…

COSC 1436 — Ch 12 Flashcards | Quizlet

Test Match Создано lolita_applebum Условия в этом наборе (14) 1. Рекурсивная функция ______. а. вызывает другую функцию b. аварийно останавливает программу c. называет себя д. может быть вызван только один раз c. вызывает себя 2. Функция вызывается один раз из основной функции программы, а затем она вызывает себя четыре раза. Глубина рекурсии ______. Продолжить чтение…

Решено Функция, которая вызывает сама себя, называется — McqMate

Обсуждение, связанное с вопросами с множественным выбором Алгоритм, который прямо или косвенно вызывает саму себя, известен как Если функция объявлена ​​как void fn (int *p), то какое из следующих утверждений допустимо для вызова функции fn? Ключевое слово, используемое для передачи управления от функции обратно к вызывающей функции: Продолжить чтение.

No related posts.