✅ Рекурсивна функція в 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.

Ми імпортуємо бібліотеку "час" і перевіримо, скільки часу потрібна рекурсія та ітерація, щоб повернути результат.

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 Гб оперативної пам’яті 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 - Що таке функція рекурсії?