Rekurze a rekurzivní algoritmy

Toto slovo označuje proces, který odkazuje na opakování stejných prvků „sobě podobným způsobem“. Důstojným příkladem takového procesu je ruská hnízdící panenka, a nebýt hranice možností, pak by se taková hračka opakovala do nekonečna.

Z technických důvodů je rekurze stále konečná veličina.

V programování tento termín odkazuje na proces volání samotné funkce nebo volání funkce zevnitř. Rekurzivní volání musí mít přirozeně zcela proveditelné podmínky ukončení, jinak program s jinými podmínkami zamrzne a spadne s přeplněným zásobníkem.

Příkladem matematické rekurze je už tak docela nudný příklad výpočtu faktoriálu. Ve skutečnosti se rekurze ve webovém programování používá poměrně často, a to vše proto, že rekurze je jedinou možností, jak obejít jakoukoli standardní strukturu, když nevědí přesně o její skutečné velikosti a hloubce vnoření. Bez toho se neobejde ani konstrukce grafů. Toto je klasická možnost.

Abyste se ujistili, že je tento proces nezbytný, stojí za to zkusit sestavit mapu webu se sekcemi podle hierarchické struktury vnořených seznamů. To bude nereálné, pokud se předem neomezíte na jeho velikost a investiční hloubku. Pokud ale přeci jen něco podobného postavíte, pochopíte, že vám v určité chvíli celá konstrukce zamrzne a přestane fungovat.

Rekurze ve vyhledávačích

Na rekurzi závisí i vyhledávače. Od chvíle, kdy bylo zavedeno kritérium autority webu, měřené počtem odkazů, spadaly do těchto sítí i vyhledávače. Odkaz „hmotnost“ webu se skládá z malých kousků „hmoty“ všech zdrojů, které na něj odkazují. Pro výpočet tohoto ukazatele pro jeden web je nutné vypočítat „hmotnost“ všech možností odkazů, které se zase skládají z dalších podobných komponent atd., v celé hloubce vyhledávací sítě. Tolik k rekurzi v praxi.

Rekurzivní PageRank od Googlu

Toto je název pro výpočetní algoritmus vytvořený a publikovaný společností Google. Tento algoritmus je známý již dlouhou dobu, ale bez ohledu na to, kolikrát je přetvářen a doplňován nejrůznějšími vylepšeními, je stále založen na stejné rekurzivní metodě. Podstata zůstává vždy stejná: výpočty, přepočty a zase přepočty. Výsledkem je opět stejná funkce.

Rekurzivní TCI od Yandex

TIC vytvořený Yandexem má přesně stejnou strukturu jako předchozí algoritmus. Jediný rozdíl je v tom, že se počítá pro celý web jako celek, nikoli pro každou jednotlivou stránku. To je důvod, proč vyhledávač Yandex žije mnohem svobodněji než ostatní, protože stránek je mnohonásobně méně než stránek a je mnohem snazší je spočítat.

Tento indikátor však neovlivňuje výsledky vyhledávání v Yandex. Pro tyto účely má hluboce skrytý VIC, který je obdobou PageRanku. Objem výpočtů z Yandexu je tedy také značný.

Rekurzivní výpočetní algoritmus založený na váze odkazu ukázal, že dva weby, které na sebe mají odkazy, mají nerealisticky vysokou váhu. Proto ihned po zveřejnění algoritmu PageRank začaly optimalizátory podporovat rekurzivní spojování. Provedené experimenty potvrdily, že použitá metoda má efektivní výsledek.

Komentář k tomuto článku:

Pro komentování se prosím zaregistrujte.

Rekurzivní algoritmus

Rekurze- metoda definování třídy objektů nebo metod tak, že se nejprve určí jeden nebo více (obvykle jednoduchých). základní případy nebo metody a poté z nich definovat pravidlo pro konstrukci definované třídy, která přímo nebo nepřímo odkazuje na tyto základní případy.

Jinými slovy, rekurze je způsob, jak obecně definovat objekt nebo akci prostřednictvím sebe sama, pomocí dříve definovaných soukromých definic. Rekurze se používá, když lze identifikovat sebepodobnost problému.

Příklady

Algoritmus pro pohyb věže, algoritmus přesune požadovaný počet disků ze „zdrojové“ pyramidy do „úkolové“ pyramidy pomocí „náhradní“ pyramidy.

Pokud je počet disků jeden, pak:

• Přesuňte disk ze zdroje do úlohy

Jinak:

