С прости думи, рекурсията е начин за решаване на проблема чрез извикване на самата функция, Думата „ рекурсивен ”Произхожда от латинския глагол“ повтарят ”, Което означава да се преработи нещо. Това прави рекурсивната функция, тя повтаря едно и също нещо отново и отново, т.е. тя се припомня. В тази статия ще научим за рекурсията в python. Следват темите, разгледани в този блог:
- Какво представлява рекурсията в Python?
- Условие за прекратяване
- Python’s Recursion Limit
- Списъци за изравняване с рекурсия
- Предимства на рекурсията
- Недостатъци на рекурсията
Какво представлява рекурсията в Python?
Рекурсията е процес на определяне на нещо от гледна точка на себе си. Знаем, че в Python всяка функция може да извика всяка друга функция, функция също може да извика себе си. Тези типове функции, които се самоизвикват, докато дадено условие не е изпълнено, се наричат рекурсивни функции.
нека вземем няколко примера, за да видим как работи това. Ако ви бъде дадено положително цяло число n, факториалът ще бъде.
- н! = n * (n-1) * (n-2) и т.н.
- 2! = 2 * (2-1)
- един! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Замяната на горните стойности ще доведе до следния израз
- 4! = 4 * 3 * 2 * 1
Трябва да дефинираме функция, която позволява да кажем факт (n), който приема положително цяло число или 0 като свой параметър и връща n-ти факториал, как можем да направим това, използвайки рекурсия?
Нека да видим, за да използваме рекурсията, трябва да разгледаме следното уравнение
н! = n. (n-1). (n-2) & hellip3.2.1
н! = n. (n-1)! # можем да пренапишем горното изявление както на този ред
Сега тук, ако предадем 2 като параметър, ще получим:
2! = 2,1! = 2
По същия начин, ако преминем 1, ще получим:
използване на скенер в java
един! = 1,0! = 1
Но ако преминем 0, той се счупва
0! = 0. (- 1)! и тук факториал за -1 не е дефиниран, така че това работи само за стойности> 0
Така че трябва да напишем два случая
1. п! = n. (n-1)! ако n> = 1
2. 1, ако n = 0
Това е цялостно решение за всички положителни числа и 0.
претоварване на функцията в c ++
Условие за прекратяване
Рекурсивната функция трябва да изпълнява важно условие за прекратяване. Придвижвайки се към състояние, при което проблемът може да бъде решен без допълнителна рекурсия, рекурсивната функция ще се прекрати, минимизирайки проблема в по-малките под-стъпки. Рекурсията може да завърши в безкраен цикъл, ако условието за прекратяване не е изпълнено в разговорите.
Факторни условия:
- факториал на n = n * (n-1), докато n е по-голямо от 1.
- 1, ако n = 0
Ще преобразуваме горните факториални условия в python код:
def fact (n): ако n == 1: връщане n else: връщане n * факт (n-1)
Да вземем пример, да кажем, че искаме да намерим факториал от 4:
fact (4) #this ще върне 4 * fact (3) и така до n == 1.
Изход: 24
Използва се толкова често като пример за рекурсия поради своята простота и яснота. Решаването на по-малки случаи на проблем на всяка стъпка се нарича рекурсия в компютърните науки.
Python’s Recursion Limit
В някои езици можете да създадете безкраен рекурсивен цикъл, но в Python има ограничение за рекурсия. За да проверите лимита, стартирайте следната функция от модула sys. което ще даде границата на рекурсионния набор за python.
импортиране на sys sys.getrecursionlimit ()
Изход: 1000
Можете също така да промените лимита, като използвате функцията sys модулsetrecursionlimit () според вашето изискване, сега нека създадем функция, която се извиква рекурсивно, докато надвиши лимита и проверява какво се случва:
деф рекурсивно (): рекурсивно () ако __name__ == '__main__': рекурсивно ()
Ако стартирате горния код, ще получите изключение по време на изпълнение: RuntimeError: превишена е максималната дълбочина на рекурсия. Python ви пречи да създадете функция, която завършва в безкраен рекурсивен цикъл.
Списъци за изравняване с рекурсия
Други неща, които можете да правите с помощта на рекурсия, с изключение на факториали, да речем, че искате да създадете единичен от вложен в списък, може да се направи с помощта на кода по-долу:
def flatten (a_list, flat_list = none): ако flat_list е none: flat_list = [] за елемент в a_list: if isinstance (item, list): flatten (item, flat_list) else: flat_list.append (item) return flat_list if __name__ == '__main__': вложен = [1,2,3, [4,5], 6] x = изравняване (вложено) print (x)
Изход: [1,2,3,4,5,6]
Изпълнението на горния код ще доведе до един списък вместо целочислен списък, съдържащ цял списък, който използвахме като вход. Можете също да направите същото нещо, като използвате и други начини, Python има нещо, наречено itertools.chain (), можете да проверите кода, използван за създаване на функционална верига (), това е различен подход да се направи същото нещо като нас.
Предимства на рекурсията
Кодът е изчистен и елегантен в рекурсивна функция.
Комбинираната задача може да бъде разделена на по-прости подзадачи с помощта на рекурсия.
Генерирането на последователност е по-лесно с рекурсия, отколкото използването на някаква вложена итерация.
как да се избегне блокиране в java -
Недостатъци на рекурсията
Следването на логиката зад рекурсивната функция може да бъде трудно понякога.
Рекурсивните разговори са скъпи (неефективни), тъй като отнемат много памет и време.
Рекурсивните функции са трудни за отстраняване на грешки.
В тази статия видяхме какво е рекурсия и как можем да разработим рекурсивни функции от постановката на проблема, как математически може да бъде дефинирана заявка за проблем. Решихме проблем с факториала и открихме условия, необходими за намиране на факториали, от които успяхме да конвертираме тези условия в python код, давайки ви разбирането за това как работи рекурсията. Мисля, че е добре, че Python има вграден лимит за рекурсия, за да попречи на разработчиците да създават лошо конструирани рекурсивни функции. Едно важно нещо, което трябва да забележите, е, че рекурсията е трудна за отстраняване на грешки, тъй като функцията продължава да се извиква.