Vše, co potřebujete vědět o rekurzi v Pythonu



Tento článek vám pomůže získat podrobné a komplexní znalosti o rekurzi v Pythonu. Jak to funguje? a jaký je jeho účel?

Jednoduše řečeno, rekurze je způsob, jak vyřešit problém tím, že se funkce volá sama, slovo „ rekurzivní „Pochází z latinského slovesa“ opakovat “, Což znamená něco předělat. To je to, co dělá rekurzivní funkce, znovu a znovu opakuje to samé, tj. Připomíná se. V tomto článku se dozvíme o rekurzi v pythonu. Následující témata se zabývají tímto blogem:

Co je rekurze v Pythonu?

Rekurze je proces určování něčeho samotného. Víme, že v Pythonu může jakákoli funkce volat jakoukoli jinou funkci, funkce se také může nazývat sama. Tyto typy funkcí, které se nazývají, dokud není splněna určitá podmínka, se nazývají rekurzivní funkce.





Recursion-in-Python

Podívejme se na několik příkladů, abychom zjistili, jak to funguje. Pokud dostanete kladné celé číslo, faktoriál by byl.



  • n! = n * (n-1) * (n-2) atd.
  • 2! = 2 * (2-1)
  • jeden! = 1
  • 0! = 0
  • 4! = 4 * 3!
  • 3! = 3 * 2!
  • 2! = 2 * 1!

Nahrazení výše uvedených hodnot bude mít za následek následující výraz

  • 4! = 4 * 3 * 2 * 1

Musíme definovat funkci, řekněme fakt (n), která jako parametr vezme kladné celé číslo nebo 0 a vrátí n-tý faktoriál, jak to můžeme udělat pomocí rekurze?

Podívejme se, abychom to mohli udělat pomocí rekurze, musíme prozkoumat následující rovnici



  • n! = n. (n-1). (n-2) & hellip3.2.1

  • n! = n. (n-1)! # můžeme přepsat výše uvedené prohlášení jako na tomto řádku

    parsování XML souborů v Javě
  • Nyní, pokud předáme 2 jako parametr, dostaneme:

    • 2! = 2,1! = 2

  • Podobně, když předáme 1, dostaneme:

  • Pokud ale předáme 0, rozbije se

    • 0! = 0. (- 1)! a zde faktoriál pro -1 není definován, takže to funguje pouze pro hodnoty> 0

  • Musíme tedy napsat dva případy

    • 1. n! = n. (n-1)! pokud n> = 1

    • 2. 1 pokud n = 0

Toto je kompletní řešení pro všechna kladná celá čísla a 0.

Podmínka ukončení

Rekurzivní funkce musí splnit důležitou podmínku pro ukončení. Pohybem směrem k podmínce, kde lze problém vyřešit bez další rekurze, se rekurzivní funkce ukončí a problém se minimalizuje do menších dílčích kroků. Rekurze může skončit v nekonečné smyčce, pokud ve volání není splněna podmínka ukončení.

Faktorové podmínky:

  • faktoriál n = n * (n-1), pokud je n větší než 1.
  • 1 pokud n = 0

Převedeme výše uvedené faktoriální podmínky v kódu pythonu:

def fact (n): if n == 1: return n else: return n * fact (n-1)

Vezměme si příklad, řekněme, že chceme najít faktoriál 4:

fakt (4) #this vrátí 4 * fakt (3) a tak dále, dokud n == 1.
 Výstup: 24

Používá se tak často jako příklad rekurze kvůli své jednoduchosti a srozumitelnosti. Řešení menších instancí problému se v každém kroku označovalo jako rekurze v počítačové vědě.

Limit rekurze Pythonu

V některých jazycích můžete vytvořit nekonečnou rekurzivní smyčku, ale v Pythonu existuje limit rekurze. Pro kontrolu limitu spusťte následující funkci z modulu sys. což dá limit rekurze nastavené pro python.

importovat sys sys.getrecursionlimit ()
 Výstup: 1000

Můžete také změnit limit pomocí funkce sysrecursionlimit () modulu sys podle vašeho požadavku. Nyní vytvořme funkci, která se rekurzivně volá, dokud nepřekročí limit a nekontroluje, co se stane:

def rekurzivní (): rekurzivní () pokud __name__ == '__main__': rekurzivní ()

Pokud spustíte výše uvedený kód, získáte runtime výjimku: RuntimeError: překročena maximální hloubka rekurze. Python vám brání ve vytvoření funkce, která skončí v nekonečné rekurzivní smyčce.

Sloučení seznamů s rekurzí

Další věci, které můžete pomocí rekurze dělat, s výjimkou faktoriálů, řekněme, že chcete vytvořit singl ze seznamu, který je vnořený, lze provést pomocí níže uvedeného kódu:

def flatten (a_list, flat_list = none): pokud flat_list není none: flat_list = [] pro položku v a_list: if isinstance (item, list): flatten (item, flat_list) else: flat_list.append (item) vrátit flat_list pokud __name__ == '__main__': nested = [1,2,3, [4,5], 6] x = zploštění (vnoření) print (x)
 Výstup: [1,2,3,4,5,6]

Spuštění výše uvedeného kódu bude mít za následek jediný seznam namísto celočíselného seznamu obsahujícího celočíselný seznam, který jsme použili jako vstup. Stejnou věc můžete udělat i jinými způsoby, Python má něco, co se nazývá itertools.chain (), můžete zkontrolovat kód použitý pro vytvoření funkčního řetězce (), je to jiný přístup k tomu, co děláme stejně jako my.

Výhody rekurze

  • Kód je čistý a elegantní v rekurzivní funkci.

  • Složený úkol lze pomocí rekurze rozdělit na jednodušší dílčí problémy.

  • Generování sekvence je s rekurzí snazší než s použitím nějaké vnořené iterace.

Nevýhody rekurze

  • Sledování logiky za rekurzivní funkcí může být někdy těžké.

  • Rekurzivní volání jsou drahá (neúčinná), protože zabírají spoustu paměti a času.

  • Rekurzivní funkce se obtížně ladí.

    algoritmy a datové struktury v Javě

V tomto článku jsme viděli, co je to rekurze a jak můžeme vyvinout rekurzivní funkce z prohlášení o problému, jak matematicky lze problémové prohlášení definovat. Vyřešili jsme problém faktoriálu a zjistili jsme podmínky potřebné k nalezení faktoriálů, ze kterých jsme byli schopni převést tyto podmínky do kódu pythonu, abychom vám porozuměli, jak funguje rekurze. Myslím, že je skvělé, že Python má zabudovaný limit pro rekurzi, aby vývojářům zabránil ve vytváření špatně konstruovaných rekurzivních funkcí. Jedna důležitá věc, kterou si musíte všimnout, je, že rekurze je těžké ladit, protože funkce se stále volá.