• Rekurzivně přesuňte všechny disky kromě jednoho ze zdroje na náhradní, přičemž úlohu použijte jako náhradní
• Přesuňte zbývající disk ze zdroje do úlohy
• Přesuňte všechny disky ze skladu do úlohy pomocí zdroje jako zásoby

Rekurze v programování

Funkce

Třída prvek_seznamu_seznamu (prvek_seznamu_seznamu *další; /* odkaz na další prvek stejného typu */ int data; /* nějaké údaje */ );

Rekurzivní struktura dat často diktuje použití rekurze ke zpracování dat.

Rekurze ve fyzice

Klasickým příkladem nekonečné rekurze jsou dvě zrcadla umístěná proti sobě: tvoří dva koridory slábnoucích odrazů zrcadel.

Dalším příkladem nekonečné rekurze je efekt samobuzení (kladná zpětná vazba) v elektronických zesilovacích obvodech, kdy signál z výstupu jde na vstup, je zesílen, jde zpět na vstup obvodu a je opět zesílen. Zesilovače, pro které je tento provozní režim standardní, se nazývají samooscilátory.

Rekurze v lingvistice

Schopnost jazyka generovat vnořené věty a konstrukce. Základní nabídka kočka snědla myš lze rozšířit pomocí rekurze jako Váňa uhodla, že kočka snědla myš, pak jako Káťa ví, že Váňa uhodla, že kočka snědla myš a tak dále. Rekurze je považována za jednu z lingvistických univerzálií, to znamená, že je charakteristická pro jakýkoli přirozený jazyk (i když v poslední době se možná absence rekurze v jednom z jazyků Amazonie - Pirahã, kterou si všiml lingvista D. Everett bylo aktivně diskutováno). Rekurze v lingvistice, její odrůdy a nejcharakterističtější projevy v ruském jazyce jsou popsány v článku E.A. Lodatka „Rekurzivní lingvistické struktury“ (viz: Rekurzivní lingvistické struktury)

Citáty

Humor

Většina vtipů o rekurzi je o nekonečné rekurzi, která nemá žádnou výstupní podmínku. Slavná rčení: „Abyste porozuměli rekurzi, musíte nejprve porozumět rekurzi“, „Abyste něco udělali, musíte něco udělat“, „K přípravě salátu potřebujete: okurky, rajčata, salát“. Velmi oblíbený vtip o rekurzi, připomínající heslo ze slovníku:

Několik příběhů Stanislawa Lema je věnováno (možným) incidentům s nekonečnou rekurzí:

• Příběh o Ion the Quiet „Čtrnáctá cesta“ z „Hvězdných deníků Iyon the Quiet“, ve kterém hrdina postupně přechází od článku o sepulki k článku o sepulaci, odtud k článku o sepulcarii, který opět obsahuje odkaz na článek „sepulki“.
• Příběh o inteligentním stroji, který měl dostatek inteligence a lenosti postavit podobný, aby vyřešil daný problém, a řešení mu svěřil (výsledkem byla nekonečná rekurze, kdy každý nový stroj postavil podobný a úkol delegoval na to).

Ruská lidová pohádková píseň „Kněz měl psa...“ je příkladem rekurze:

Kněz měl psa, miloval ho,
Ona snědla kus masa, on ji zabil,
Zakopaný v zemi
Titulek napsal:

„Kněz měl psa, miloval ji, snědla kus masa, zabil ji, zakopal ji do země, nápis byl napsán: „Kněz měl psa, miloval ji, snědla kus maso, zabil ji, pohřbil ji do země, nápis napsal: ...

Viz také

• Opakující se sekvence (návratová sekvence)

Odkazy

• Thomas H. Corman, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein Algoritmy: konstrukce a analýza = ÚVOD DO ALGORITHMŮ. - 2. vyd. - M.: "Williams", 2006. - S. 1296. - ISBN 0-07-013151-1

Nadace Wikimedia.

2010.

Podívejte se, co je „rekurzivní algoritmus“ v jiných slovnících: rekurzivní algoritmus

- rekursyvusis algoritmas statusas T sritis automatika atitikmenys: angl. rekurzivní algoritmus vok. rekursiver Algorithmus, m rus. rekurzivní algoritmus, m pranc. algorithme récursif, m … Automatikos terminų žodynas rekurzivní řídicí algoritmus

- rekursyvusis valdymo algoritmas statusas T sritis automatika atitikmenys: angl. recursive control algorithm vok. rekursiver Regelungs od. Steuerungs algoritmus, m rus. rekurzivní řídicí algoritmus, m pranc. algorithme de réglage récurrent, m … Automatikos terminų žodynas

