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

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

Отдельно остановимся на рекурсивных функциях. Рекурсивная функция представляет такую конструкцию, при которой функция вызывает саму себя.

Рекурсивная функция факториала

Возьмем, к примеру, вычисление факториала, которое использует формулу n! = 1 * 2 * … * n . То есть по сути для нахождения факториала числа мы перемножаем все числа до этого числа. Например, факториал числа 4 равен 24 = 1 * 2 * 3 * 4 , а факторил числа 5 равен 120 = 1 * 2 * 3 * 4 * 5 .

Определим метод для нахождения факториала:

int Factorial(int n)

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

На уровне языка программирования для возвращения базового варианта применяется оператор return :

if (n == 1) return 1;

То есть, если вводимое число равно 1, то возвращается 1

Другая особенность рекурсивных функций: все рекурсивные вызовы должны обращаться к подфункциям, которые в конце концов сходятся к базовому варианту:

return n * Factorial(n - 1);

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

Используем эту функцию:

int Factorial(int n) < if (n == 1) return 1; return n * Factorial(n - 1); >int factorial4 = Factorial(4); // 24 int factorial5 = Factorial(5); // 120 int factorial6 = Factorial(6); // 720 Console.WriteLine($"Факториал числа 4 = "); Console.WriteLine($"Факториал числа 5 = "); Console.WriteLine($"Факториал числа 6 = ");

Рассмотрим поэтапно, что будет в случае вызова Factorial(4) .

Сначала идет проверка, равно ли число единице:

if (n == 1) return 1;

Но вначале n равно 4, поэтому это условие ложно, и соответственно выполняется код

return n * Factorial(n - 1);

То есть фактически мы имеем:

return 4 * Factorial(3);

Factorial(3)

Опять же n не равно 1, поэтому выполняется код

return n * Factorial(n - 1);

То есть фактически:

return 3 * Factorial(2);

Factorial(2)

Опять же n не равно 1, поэтому выполняется код

return n * Factorial(n - 1);

То есть фактически:

return 2 * Factorial(1);

Factorial(1)

Теперь n равно 1, поэтому выполняется код

if (n == 1) return 1;

В итоге выражение

Factorial(4)

В реальности выливается в

4 * 3 * 2 * Factorial(1)

Рекурсивная функция Фибоначчи

Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. То есть последовательность Фибоначчи будет выглядеть так 0 (0-й член), 1 (1-й член), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . Для определения чисел этой последовательности определим следующий метод:

int Fibonachi(int n) < if (n == 0 || n == 1) return n; return Fibonachi(n - 1) + Fibonachi(n - 2); >int fib4 = Fibonachi(4); int fib5 = Fibonachi(5); int fib6 = Fibonachi(6); Console.WriteLine($"4 число Фибоначчи = "); Console.WriteLine($"5 число Фибоначчи = "); Console.WriteLine($"6 число Фибоначчи = ");

Здесь базовый вариант выглядит следующий образом:

if (n == 0 || n == 1) return n;

То есть, если мы ищем нулевой или первый элемент последовательности, то возвращается это же число — 0 или 1. Иначе возвращается результат выражения Fibonachi(n — 1) + Fibonachi(n — 2);

Рекурсии и циклы

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

static int Fibonachi2(int n) < int result = 0; int b = 1; int tmp; for (int i = 0; i < n; i++) < tmp = result; result = b; b += tmp; >return result; >

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

Как работает рекурсия – объяснение в блок-схемах и видео

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works — explained with flowcharts and a video.

«Для того чтобы понять рекурсию, надо сначала понять рекурсию»

Рекурсию порой сложно понять, особенно новичкам в программировании. Если говорить просто, то рекурсия – это функция, которая сама вызывает себя. Но давайте попробую объяснить на примере.

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

Вы открываете коробку только чтобы найти… еще больше коробок. Коробки внутри коробок и вы не знаете, в какой из них Ваш ключ. Вам срочно нужна рубашка, так что вам надо придумать хороший алгоритм и найти ключ.

Есть два основных подхода в создании алгоритма для решения данной проблемы: итеративный и рекурсивный. Вот блок-схемы этих подходов:

Какой подход для Вас проще?

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

