✅ Рекурсивная функция в Python - Что такое функция рекурсии?

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

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

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

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

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

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

Допустим, нам нужно найти факториал числа 5 => 5! (Наша проблема)

Чтобы найти 5! проблема может быть разбита на более мелкие 5! => 5 х 4!

Итак, чтобы получить 5! Нам нужно найти 4! и умножьте это на 5.

Давайте продолжим разделять проблему

5! = 4! х 5

4! = 3! х 4

3! = 3 х 2!

2! = 2 х 1!

1! = 1

Когда он достигает наименьшего куска, т.е. получая факториал 1, мы можем вернуть результат как

Давайте возьмем пример псевдокода:

Алгоритм факториала

Давайте посмотрим алгоритм для факториала:

function get_factorial( n ): if n < 2: return 1 else: return get_factorial(n -1)

Вызовы функций

Предположим, мы находим факториал 5.

get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call get_factorial(1) returns 1 #5th call

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

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

Плюсы и минусы рекурсивной функции Python

Выполнение рекурсии таково, что она не будет выполнять никаких вычислений, пока не достигнет базового условия.
При достижении базовых условий вам может не хватить памяти.
В большой проблеме, где может быть миллион шагов или, скажем, миллион рекурсий, программа может в итоге выдать ошибку памяти или ошибку сегментации.
1000000! = 1000000 * 999999! знак равно
Рекурсия отличается от итерации, она не масштабируется как итерационный метод.
Разные языки имеют разные оптимизации для рекурсии.
Во многих языках итерационный метод будет работать лучше, чем рекурсия.
Каждый язык имеет некоторые ограничения по глубине рекурсии, с которыми вы можете столкнуться при решении больших задач.
Иногда трудно понять сложные проблемы с рекурсией, тогда как с итерацией все довольно просто.

Некоторые плюсы

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

Код Python - рекурсия против итерации

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

Здесь мы бы сравнили метод рекурсии и итерации, чтобы увидеть, как Python работает в обоих случаях.

1. Код рекурсии для факториала

def get_recursive_factorial(n): if n < 0: return -1 elif n < 2: #base condition return 1 else: return n * get_recursive_factorial(n -1) #recursion condition

2. Факториальная задача с использованием итерации (зацикливание)

def get_iterative_factorial(n): if n < 0: return -1 else: fact = 1 for i in range( 1, n+1 ): fact *= i return fact

3. Печать результатов

print(get_recursive_factorial(6)) print(get_iterative_factorial(6))

Выход:

Как мы видим, оба дают одинаковый результат, поскольку мы написали одну и ту же логику. Здесь мы не видим никакой разницы в исполнении.

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

Мы импортируем библиотеку «time» и проверим, сколько времени потребуется для рекурсии и итерации, чтобы вернуть результат.

4. Код с расчетом времени

import time def get_recursive_factorial(n): if n < 0: return -1 elif n < 2: return 1 else: return n * get_recursive_factorial(n-1) def get_iterative_factorial(n): if n < 0 : return -1 else: fact = 1 for i in range(1, n+1): fact *= i return fact start_time = time.time() get_recursive_factorial(100) print("Recursion--- %s seconds ---" % (time.time() - start_time)) start_time = time.time() get_iterative_factorial(100) print("Iteration--- %s seconds ---" % (time.time() - start_time))

Мы сделаем повторное выполнение с другим значением факториала и посмотрим результаты. Приведенные ниже результаты могут отличаться на разных машинах. Мы использовали MacBook Pro 16 ГБ RAM i7.

Мы используем Python 3.7 для выполнения

Дело 1: - Факториал 6:

Случай 2: Факториал 50:

Случай 3: Факториал 100:

Случай 4: Факториал 500:

Случай 5: Факториал 1000:

Мы проанализировали оба метода в другой проблеме. Более того, оба выполнили подобное, кроме случая 4.

В случае 5 мы получили ошибку при выполнении рекурсии.

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

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

Функция «sys.getrecursionlimit ()» сообщит вам предел для рекурсии.

Предел рекурсии может быть изменен, но не рекомендуется, это может быть опасно.

Вывод - рекурсивная функция Python

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

Рекурсивная функция в Python - Что такое функция рекурсии?