В този урок ще се научите да създавате рекурсивна функция (функция, която се извиква).
Какво е рекурсия?
Рекурсията е процес на определяне на нещо от гледна точка на себе си.
Пример за физически свят би бил поставянето на две успоредни огледала един срещу друг. Всеки обект между тях ще бъде отразен рекурсивно.
Рекурсивна функция на 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: превишена е максималната дълбочина на рекурсия
Предимства на рекурсията
- Рекурсивните функции правят кода да изглежда чист и елегантен.
- Сложна задача може да бъде разделена на по-прости подзадачи с помощта на рекурсия.
- Генерирането на последователност е по-лесно с рекурсия, отколкото използването на някаква вложена итерация.
Недостатъци на рекурсията
- Понякога логиката зад рекурсията е трудна за проследяване.
- Рекурсивните разговори са скъпи (неефективни), тъй като отнемат много памет и време.
- Рекурсивните функции са трудни за отстраняване на грешки.
