Концепция рекурсивной функции Python: учебник по Python для начинающих

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

Что такое рекурсия Python ?

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

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

Давайте подробно рассмотрим рекурсивную функцию, чтобы ясно понять ее работу.

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

Мы знаем, что рекурсивная функция в Python вызывает сама себя, как она определена через самореферентные выражения, т. е. в терминах самой себя. Он продолжает повторять свое поведение до тех пор, пока не будет выполнено определенное условие для возврата значения или результата. Давайте теперь посмотрим на пример, чтобы узнать, как это работает.

Читайте также: Вопросы и ответы на собеседовании по Python

Предположим, вы хотите узнать факториал целого числа. Факториал — это не что иное, как произведение всех чисел, начиная с 1 и заканчивая этим целым числом. Например, факториал числа 5 (записанного как 5!) будет равен 1*2*3*4*5*6, то есть 720. У нас есть рекурсивная функция calc_factorial(x), которая определяется следующим образом:

определение calc_factorial(x):

#Рекурсивная функция для нахождения факториала целого числа

если х == 1:

вернуть 1

еще

возврат (x * calc_factorial (x-1))

Что произойдет, если вы вызовете эту функцию с положительным целым числом, например 4? Ну, каждый вызов функции будет добавлять кадр стека, пока мы не достигнем базового случая (когда число уменьшится до 1). Базовое условие требуется для того, чтобы рекурсия заканчивалась и не продолжалась бесконечно. Итак, в данном случае после четвертого вызова будет возвращено значение 24.

Реализация рекурсивной функции в Python

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

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

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

Читайте: Зарплата разработчиков Python в Индии

Поддержание состояния

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

Например, если вы используете рекурсию для вычисления 1+2+3+4+…….+10. Здесь текущее число, которое вы добавляете, и сумма, накопленная до этой точки, формирует состояние, которое вам нужно поддерживать. Поддержание состояния включает передачу обновленного текущего состояния в качестве аргументов при каждом вызове. Вот как вы можете это сделать.

def sum_numbers (текущее_число, накопленная_сумма)

#Базовый вариант

#Вернуть конечное состояние

если текущий номер == 11:

возврат накопленной_суммы

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

#Пропустить состояние через рекурсивный вызов

Еще:

возврат суммы_числа (текущее_число + 1, накопленная_сумма + текущее_число)

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

текущее_число = 1

накопленная_сумма = 0

определение сумма_числа():

глобальный текущий_номер

глобальная накопленная_сумма

#Базовый вариант

если текущее_число==11

возврат накопленной_суммы

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

еще:

накопленная_сумма = накопленная_сумма + текущее_число

текущий_номер = текущий_номер + 1

вернуть число_суммы ()

Рекурсивные структуры данных

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

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

Рекурсия в вычислениях Фибоначчи

Итальянский математик Фибоначчи впервые определил числа Фибоначчи в 13 веке, чтобы смоделировать рост популяции кроликов. Он пришел к выводу, что, начиная с одной пары кроликов в первый год, количество пар кроликов, родившихся в данном году, равно количеству пар кроликов, родившихся в каждый из последних двух лет. Это можно записать как: Fn = Fn-1 + Fn-2 (базовые случаи: F0=1 и F1=1).

Когда вы пишете рекурсивную функцию для вычисления числа Фибоначчи, это может привести к наивной рекурсии. Это происходит, когда определение рекурсивной функции наивно соблюдается, и вы в конечном итоге пересчитываете значения без необходимости. Чтобы избежать пересчета, вы можете применить декоратор lru_cache к функции. Он кэширует результаты и предотвращает неэффективность процесса.

Подробнее: 10 лучших инструментов Python, которые должен знать каждый разработчик Python

Плюсы и минусы рекурсии

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

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

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

Если вам интересно узнать о науке о данных, ознакомьтесь с дипломом IIIT-B & upGrad PG в области науки о данных, который создан для работающих профессионалов и предлагает более 10 тематических исследований и проектов, практические семинары, наставничество с отраслевыми экспертами, 1- on-1 с отраслевыми наставниками, более 400 часов обучения и помощи в трудоустройстве в ведущих фирмах.