function look_for_key(main_box) < let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) < box = pile.grab_a_box(); for (item in box) < if (item.is_a_box()) < pile.append(item) >else if (item.is_a_key()) < console.log("found the key!") >> > >

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

function look_for_key(box) < for (item in box) < if (item.is_a_box()) < look_for_key(item); >else if (item.is_a_key()) < console.log("found the key!") >> >

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

Поскольку рекурсия используется во многих алгоритмах, очень важно понять как она работает. Если рекурсия до сих пор не кажется Вам простой, не беспокойтесь: Я собираюсь пройтись еще по нескольким примерам.

Граничный и рекурсивный случай

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

// WARNING: This function contains an infinite loop! function countdown(i) < console.log(i) countdown(i - 1) >countdown(5); // This is the initial call to the function.

Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)

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

И снова функция подсчета, только уже с граничным случаем:

function countdown(i) < console.log(i) if (i else < // recursive case countdown(i - 1) >> countdown(5); // This is the initial call to the function.

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

Сначала мы выведем цифру 5, используя команду Console.Log. Т.к. 5 не меньше или равно 1, то мы перейдем в блок else. Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).

Мы выведем цифру 4. И снова i не меньше или равно 1, так что мы переходим в блок else и передаем цифру 3. Это продолжается, пока i не станет равным 1. И когда это случится мы выведем в консоль 1 и i станет меньше или равно 1. Наконец мы зайдем в блок с ключевым словом return и выйдем из функции.

Стек вызовов

Рекурсивные функции используют так называемый «Стек вызовов». Когда программа вызывает функцию, функция отправляется на верх стека вызовов. Это похоже на стопку книг, вы добавляете одну вещь за одни раз. Затем, когда вы готовы снять что-то обратно, вы всегда снимаете верхний элемент.

Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1. Вот рекурсивная функция для подсчета факториала числа:

function fact(x) < if (x == 1) < return 1; >else < return x * fact(x-1); >> 

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

Заметили, как каждое обращение к функции fact содержит свою собственную копию x. Это очень важное условие для работы рекурсии. Вы не можете получить доступ к другой копии функции от x.

Нашли уже ключ?

Давайте кратенько вернемся к первоначальному примеру поиска ключа в коробках. Помните, что первым был итеративный подход с использованием циклов? Согласно этому подходу Вы создаете стопку коробок для поиска, поэтому всегда знаете в каких коробках вы еще не искали.

Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!

И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!

Вы также можете посмотреть мое пятиминутное видео про рекурсию. Оно должно усилить понимание, приведенных здесь концепций.

Заключение от автора

Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием «Algorithms in Motion». И курс и статься написаны по замечательной книге «Grokking Algorithms», автором которой является Adit Bhargava, кем и были нарисованы все эти замечательные иллюстрации.

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

От себя хочу добавить, что с интересом наблюдаю за статьями и видеоуроками Beau Carnes, и надеюсь что Вам тоже понравилась статья и в особенности эти действительно замечательные иллюстрации из книги A. Bhargav «Grokking Algorithms».

• рекурсия
• алгоритмы
• обучение программированию
• образование
• javascript
• перевод

Рекурсия

Рекурсия (recursion) — это поведение функции, при котором она вызывает сама себя. Такие функции называются рекурсивными. В отличие от цикла, они не просто повторяются несколько раз, а работают «внутри» друг друга.

Известная шутка гласит: «Чтобы понять рекурсию, надо понять рекурсию».

«IT-специалист с нуля» наш лучший курс для старта в IT

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

Это работает так: функция A от единицы запускает функцию A от двойки, та — от тройки, и так далее, пока не будет высчитано нужное значение. Чтобы рекурсивный вызов закончился, нужно сразу прописать в функции A условие выхода из рекурсии: например, если получено какое-то значение, нужно не запускать функцию заново, а вернуть некоторый результат.

Если не прописать условие выхода, рекурсия будет бесконечной. А пока условие выхода не достигнуто, все вызванные экземпляры функции A будут работать одновременно — один вкладывает другой в себя.

Поддержка рекурсивного вызова есть практически во всех современных языках программирования.

Профессия / 8 месяцев
IT-специалист с нуля

Попробуйте 9 профессий за 2 месяца и выберите подходящую вам

Кто пользуется рекурсией и зачем она нужна

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

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

