Vzájemná rekurze

V matematice a programování je vzájemná rekurze typem rekurze , kdy dva matematické nebo programové objekty, jako jsou funkce nebo datové typy, jsou definovány navzájem [1] . Vzájemná rekurze je běžná ve funkcionálním programování a v některých problémových oblastech, jako je metoda rekurzivního sestupu , kde jsou datové typy přirozeně vzájemně rekurzivní, což není běžné v jiných oborech.

Příklady

Datové typy

Nejdůležitějším příkladem dat, která lze definovat pomocí vzájemné rekurze, je strom , který lze definovat jako les (seznam stromů). V symbolické podobě:

f: [t[1], ..., t[k]] t:vf

Les f se skládá ze seznamu stromů, zatímco strom t se skládá z dvojice - hodnota v a lesa f (děti). Tato definice je elegantní a snadno se s ní pracuje, protože strom je vyjádřen jednoduchými slovy – seznam jednoho typu a dvojice dvou typů. Tento datový typ je vhodný pro mnoho stromových algoritmů, které zpracovávají hodnoty jedním způsobem a řeší větvení jiným způsobem.

Tuto vzájemně rekurzivní definici lze převést na jedinou rekurzivní definici pomocí vestavěné definice doménové struktury: t: v [t[1], ..., t[k]]. Strom t je pár - hodnota v a seznam stromů (dětí). Tato definice je kompaktnější, ale ne vše je zde čisté - strom je dvojice - hodnota jednoho typu a seznam jiného typu, což bude vyžadovat odvíjení od výše uvedené definice.

Ve standardním ML lze stromové a lesní datové typy definovat vzájemně rekurzivně následovně, pokud jsou povoleny prázdné stromy [2] :

datový typ ' strom = Empty | Uzel ' a * ' les a ' les = nula | _ _ _ Nevýhody ' strom * ' les _ _ _

Funkce počítače

Stejně jako algoritmy na rekurzivních datových typech mohou být definovány rekurzivními funkcemi, algoritmy na vzájemně rekurzivních datových strukturách mohou být přirozeně definovány vzájemně rekurzivními funkcemi. Mezi známé příklady patří stromové algoritmy a metoda rekurzivního sestupu . Stejně jako v případě přímé rekurze je optimalizace koncové rekurze nezbytná, pokud je hloubka rekurze velká nebo není vůbec omezena. Všimněte si, že optimalizace rekurze ocasu obecně (pokud volaná funkce není stejná jako původní funkce, jako u rekurze ocasu) může být obtížnější implementovat než v případě optimalizace rekurze ocasu a efektivní implementace vzájemné rekurze ocasu nemusí být k dispozici v jazycích, které optimalizují pouze koncová volání. V jazycích, jako je Pascal , které vyžadují definice objektů před použitím objektu, vyžadují vzájemně rekurzivní funkce dopřednou deklaraci .

Stejně jako u přímých rekurzivních funkcí mohou být užitečné funkce wrapper se vzájemně rekurzivními funkcemi definovanými jako vnořené funkce To je užitečné zejména pro sdílení dat mezi více funkcemi bez předávání parametrů.

Základní příklady

Standardní příklad vzájemné rekurze, což je nepochybně umělý trik, určuje, zda je číslo sudé nebo ne, definováním dvou samostatných funkcí, které se navzájem volají a snižují číslo při každém hovoru [3] . Na C:

bool is_even ( unsigned int n ) { if ( n == 0 ) vrátit true ; jiný návrat je_lichý ( n - 1 ); } bool je_lichý ( unsigned int n ) { if ( n == 0 ) vrátit false ; jiný return is_even ( n - 1 ); }

Tyto funkce jsou založeny na pozorování, že otázka "4 je sudá?" je ekvivalentní k otázce "3 je lichá?", která je zase ekvivalentní k otázce "2 je sudá" a tak dále až do 0. Příklad ukazuje vzájemnou rekurzi jednotek , kterou lze snadno nahradit a smyčka. V tomto příkladu jsou vzájemná rekurzní volání koncová volání a je žádoucí optimalizovat koncová volání tak, aby provádění probíhalo na konstantním zásobníku. V C budou funkce vyžadovat O ( n ) zásobníkový prostor, pokud místo volání funkcí nepoužijete skoky (goto) [4] . Příklad lze převést na jedinou rekurzivní funkci is_even. V tomto případě is_oddlze použít inline a zavolá is_even, ale is_evenzavolá pouze sám sebe.

