Рекурсивное вычисление факториала python

Рекурсия

Рекурсия — это мощный инструмент в программировании, который может быть использован для решения многих задач. В 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
 
Источник