У цьому посібнику ви навчитеся створювати рекурсивну функцію (функцію, яка викликає себе).
Що таке рекурсія?
Рекурсія - це процес визначення чогось із точки зору самого себе.
Прикладом фізичного світу може бути розміщення двох паралельних дзеркал один напроти одного. Будь-який об'єкт між ними буде відображатися рекурсивно.
Рекурсивна функція Python
У Python ми знаємо, що функція може викликати інші функції. Функція навіть може викликати себе. Ці типи конструкцій називаються рекурсивними функціями.
На наступному зображенні показано роботу рекурсивної функції recurse.
Рекурсивна функція в Python
Далі наведено приклад рекурсивної функції для пошуку факторіалу цілого числа.
Факториал числа - це добуток усіх цілих чисел від 1 до цього числа. Наприклад, множник 6 (позначений як 6!) Дорівнює 1 * 2 * 3 * 4 * 5 * 6 = 720.
Приклад рекурсивної функції
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Вихідні дані
Факторіал 3 дорівнює 6
У наведеному вище прикладі factorial()є рекурсивною функцією, як вона сама називається.
Коли ми викликаємо цю функцію з додатним цілим числом, вона буде рекурсивно викликати себе, зменшуючи число.
Кожна функція множить число на факторіал числа під ним, поки воно не дорівнює одиниці. Цей рекурсивний виклик можна пояснити наступними кроками.
факторіал (3) # 1-й дзвінок з 3 3 * факторіал (2) # 2-й дзвінок з 2 3 * 2 * факторіал (1) # 3-й дзвінок з 1 3 * 2 * 1 # повернення з 3-го дзвінка як номер = 1 3 * 2 # повернення з 2-го дзвінка 6 # повернення з 1-го дзвінка
Давайте розглянемо зображення, яке показує покроковий процес того, що відбувається:
Робота рекурсивної факторіальної функції
Наша рекурсія закінчується, коли число зменшується до 1. Це називається базовою умовою.
Кожна рекурсивна функція повинна мати базову умову, яка зупиняє рекурсію, інакше функція сама нескінченно викликає себе.
Інтерпретатор Python обмежує глибину рекурсії, щоб уникнути нескінченних рекурсій, що призводить до переповнення стека.
За замовчуванням максимальна глибина рекурсії становить 1000. Якщо межа перетнута, це призводить до RecursionError. Давайте розглянемо одну з таких умов.
def recursor(): recursor() recursor()
Вихідні дані
Відстеження (останній останній дзвінок): Файл "", рядок 3, у файлі "", рядок 2, у файлі "", рядок 2, у файлі "", рядок 2, у (Попередній рядок повторено ще 996 разів ) RecursionError: перевищено максимальну глибину рекурсії
Переваги рекурсії
- Рекурсивні функції роблять код вигляд чистим та елегантним.
- Складне завдання можна розбити на більш прості підзадачі за допомогою рекурсії.
- Генерування послідовності простіше з рекурсією, ніж використання вкладеної ітерації.
Недоліки рекурсії
- Іноді логіку рекурсії важко простежити.
- Рекурсивні дзвінки є дорогими (неефективними), оскільки вони займають багато пам'яті та часу.
- Рекурсивні функції важко налагодити.