Příklad z obecnější třídy příkladů, stromový algoritmus, lze rozložit na hodnotovou operaci a operaci větvení a poté rozdělit na dvě vzájemně rekurzivní funkce, přičemž jedna z funkcí působí na strom a volá funkci lesa. , druhý pracuje s lesem a volá funkci pro strom pro každý prvek lesa. V jazyce Python:

def f_tree ( strom ): f_value ( strom . hodnota ) f_forest ( strom . děti ) def f_forest ( les ): pro strom v lese : f_tree ( strom )

V tomto případě funkce stromu volá funkci doménové struktury pomocí jedné rekurze, ale funkce doménové struktury používá vícenásobnou rekurzi na stromě .

Pomocí datových typů popsaných výše ve Standard ML lze velikost stromu (počet hran) vypočítat pomocí následujících vzájemně rekurzivních funkcí [5] :

zábava size_tree Prázdný = 0 | size_tree ( Uzel (_, f )) = 1 + size_forest f a size_forest Nil = 0 | size_forest ( Cons ( t , f' )) = size_tree t + size_forest f'

Podrobnější příklad schématu , který počítá počet listů ve stromu [6] :

( definovat ( strom počítání listů ) ( if ( list? strom ) 1 ( počítání listů v lese ( dětský strom )))) ( definovat ( count-leaves-in-forest forest ) ( if ( null? forest ) 0 ( + ( count-leaves ( car forest )) ( count-leaves-in-forest ( cdr forest )))))

Tyto příklady lze snadno zredukovat na jedinou rekurzivní funkci začleněním funkce lesa do funkce stromu, což se v praxi často provádí.

Pokročilejší příklady

Složitější příklady jsou příklady rekurzivního sestupu , které lze implementovat přirozeným způsobem tak, že každému generativnímu pravidlu gramatiky dáme jednu funkci, která se pak vzájemně rekurzivně volají. Obecně se bude jednat o vícenásobné rekurze, kdy generování pravidel kombinuje několik pravidel. To lze provést bez vzájemné rekurze, tím, že pro každé pravidlo generování máme samostatné funkce, ale zavoláním jedné řídicí funkce nebo zpracováním celé gramatiky v jedné funkci.

Vzájemnou rekurzi lze také použít k implementaci stavového automatu s jednou funkcí pro každý stav a jednou rekurzí na změnu stavu. To vyžaduje optimalizaci koncové rekurze, pokud je počet stavů velký nebo neomezený. Tento přístup lze použít jako jednoduchou formu kooperativního multitaskingu . Podobný přístup k multitaskingu využívá korutiny , které se navzájem volají, kde místo toho, aby byla přerušena voláním jiné procedury, jedna korutina volá další, ale není přerušena, ale pokračuje v provádění, když se volaná korutina vrátí. To umožňuje jednotlivým rutinám uložit stav bez nutnosti předávat parametry nebo ukládat sdílené proměnné.

Existují také algoritmy, které mají přirozeně dvě fáze, jako je minimax (min a max), a ty lze implementovat vytvořením samostatné vzájemně rekurzivní funkce pro každou fázi, i když je lze také kombinovat do jediné přímé rekurzivní funkce.

Matematické funkce

V matematice jsou mužské a ženské Hofstadterovy sekvence příkladem dvojice sekvencí celých čísel, která jsou vzájemně rekurzivní.

Fraktály lze vypočítat (s požadovanou přesností) pomocí rekurzivních funkcí. To lze někdy provést elegantněji pomocí vzájemně rekurzivních čísel. Dobrým příkladem je Sierpinského křivka .

Prevalence

Vzájemná rekurze je široce používána ve funkcionálním programování a často se používá v programech napsaných v Lisp , Scheme , ML a dalších podobných jazycích . V jazycích jako Prolog je vzájemná rekurze téměř nevyhnutelná.

Některé programovací styly odrazují od vzájemné rekurze a tvrdí, že je obtížné rozlišit mezi podmínkami, které vrátí odpověď, od podmínek, které způsobí, že se kód zacyklí (běží navždy bez vrácení odpovědi). Peter Norvig poukázal na vývojový vzorec , kterému bychom se měli stejně vyhnout. Říká [7] :

Pokud máte dvě vzájemně rekurzivní funkce, které mění stav objektu, zkuste přesunout téměř všechny funkce do jedné z těchto funkcí. V opačném případě je pravděpodobnější, že skončíte s duplikací kódu.

Terminologie

Vzájemná rekurze je také známá jako nepřímá rekurze , na rozdíl od přímé rekurze , kdy jedna funkce volá sama sebe přímo. Jde jen o rozdíl v důrazu, nikoli o rozdíl v přístupu – „nepřímá rekurze“ zdůrazňuje použití jednotlivé funkce, zatímco „vzájemná rekurze“ zdůrazňuje použití množiny funkcí spíše než jednotlivé jednotlivé funkce. Například, pokud f volá sebe, je to přímá rekurze. Jestliže f volá g a pak g volá f, který zase volá g , z hlediska samotného f má f nepřímou rekurzi. Z hlediska funkce g má také nepřímou rekurzi. Ale z hlediska množiny funkcí f a g máme vzájemnou rekurzi. Podobně se může vzájemně volat množina tří nebo více funkcí.

Redukce na přímou rekurzi

Matematicky je množina vzájemně rekurzivních funkcí primitivně rekurzivní , což lze dokázat pomocí zpětné rekurze [8] , pro kterou je zkonstruována funkce F , která vyčísluje hodnoty jednotlivých rekurzivních funkcí v proloženém pořadí: a vzájemná rekurze je přepsán jako primitivní rekurze.

Jakákoli vzájemná rekurze mezi dvěma procedurami může být redukována na přímou rekurzi vložením kódu jedné procedury do druhé. Pokud existuje pouze jedno místo, kde procedura volá jiné, lze to provést přímo, ale pokud existuje několik takových míst, může být vyžadována duplikace kódu. Pokud jde o využití zásobníku, dvě vzájemně rekurzivní procedury naplní zásobník sekvencí volání ABABAB... a vložení procedury B do A vede k přímé rekurzi (AB)(AB)(AB)...

Alternativně lze libovolný počet procedur sloučit do jediné procedury, která má jako argument označenou unii (nebo algebraický datový typ ), která ukládá informace o volané proceduře a jejích argumentech. Sestavená procedura vybere větev na základě argumentů a spustí příslušný kód, poté použije přímou rekurzi, aby se zavolala s příslušnými argumenty. Tento přístup lze považovat za zkrácenou verzi vyloučení funkcí [9] . Toto sloučení funkcí může být užitečné, když některé funkce mohou být volány externím kódem, takže vnoření jedné procedury do druhé není možné. Takový kód je třeba převést tak, aby se volání procedury provádělo zřetězením argumentů do „označeného spojení“, jak je popsáno výše. Další možností je použít balicí proceduru.

Viz také

Poznámky

  1. ↑ Rubio-Sánchez, Urquiza-Fuentes, Pareja-Flores, 2008 , s. 235-239.
  2. ↑ Harper, 2005 , " Typy dat ".
  3. ↑ Hutton, 2007 , 6.5 Vzájemná rekurze, pp. 53–55 .
  4. ↑ „ Vzájemná rekurze ocasu archivována 10. dubna 2016 na Wayback Machine “ a „ Tail-Rekurzivní funkce archivována 10. dubna 2016 na stroji Wayback “, Výukový program o funkcích programování v ATS Archivováno 27. prosince 2017 na stroji Wayback Xi, Hongwei 2010
  5. ↑ Harper, 2005 , " Datové typy ".
  6. ↑ Harvey, Wright, 1999 , V. Abstrakce: 18. Stromy: Vzájemná rekurze, pp. 310–313 .
  7. ↑ Řešení každého sudoku . Získáno 13. ledna 2017. Archivováno z originálu 15. listopadu 2020.
  8. ↑ " vzájemná rekurze Archivováno 21. června 2018 na Wayback Machine " PlanetMath
  9. ↑ Reynolds, John (srpen 1972). „Definální interprety pro programovací jazyky vyššího řádu“ (PDF) . Sborník příspěvků z výroční konference ACM . Boston, Massachusetts. str. 717-740. Archivováno 29. června 2011 na Wayback Machine

Literatura

  • Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes, Cristóbal Pareja-Flores. Bulletin ACM SIGCSE. - ACM, 2008. - T. 40. - S. 235-239.
  • Robert Harper. Programování ve standardním ML (pracovní návrh ze 17. května 2005). — Carnegie Mellon University, 2005.
  • Brian Harvey, Matthew Wright. Jednoduše schéma: Představujeme informatiku. - MIT Press, 1999. - ISBN 978-0-26208281-5 .
  • Graham Hutton. Programování v Haskellu. - Cambridge University Press, 2007. - ISBN 978-0-52169269-4 .

Odkazy