Рекурсию можно встретить и в других отраслях: физике, биологии, лингвистике и даже архитектуре. Например, фрактальные формы вроде листа папоротника или снежинки — рекурсивные. Вложенные предложения — тоже. А самый наглядный вид рекурсии — два поставленных друг напротив друга зеркала.

Программисты пользуются рекурсией и ради забавы. Например, известная аббревиатура GNU расшифровывается как GNU is Not Unix – первая буква скрывает под собой ту же аббревиатуру. Это тоже рекурсия.

Отличия рекурсии от цикла

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

• в цикле новые функции не вызываются внутри вызванных ранее;
• рекурсия же — это функция, вызывающая сама себя с другими аргументами.

Простыми словами: инструкция с пунктом «Вернись к пункту 1» — это цикл, инструкция с пунктом «Прочитай инструкцию заново» — рекурсия.

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

Прерывание рекурсии

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

Обычно путь выхода — это какое-то условие, которое проверяется в самом начале выполнения функции. Если оно выполняется, функция вызовет себя снова, если нет — выдаст какое-то значение, отдаст его предыдущему «соседу» и закроется.

Например, если n > 1, то вызвать A(n-1). Иначе вернуть 1. Получается, что когда n станет меньше или равен единице, то A не запустится заново — очередной экземпляр просто вернет единицу. Остальные экземпляры получат нужный себе результат и тоже закроются по каскаду. Этот процесс называется обратным ходом рекурсии. А то, что было до него, — прямым ходом.

Количество открытых в итоге функций называется глубиной рекурсии.

Пример рекурсии: расчет чисел Фибоначчи

Известный пример рекурсивных расчетов — числа Фибоначчи. Каждое следующее число в ряду — сумма двух предыдущих, начиная с 1.

Получается так: 1, 1, 2, 3, 5, 8, 13, 21 и так далее. Использование рекурсии здесь — напрашивающийся и интуитивно понятный способ расчета:

• допустим, функция называется fibonacci(n) и рассчитывает n-е по счету число Фибоначчи;
• на первом шаге функция вызывает fibonacci(n-1) и fibonacci(n-2), то есть себя, но с другими аргументами, и складывает получившиеся результаты;
• новые вызовы будут делать то же самое, пока n не дойдет до единицы или нуля — это первое число Фибоначчи, и в таком случае функция вернет 1;
• предыдущий экземпляр функции получит два результата 1 — от единицы и нуля, сложит их и отправит «назад» к более ранним соседям;
• в итоге все вызванные функции получат от своих «потомков» ответ, сложат полученные значения и вернут их самой первой функции fibonacci(n);
• та сложит финальные значения, вернет результат и закроется.

Это только один простой пример; рекурсивных алгоритмов намного больше. Еще один известный — расчет факториала числа.

Курс для новичков «IT-специалист
с нуля» – разберемся, какая профессия вам подходит, и поможем вам ее освоить

Другие примеры рекурсивных расчетов

• Вычисление факториала числа — последовательных умножений на предыдущее число. Например, 3! (факториал от трех) — это 1 * 2 * 3.
• Расчет и изображение фракталов — конструкций, где более мелкие элементы повторяют более крупные. Яркие примеры фракталов — снежинка и лист папоротника.
• Обход ветвящихся структур данных, например графов и деревьев.
• Компьютерный анализ естественного языка, фраз и предложений.
• Поиск пути в лабиринте и построение маршрутов — к примеру, алгоритмы DFS и BFS.
• Вычисления с числовыми рядами, например те же числа Фибоначчи или поиск простых чисел.
• Математические операции, требующие повторяющихся действий с разными значениями, к примеру возведение в степень больше 2, поиск максимума или минимума.
• Операции с системами счисления, к примеру перевод чисел из одной в другую.

За пределами математики и информатики можно вспомнить много других примеров рекурсии: от самовозбуждения электронных схем до сказок «Тысячи и одной ночи».

Прямая и косвенная рекурсия

Рекурсию можно условно разделить на прямую и косвенную.

• Прямая вызывает сама себя напрямую. То есть функция A вызывает функцию A с другими аргументами.
• Косвенная действует через «третью» функцию. Функция A вызывает функцию B, а та в свою очередь снова вызывает функцию A. Это тоже рекурсия, просто менее очевидная.