Toto je algoritmus pro řazení prvků v seznamu. Pokud má položka seznamu více polí, pole, které slouží jako kritérium řazení, se nazývá klíč řazení. V praxi se jako klíč často používá číslo a v jiných oblastech... ... Wikipedie

Rekurzivní akronym Zkratka (někdy backronym), která odkazuje sama na sebe. Mezi počítačovými hackery se stalo tradičním volit zkratky a zkratky, které na sebe nepřímo nebo přímo odkazují. Jeden z prvních příkladů... ... Wikipedie

- (anglicky: Recursive descent parser) algoritmus analýzy implementovaný vzájemným voláním procedur analýzy, které vyhovují pravidlům bezkontextové gramatiky nebo BNF. Aplikace pravidel postupně, zleva doprava... Wikipedie

Rekurzivní metoda pro vytvoření řezné sítě pro rozdělení více 2D polygonů obsahujících ostrůvky na oblasti bez ostrůvků. Lze použít v geografických informačních systémech k převodu ostrovních polygonů na neostrovní. Odkaz? ... Wikipedie

Algoritmy pro vyhledávání v grafu A* B* Algoritmus Bellmana Forda Obousměrné vyhledávání Algoritmus Dijkstra Algoritmus Johnsona Algoritmus Johnsona Hledání do šířky Hledání napřed do hloubky Hledání s omezenou hloubkou Hledání s první nejlepší shodou Algoritmus Floyda Warshalla Hledat... ... Wikipedia

Tento termín má jiné významy, viz Ppm. PPM (Prediction by Partial Matching) je adaptivní statistický bezztrátový algoritmus komprese dat založený na kontextovém... ... Wikipedia

Funkce: rekurzivně dané funkce ve své definici obsahuje zejména sebe, funkce definovaná rekurentním vzorcem je rekurzivní. V jednom výrazu tedy můžete poskytnout nekonečnou sadu způsobů, jak vypočítat funkci, definovat mnoho objektů prostřednictvím sebe pomocí dříve specifikovaných soukromých definic.

Data

Struktura element_of_list ( element_of_list * next; /* odkaz na další prvek stejného typu */ int data;

Rekurzivní struktura dat často diktuje použití rekurze ke zpracování dat.

/* nějaké údaje */ );

Ve fyzice

Dalším příkladem nekonečné rekurze je efekt samobuzení (kladná zpětná vazba) v elektronických zesilovacích obvodech, kdy signál z výstupu jde na vstup, je zesílen, jde zpět na vstup obvodu a je opět zesílen. Zesilovače, pro které je tento provozní režim standardní, se nazývají samooscilátory.

Klasickým příkladem nekonečné rekurze jsou dvě zrcadla umístěná proti sobě: tvoří dva koridory klesajících odrazů zrcadel.

V lingvistice kočka snědla myš Schopnost jazyka generovat vnořené věty a konstrukce. Základní nabídka" Váňa uhodla, že kočka snědla myš, pak jako Káťa ví, že Váňa uhodla, že kočka snědla myš» lze rozšířit pomocí rekurze jako a tak dále. Rekurze je považována za jednu z lingvistických univerzálií, to znamená, že je charakteristická pro jakýkoli přirozený jazyk. V poslední době se však aktivně diskutuje o možné absenci rekurze v jednom z jazyků Amazonie - Pirahã, což zaznamenal lingvista Daniel Everett () .

angličtina

V kultuře

Většina vtipů o rekurzi se týká nekonečné rekurze, ve které neexistuje žádná výstupní podmínka, například slavné rčení: „Abyste pochopili rekurzi, musíte nejprve pochopit rekurzi.

Několik příběhů Stanislawa Lema je věnováno (možným) incidentům s nekonečnou rekurzí:

• Velmi oblíbený vtip o rekurzi, připomínající heslo ze slovníku:

příběh o Ion the Quiet „Čtrnáctá cesta“ z „Hvězdných deníků Iyon the Quiet“, ve kterém hrdina postupně přechází od článku o sepulci k článku o sepulaci, odtud k článku o sepulkarech, ve kterém je je opět odkaz na článek „sepulki“:
Našel jsem následující stručné informace:
„SEPULKI jsou důležitým prvkem civilizace Ardritů (q.v.) z planety Enteropia (q.v.). Viz SEPULCARIA."
Postupoval jsem podle této rady a četl:
"SEPULCARIA - zařízení pro sepulaci (viz)."
Hledal jsem "Sepulenia"; stálo to:

