V tomto tutoriále sa naučíte vytvárať rekurzívne funkcie (funkcie, ktoré si hovoria).
Čo je to rekurzia?
Rekurzia je proces definovania niečoho v jeho zmysle.
Fyzickým svetovým príkladom by bolo umiestnenie dvoch paralelných zrkadiel oproti sebe. Akýkoľvek objekt medzi nimi by sa odrážal rekurzívne.
Rekurzívna funkcia v Pythone
V Pythone vieme, že funkcia môže volať ďalšie funkcie. Je dokonca možné, aby si funkcia sama hovorila. Tieto typy konštruktov sa označujú ako rekurzívne funkcie.
Nasledujúci obrázok ukazuje fungovanie rekurzívnej funkcie s názvom recurse.
Rekurzívna funkcia v Pythone
Nasleduje príklad rekurzívnej funkcie na vyhľadanie faktoriálu celého čísla.
Faktoriál čísla je súčin všetkých celých čísel od 1 do tohto čísla. Napríklad faktoriál 6 (označený ako 6!) Je 1 * 2 * 3 * 4 * 5 * 6 = 720.
Príklad rekurzívnej funkcie
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))
Výkon
Faktoriál 3 je 6
Vo vyššie uvedenom príklade factorial()je to rekurzívna funkcia, ako si hovorí.
Keď túto funkciu zavoláme s kladným celým číslom, bude sa rekurzívne nazývať znížením počtu.
Každá funkcia vynásobí číslo faktoriálom čísla pod ním, kým sa nerovná jednej. Toto rekurzívne volanie je možné vysvetliť v nasledujúcich krokoch.
faktoriál (3) # 1. hovor s 3 3 * faktoriál (2) # 2. hovor s 2 3 * 2 * faktoriál (1) # 3. hovor s 1 3 * 2 * 1 # návrat z 3. hovoru ako číslo = 1 3 * 2 # návrat z 2. hovoru 6 # návrat z 1. hovoru
Pozrime sa na obrázok, ktorý ukazuje postupný proces toho, čo sa deje:
Práca s rekurzívnou faktoriálnou funkciou
Naša rekurzia končí, keď sa počet zníži na 1. Toto sa nazýva základná podmienka.
Každá rekurzívna funkcia musí mať základnú podmienku, ktorá zastaví rekurziu, inak sa funkcia nazýva nekonečne.
Interpretátor Pythonu obmedzuje hĺbky rekurzie, aby zabránil nekonečným rekurziám, ktoré vedú k pretečeniu zásobníka.
Štandardne je maximálna hĺbka rekurzie 1 000. Ak dôjde k prekročeniu limitu, bude to mať za následok RecursionError. Pozrime sa na jednu takúto podmienku.
def recursor(): recursor() recursor()
Výkon
Traceback (posledný hovor posledný): Súbor „“, riadok 3, v priečinku „“, riadok 2, v priečinku „“, riadok 2, v priečinku „“, riadok 2, v a (predchádzajúci riadok sa opakuje 996-krát ) RecursionError: bola prekročená maximálna hĺbka rekurzie
Výhody rekurzie
- Vďaka rekurzívnym funkciám bude kód vyzerať čisto a elegantne.
- Zložitú úlohu je možné pomocou rekurzie rozdeliť na jednoduchšie čiastkové problémy.
- Generovanie sekvencie je s rekurziou jednoduchšie ako s použitím vnorenej iterácie.
Nevýhody rekurzie
- Logiku, ktorá stojí za rekurziou, je niekedy ťažké dodržať.
- Rekurzívne hovory sú drahé (neúčinné), pretože zaberajú veľa pamäte a času.
- Rekurzívne funkcie je ťažké ladiť.