Еще бывают линейная и каскадная рекурсии. В линейной экземпляр функции вызывает сам себя только один раз, в каскадной — несколько. Например, расчет чисел Фибоначчи — каскадная рекурсия, потому что функция вызывает себя дважды: для n-1 и n-2.

Рекурсивный и итеративный процессы

Одну и ту же рекурсию можно использовать по-разному. Например, есть понятия рекурсивного и итеративного процесса. И там, и там применяется рекурсия, но различается подход к ней.

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

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

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

Преимущества рекурсии

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

Ясность. Прочитать рекурсивный код обычно проще, чем программу, полную ухищрений для решения той же задачи без рекурсии. Это важный плюс, если речь идет о коммерческом программировании, где код часто смотрят другие люди.

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

Краткость. Рекурсивная функция обычно короче, чем реализация без рекурсии. Разработчику проще и удобнее написать несколько строк кода, чем создавать огромную программу, тратить время и силы и путаться в написанном.

Красота. Наконец, сам концепт многие считают красивым и изящным. Это и правда так — посмотрите на фракталы и снежинки: в них есть определенная красота. Рекурсию используют даже в искусстве: от матрешек до сложных узоров, украшающих готические соборы.

Недостатки рекурсии

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

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

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

Чем пользоваться: рекурсией или циклом

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

• Если программе важна высокая скорость работы и низкая нагрузка или существует риск переполнения памяти — лучше выбрать вариант без рекурсии.
• Если скорость не так важна, а реализация без рекурсии отнимет много времени и строк кода — лучше воспользоваться рекурсивным подходом.

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

Как начать работать с рекурсией

Концепт и примеры рекурсивных функций можно найти в любом учебнике по программированию. Обычно начинающим предлагают потренироваться на простых «классических» задачах вроде чисел Фибоначчи или расчета факториала. Затем можно переходить к более сложным заданиям: обход графа, анализ текста или что-либо еще. А какой язык выбрать — зависит от ваших предпочтений и пожеланий к отрасли.

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

IT-специалист с нуля

Наш лучший курс для старта в IT. За 2 месяца вы пробуете себя в девяти разных профессиях: мобильной и веб-разработке, тестировании, аналитике и даже Data Science — выберите подходящую и сразу освойте ее.

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

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

Мемоизация

Если применение рекурсии при решении задачи неизбежно, есть простой способ ускорить выполнение функции – для этого используют декоратор @lru_cache() модуля functools. Сравним скорость выполнения рекурсивного кода при решении следующей олимпиадной задачи.

Задача: лесенка представляет собой набор кубиков. В этом наборе каждый последующий ряд состоит из меньшего числа кубиков, чем предыдущий. Надо написать программу для вычисления количества лесенок, которое можно построить из n кубиков.

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

Пример ввода:

Посещаем узел Анна. Проверяем, состоит ли имя Анна из 9 букв. Посещаем узел Егор. Проверяем, состоит ли имя Егор из 9 букв. Посещаем узел Мария. Проверяем, состоит ли имя Мария из 9 букв. Посещаем узел Светлана. Проверяем, состоит ли имя Светлана из 9 букв. Посещаем узел Инга. Проверяем, состоит ли имя Инга из 9 букв. Посещаем узел Елизавета. Проверяем, состоит ли имя Елизавета из 9 букв. Имя из 9 букв: Елизавета 

root = ]>, , ]>, ]>]> def find_name(node): print(f"Посещаем узел . ") print(f"Проверяем, состоит ли имя из 9 букв. ") if len(node['name']) == 9: return node['name'] # граничный случай if len(node['children']) > 0: # рекурсивный случай for child in node['children']: returnValue = find_name(child) if returnValue != 'не найдено': return returnValue return 'не найдено' # граничный случай - имен из 9 букв нет print(f"Имя из 9 букв: ") 

Примечание: без рекурсии такую задачу можно решить с помощью ООП:

class Node: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right def traverse(root): if root is None: return traverse(root.left) if len(root.data) == 9: print(f'Имя найдено: ') return traverse(root.right) if len(root.data) == 9: print(f'Имя найдено: ') return if __name__ == '__main__': root = Node('Анна') root.left = Node('Егор') root.right = Node('Светлана') root.left.left = Node('Мария') root.right.left = Node('Инга') root.right.right = Node('Марина') root.right.left.left = Node('Елизавета') root.right.left.right = Node('Антон') traverse(root) 