„SEPULACE je obsazení Ardritů (q.v.) z planety Enteropia (q.v.). Viz SEPULS.”

• Příběh z „Kyberiády“ o inteligentním stroji, který měl dostatek inteligence a lenosti postavit podobný, aby vyřešil daný problém, a svěřil mu řešení (výsledkem byla nekonečná rekurze, kdy každý nový stroj postavil podobný a delegoval na něj úkol).
• Rekurzivní zkratky: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor) atd.

Viz také

• Návratová sekvence

Poznámky

Nadace Wikimedia.

Podívejte se, co je „Rekurze“ v jiných slovnících:

Návrat, opakování Slovník ruských synonym. rekurzivní podstatné jméno, počet synonym: 1 ... Slovník synonym

rekurze- - [] rekurze V obecném smyslu výpočet funkce pomocí specifického algoritmu. Příklady takových algoritmů jsou opakující se vzorce, které odvozují výpočet daného termínu... ... Technická příručka překladatele

Rekurze- v obecném smyslu výpočet funkce pomocí specifického algoritmu. Příkladem takových algoritmů jsou opakující se vzorce, které odvozují výpočet daného členu posloupnosti (nejčastěji numerického) z výpočtu několika předchozích ... Ekonomicko-matematický slovník

Rekurze- Terapeutický vzorec, ve kterém se vezme nějaký stav nebo kritérium formulované v původním prohlášení a aplikuje se na samotný výrok. Například: Nemám čas. Kolik času jste museli strávit, abyste se ujistili, že... ... Skvělá psychologická encyklopedie

Metoda určování funkcí, která je předmětem studia v teorii algoritmů a dalších odvětvích matematiky. logika. Tato metoda se již dlouho používá v aritmetice k určení číselných posloupností (progrese, Fibonacciho čísla atd.).... ... Matematická encyklopedie

rekurze- (pozadí) (lat. recursio návrat). Jedna ze tří fází artikulace zvuku, odsazení. Převedení řečových orgánů do klidného stavu nebo zahájení artikulování další hlásky. Ve slově zbytek se rekurze (odsazení) při artikulaci [t] může překrývat ... ... Slovník lingvistických pojmů T.V. Hříbě

Z latinského recursio (návrat). Obecně je to název pro proces opakování prvků „sobě podobným způsobem“.

Pozoruhodným příkladem rekurze je hnízdění panenek. Rekurzivní definice: "Hnízdící panenka je odnímatelná dutá dřevěná panenka obsahující uvnitř menší panenku." Toto je v ruštině rekurze. A nebýt limitu schopností mistrů, ideální matrjoška by šla hluboko do sebe až na atomovou úroveň. Nebo ještě hlouběji. Lefty prostě neměl dostatečně silný malý rozsah. Horní hranice je také teoreticky neomezená, ale baobaby vhodné velikosti na naší planetě nerostou. Obecně platí, že z technických důvodů musí být rekurze konečná.

V programování (stejně jako v matematice) je rekurze proces volání samotné funkce (přímá rekurze) nebo volání funkce B zevnitř funkce A, která zase obsahuje volání funkce A (nepřímá nebo vzájemná rekurze). Rekurzivní volání samozřejmě musí mít vyhovující podmínku ukončení, jinak se program zasekne, jako v nekonečné smyčce – ale na rozdíl od nekonečné smyčky se nekonečná rekurze zhroutí při přetečení zásobníku.

Příklad rekurze

Nejotravnějším příkladem rekurze v matematickém programování je výpočet faktoriálu. Neměňme naše slavné tradice. Pro ty, kteří to ještě nevzali: N! (faktoriál N) je součin všech přirozených čísel od jedné do N (faktoriál nuly je 1).
Můžete hloupě násobit čísla od 1 do N ve smyčce. Nebo můžete sestavit funkci factorial(n), která bude obsahovat podmínku a její volání. Pokud je n rovno jedné, pak funkce vrátí hodnotu 1, jinak vrátí hodnotu n vynásobenou faktoriálem(n-1).
Skicování v PHP

Funkce faktoriál($n) ( if ($n == 1) ( return 1; ) else ( return intval($n * factorial($n - 1)); ) )

Praktické aplikace rekurze

"No, proč je to tady potřeba?" - netrpělivý mladý čtenář se nás zeptá - "Vědecké nesmysly, nudnost, všemožné faktoriály... Ale prakticky, proč aplikovat tuto rekurzi?"
"Černému oku webového programování," odpovíme bez váhání. A hned to zdůvodníme.

