- Рекурсия
- Основы рекурсии в Python
- Примеры использования рекурсии в Python
- Заключение
- Рекурсивная функция в python
- Рекурсивные функции
- Вкратце о факториалах
- Детали работы рекурсивной функции
- Как работает рекурсия
- Рекурсивно или итеративно?
- Вычисление факториала
- Вычисление факториала с помощью циклов
- Нахождение факториала рекурсией
- Функция factorial модуля math
- Вычисление факториала числа с использованием рекурсии
- Решение задачи
- Исходный код
- Объяснение работы программы
- Результаты работы программы
Рекурсия
Рекурсия — это мощный инструмент в программировании, который может быть использован для решения многих задач. В Python, рекурсия может быть использована для вычисления факториала, чисел Фибоначчи, обхода деревьев и многих других задач.
В программировании рекурсия является мощным инструментом, который может использоваться для решения многих задач. Давайте рассмотрим, как использовать рекурсию в Python и как она работает.
Основы рекурсии в Python
Рекурсивная функция должна иметь базовый случай (base case) и рекурсивный случай (recursive case). Базовый случай — это условие, в котором функция не вызывает саму себя, а возвращает значение. Рекурсивный случай — это условие, в котором функция вызывает саму себя.
Например, рекурсивная функция для вычисления факториала может выглядеть так:
# Рекурсивная функция для вычисления факториала числа def factorial(n): # Базовый случай - если n равно 0, то возвращается 1 if n == 0: return 1 # Рекурсивный случай - если n не равно 0, то вызывается функция factorial для n-1 и умножается на n else: return n * factorial(n-1)
Описание функции factorial :
Рекурсивная функция factorial вычисляет факториал числа n . Факториал числа n — это произведение всех целых чисел от 1 до n , включительно. Например, факториал числа 5 равен 1 * 2 * 3 * 4 * 5, т.е. 120.
Функция factorial использует базовый случай n == 0 , чтобы остановить рекурсию. Если n равно 0, то возвращается 1 — это базовый случай. Если n не равно 0, то функция вызывает саму себя, передавая в качестве аргумента n-1 . Это рекурсивный случай. Рекурсия продолжается, пока n не станет равным 0.
Примеры использования рекурсии в Python
Рекурсия может быть использована для решения многих задач. Например, мы можем использовать рекурсию для вычисления чисел Фибоначчи. Числа Фибоначчи — это последовательность чисел, где каждое число равно сумме двух предыдущих чисел. Первые два числа равны 0 и 1. Таким образом, последовательность начинается так: 0, 1, 1, 2, 3, 5, 8, 13 и т.д.
Рекурсивная функция для вычисления чисел Фибоначчи может выглядеть так:
def fibonacci(n): # Базовый случай - если n равно 0, то возвращается 0 if n == 0: return 0 # Базовый случай - если n равно 1, то возвращается 1 elif n == 1: return 1 # Рекурсивный случай - вызов функции fibonacci для n-1 и n-2 и возвращение их суммы else: return fibonacci(n-1) + fibonacci(n-2)
Описание функции fibonacci :
Рекурсивная функция fibonacci вычисляет n-ое число Фибоначчи. Функция использует два базовых случая — когда n равно 0 и когда n равно 1 — для остановки рекурсии. В рекурсивном случае, функция вызывает саму себя для двух предыдущих чисел и возвращает их сумму.
Рекурсия также может быть использована для обхода деревьев. Дерево — это структура данных, которая состоит из узлов и связей между ними. Каждый узел имеет родителя и может иметь несколько дочерних узлов. Обход дерева — это процесс посещения каждого узла дерева ровно один раз.
Рекурсивная функция для обхода дерева может выглядеть так:
def traverse_tree(node): # Базовый случай - если узел равен None, то возвращается None if node is None: return # Рекурсивный случай - вызов функции traverse_tree для левого и правого поддерева traverse_tree(node.left) traverse_tree(node.right)
Описание функции traverse_tree :
Рекурсивная функция traverse_tree обходит дерево, начиная с корневого узла. Функция использует базовый случай node is None , чтобы остановить рекурсию, когда дошли до конца поддерева. В противном случае, функция вызывает себя для левого и правого поддерева.
Заключение
Рекурсия — это один из способов решения задач в программировании. Хотя рекурсия может быть мощным инструментом, ее необходимо использовать с осторожностью и пониманием. Для использования рекурсии в Python необходимо понимать основные принципы рекурсии, а также уметь правильно выбирать базовый и рекурсивный случаи для каждой задачи.
Рекурсивная функция в python
Рекурсию не очень просто понять при первом знакомстве, но без ее понимания в разработке будет тяжело. В этом материале рассмотрим:
- Рекурсивную функцию поиска факториала.
- Как рекурсивные функции работают в коде.
- Действительно ли рекурсивные функции выполняют свои задачи лучше итеративных?
Рекурсивные функции
Рекурсивная функция — это та, которая вызывает сама себя.
В качестве простейшего примера рассмотрите следующий код:
def factorial_recursive(n):
if n == 1:
return n
else:
return n*factorial_recursive(n-1)Вызывая рекурсивную функцию здесь и передавая ей целое число, вы получаете факториал этого числа (n!).
Вкратце о факториалах
Факториал числа — это число, умноженное на каждое предыдущее число вплоть до 1.
Например, факториал числа 7:
7! = 7*6*5*4*3*2*1 = 5040Вывести факториал числа можно с помощью функции:
num = 3
print(f"Факториал это ")Эта функция выведет: «Факториал 3 это 6». Еще раз рассмотрим эту рекурсивную функцию:
def factorial_recursive(n): .
По аналогии с обычной функцией имя рекурсивной указывается после def , а в скобках обозначается параметр n :
def factorial_recursive(n): if n == 1: return n else: return n*factorial_recursive(n-1)
Благодаря условной конструкции переменная n вернется только в том случае, если ее значение будет равно 1. Это еще называют условием завершения. Рекурсия останавливается в момент удовлетворения условиям.
def factorial_recursive(n): if n == 1: return n else: return n*factorial_recursive(n-1)
В коде выше выделен фрагмент самой рекурсии. В блоке else условной конструкции возвращается произведение n и значения этой же функции с параметром n-1 .
Это и есть рекурсия. В нашем примере это так сработало:
3 * (3-1) * ((3-1)-1) # так как 3-1-1 равно 1, рекурсия остановилась
Детали работы рекурсивной функции
Чтобы еще лучше понять, как это работает, разобьем на этапы процесс выполнения функции с параметром 3.
Для этого ниже представим каждый экземпляр с реальными числами. Это поможет «отследить», что происходит при вызове одной функции со значением 3 в качестве аргумента:
# Первый вызов
factorial_recursive(3):
if 3 == 1:
return 3
else:
return 3*factorial_recursive(3-1)
# Второй вызов
factorial_recursive(2):
if 2 == 1:
return 2
else:
return 2*factorial_recursive(2-1)
# Третий вызов
factorial_recursive(1):
if 1 == 1:
return 1
else:
return 1*factorial_recursive(1-1)Рекурсивная функция не знает ответа для выражения 3*factorial_recursive(3–1) , поэтому она добавляет в стек еще один вызов.
Как работает рекурсия
/\ factorial_recursive(1) - последний вызов || factorial_recursive(2) - второй вызов || factorial_recursive(3) - первый вызовВыше показывается, как генерируется стек. Это происходит благодаря процессу LIFO (last in, first out, «последним пришел — первым ушел»). Как вы помните, первые вызовы функции не знают ответа, поэтому они добавляются в стек.
Но как только в стек добавляется вызов factorial_recursive(1) , для которого ответ имеется, стек начинает «разворачиваться» в обратном порядке, выполняя все вычисления с реальными значениями. В процессе каждый из слоев выпадает в процессе.
- factorial_recursive(1) завершается, отправляет 1 в
- factorial_recursive(2) и выпадает из стека.
- factorial_recursive(2) завершается, отправляет 2*1 в
- factorial_recursive(3) и выпадает из стека. Наконец, инструкция else здесь завершается, возвращается 3 * 2 = 6, и из стека выпадает последний слой.
Рекурсия в Python имеет ограничение в 3000 слоев.
>>> import sys
>>> sys.getrecursionlimit()
3000Рекурсивно или итеративно?
Каковы же преимущества рекурсивных функций? Можно ли с помощью итеративных получить тот же результат? Когда лучше использовать одни, а когда — другие?
Важно учитывать временную и пространственную сложности. Рекурсивные функции занимают больше места в памяти по сравнению с итеративными из-за постоянного добавления новых слоев в стек в памяти. Однако их производительность куда выше.
Рекурсия может быть медленной, если реализована неправильно
Тем не менее рекурсия может быть медленной, если ее неправильно реализовать. Из-за этого вычисления будут происходить чаще, чем требуется.
Написание итеративных функций зачастую требуется большего количества кода. Например, дальше пример функции для вычисления факториала, но с итеративным подходом. Выглядит не так изящно, не правда ли?
def factorial_iterative(num):
factorial = 1
if num < 0:
print("Факториал не вычисляется для отрицательных чисел")
else:
for i in range (1, num + 1):
factorial = factorial*i
print(f"Факториал это ")Вычисление факториала
Факториалом числа называют произведение всех натуральных чисел до него включительно. Например, факториал числа 5 равен произведению 1 * 2 * 3 * 4 * 5 = 120.
Формула нахождения факториала:
n! = 1 * 2 * … * n,
где n – это число, а n! – факториал этого числа.
Формулу можно представить в таком виде:
т. е. каждый предыдущий множитель меньше на единицу, чем последующий. Или в перевернутом виде, когда каждый следующий меньше предыдущего на единицу:
Для вычисления факториала с помощью цикла можно использовать любую формулу. Для рекурсивного вычисления используется вторая.
Вычисление факториала с помощью циклов
n = int(input()) factorial = 1 while n > 1: factorial *= n n -= 1 print(factorial)Вычисление факториала с помощью цикла for :
n = int(input()) factorial = 1 for i in range(2, n+1): factorial *= i print(factorial)Нахождение факториала рекурсией
def fac(n): if n == 1: return 1 return fac(n - 1) * n print(fac(5))Поток выполнения программы при n = 5:
- Вызов функции fac(5)
- fac(5) вызывает fac(4)
- fac(4) вызывает fac(3)
- fac(3) вызывает fac(2)
- fac(2) вызывает fac(1)
- fac(1) возвращает в fac(2) число 1
- fac(2) возвращает в fac(3) число 1 * 2, т. е. 2
- fac(3) возвращает в fac(4) число 2 * 3, т. е. 6
- fac(4) возвращает в fac(5) число 6 * 4, т. е. 24
- fac(5) возвращает число 24 * 5, т. е. 120 в основную ветку программы
- Число 120 выводится на экран
Функция factorial модуля math
Модуль math языка программирования Python содержит функцию factorial , принимающую в качестве аргумента неотрицательное целое число и возвращающую факториал этого числа:
>>> import math >>> math.factorial(4) 24Вычисление факториала числа с использованием рекурсии
Программа принимает на вход число и вычисляет факториал этого числа с использованием рекурсивного алгоритма.
Решение задачи
- Записываем введенное пользователем число в отдельную переменную.
- Передаем это число в качестве аргумента в рекурсивную функцию, которая вычисляет факториал.
- Определяем внутри этой функции базовое условие рекурсии: в случае, когда аргумент функции меньше либо равен 1 , рекурсивная функция прекращает свою работу и возвращает в качестве результата 1 .
- В противном случае в качестве результата возвращается число, умноженное на рекурсивную функцию, аргумент которой уменьшен на единицу. И все повторяется заново.
- После того, как рекурсивная функция прекратила свою работу, на экран выводится результат.
- Конец.
Исходный код
Ниже дан исходный код, который осуществляет нахождение факториала числа при помощи рекурсии. Результаты работы программы также даны ниже.
Объяснение работы программы
- Пользователь вводит число и оно записывается в переменную n .
- Передаем число n в качестве аргумента в рекурсивную функцию, которая вычисляет факториал этого числа.
- Задаем базу рекурсии при помощи условия n
- В противном случае функция возвращает n * factorial(n-1) и все повторяется заново.
- После того, как функция завершит свою работу, результат выводится на экран.
Результаты работы программы
Пример 1: Введите число:5 Факториал числа равен: 120 Пример 2: Введите число:9 Факториал числа равен: 362880