Задание 9

Имеется многомерный вложенный список:

sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]], [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]], [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]], [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]], [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]], ] 

Напишите рекурсивную и итеративную функции для преобразования списка в одномерный.

Ожидаемый результат:

[5, 7, 2, 4, 9, 5, 2, 5, 4, 3, 2, 1, 5, 9, 5, 4, 3, 1, 2, 4, 7, 2, 6, 4, 4, 1, 6, 3, 8, 4, 5, 9, 1, 3, 1, 5, 6, 4, 2, 1, 2, 5, 6, 8, 2, 3, 4, 5, 3, 2, 2, 1, 4, 2, 5, 4, 3, 1, 6, 7, 9, 0, 5, 2, 4, 7, 3, 4, 4, 2, 5, 6, 7, 5, 7, 1, 3, 4, 6, 6, 4, 5] 

Решение 1 – рекурсивное:

def flat_list_recur(lst): if lst == []: return lst if isinstance(lst[0], list): return flat_list_recur(lst[0]) + flat_list_recur(lst[1:]) return lst[:1] + flat_list_recur(lst[1:]) sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]], [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]], [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]], [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]], [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]], ] print(flat_list_recur(sp)) 

Решение 2 – итеративное:

def flat_list_iter(lst): result = [] stack = [lst] while stack: current = stack.pop(-1) if isinstance(current, list): stack.extend(current) else: result.append(current) result.reverse() return result sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]], [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]], [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]], [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]], [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]], ] print(flat_list_iter(sp)) 

Задание 10

Реализуйте алгоритм бинарного поиска с помощью итеративной и рекурсивной функций. Число задается с помощью randrange(2000), в списке хранятся числа от 1 до 1000, т.е. не во всех случаях заданное число будет присутствовать в списке.

Пример вывода:

Число найдено: 787 

Решение 1 – рекурсивное:

from random import randrange def binary_recursive(lst, start, end, num): if end >= start: mid = (end + start) // 2 if lst[mid] == num: # граничный случай - элемент находится посередине return mid elif lst[mid] > num: # рекурсивный случай - элемент находится слева return binary_recursive(lst, start, mid - 1, num) else: # рекурсивный случай - элемент находится справа return binary_recursive(lst, mid + 1, end, num) else: # граничный случай - элемент в списке не обнаружен return 'не найдено' sp = [i for i in range(1001)] n = randrange(2000) result = binary_recursive(sp, 0, len(sp)-1, n) if result != 'не найдено': print(f'Число найдено: ') else: print('Такого числа нет в списке') 

Решение 2 – итеративное:

from random import randrange def binary_iter(lst, num): start, end, mid = 0, len(lst) - 1, 0 while start num: end = mid - 1 else: return mid return 'не найдено' sp = [i for i in range(1001)] n = randrange(2000) result = binary_iter(sp, n) if result != 'не найдено': print(f'Число найдено: ') else: print('Такого числа нет в списке') 

Подведем итоги

Рекурсию стоит применять для решения задач, в которых:

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

Во всех остальных случаях целесообразнее использовать итерацию либо итерацию и стек.

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

1. Особенности, сферы применения, установка, онлайн IDE
2. Все, что нужно для изучения Python с нуля – книги, сайты, каналы и курсы
3. Типы данных: преобразование и базовые операции
4. Методы работы со строками
5. Методы работы со списками и списковыми включениями
6. Методы работы со словарями и генераторами словарей
7. Методы работы с кортежами
8. Методы работы со множествами
9. Особенности цикла for
10. Условный цикл while
11. Функции с позиционными и именованными аргументами
12. Анонимные функции
13. Рекурсивные функции
14. Функции высшего порядка, замыкания и декораторы
15. Методы работы с файлами и файловой системой
16. Регулярные выражения
17. Основы скрапинга и парсинга
18. Основы ООП: инкапсуляция и наследование
19. Основы ООП – абстракция и полиморфизм
20. Графический интерфейс на Tkinter
21. Основы разработки игр на Pygame
22. Основы работы с SQLite
23. Основы веб-разработки на Flask
24. Основы работы с NumPy
25. Основы анализа данных с Pandas