Ve skutečnosti existuje mnohem více využití rekurze ve webovém programování, než se zdá. Protože rekurze je možná jediný způsob, jak procházet jakoukoli stromovou strukturou, když není předem známa její velikost ani hloubka vnoření. Mimochodem, sestavení a procházení grafů se bez něj také neobejde. To je klasika, pánové – zkuste nějaký jiný způsob, jak hledat potřebné soubory v unixovém adresářovém stromu, a hned vám bude jasné, že bez rekurze se nikam nedostanete.

Zkuste se bez toho obejít vytvořením mapy webu s hierarchickou strukturou sekcí ve formě vnořených seznamů. Raději byste se oběsili, než abyste jej postavili, pokud předem přesně nevíte, na kolik úrovní je omezena hloubka hnízdění. A i když víte, ale zkuste se obejít bez rekurze, pak místo jednoduché, transparentní a bezpečné funkce postavíte těžkopádnou softwarovou „polici o berlích“. A až skončíte a utřete si zpocené čelo, dojde vám chmurná životní pravda: pokud změníte hloubku hnízdění, vaše rozmetací struktura okamžitě přestane správně fungovat. Proto je nepravděpodobné, že jej budete moci použít kdekoli jinde.

Rekurze ve vyhledávačích

Ano, je to tak. Vyhledávače také nemají kam uniknout před rekurzí. Od doby, kdy byl zaveden zvyk měřit autoritu webu (dokumentu) počtem odkazů, se vyhledávače dostaly do rekurzivní pasti a nechaly je v ní bloudit navždy (to je upřímné přání autora). Odkaz „váha“ webu se skládá z malých kousků „váhy“ ze všech, kteří na něj odkazují. Chcete-li vypočítat tuto váhu pro A, na kterou se vztahují B, C a D, musíte vypočítat jejich váhu, kterou zase přenášejí všemožní ostatní, jejichž váhu je také třeba vypočítat... a tak dále v celé síti zohledněny ve vyhledávači. Zcela rekurzivní problém. A vy říkáte, že je to úplná teorie. Nejskutečnější praxe.

Rekurzivní PageRank společnosti Google

Tvůrci Google zveřejnili svůj základní algoritmus pro výpočet PageRanku již dávno. A bez ohledu na to, jak se od té doby změnil, bez ohledu na to, kolik vylepšení k němu přibylo, základ zůstává stejný. Neexistuje způsob, jak zjistit, kolik hodnocení PageRank stránka B předává jako odkaz na stránku A, dokud nespočítáme, kolik hodnocení PageRank stránka B obdržela od všech ostatních stránek, které na ni odkazovaly, a to nelze zjistit, dokud nespočítáme PageRank těch stránek... budeme pokračovat? Pravděpodobně již není potřeba. Je to opět Její Veličenstvo Rekurze .

Encyklopedický YouTube

• 1 / 5

  V matematice má rekurze co do činění s metodou definování funkcí a číselných řad: rekurzivně definované  funkce určuje svou hodnotu voláním sebe sama s jinými argumenty. V tomto případě jsou možné dvě možnosti:

  e = 2 + 2 2 + 3 3 + 4 4 + … = 2 + f (2) (\displaystyle e=2+(\cfrac (2)(2+(\cfrac (3)(3+(\cfrac) 4)(4+\ldots ))))))\;=2+f(2)), Kde f (n) = n n + f (n + 1) (\displaystyle f(n)=(\cfrac (n)(n+f(n+1)))) Přímý výpočet pomocí výše uvedeného vzorce způsobí nekonečnou rekurzi, ale lze prokázat, že hodnota f(n) má s rostoucím n sklon k jednotě (proto je i přes nekonečnost řady konečná hodnota Eulerova čísla ). Pro přibližný výpočet hodnoty e stačí uměle omezit hloubku rekurze na nějaké předem určené číslo a po jejím dosažení ji použít f (n) (\displaystyle f(n)) jednotka.

  Dalším příkladem rekurze v matematice je číselná řada daná rekurentním vzorcem, kdy každý další člen řady je vypočítán jako výsledek funkce n předchozích členů. Pomocí konečného výrazu (což je kombinace opakujícího se vzorce a sady hodnot pro prvních n členů řady) lze tedy zadat definici nekonečné řady.

  Struktura element_seznamu ( element_of_list * next ; /* ukazatel na další prvek stejného typu */ int data;

  /* nějaké údaje */ );