Rekurze je proces vymezování problému (nebo řešení problému) z hlediska (jednodušší verze) sám.

například můžeme definovat operaci „najít cestu domů“ jako:

  1. Pokud jste doma, přestaňte se pohybovat.

  2. udělejte jeden krok směrem k domovu.

  3. „najděte si cestu domů“.

zde je řešení, jak najít cestu domů, dva kroky (tři kroky). Za prvé, nejdeme domů, pokud už jsme doma., Za druhé, děláme velmi jednoduchou akci, která usnadňuje řešení naší situace. Nakonec předěláme celý algoritmus.

výše uvedený příklad se nazývá rekurze ocasu. To je místo, kde poslední příkaz volá rekurzivní algoritmus. Rekurze ocasu může být přímo přeložena do smyček.

Jak byste napsali rekurzivní „algoritmus“ pro nalezení Temple Square?

dalším příkladem rekurze by bylo nalezení maximální hodnoty v seznamu čísel. Maximální hodnota v seznamu je buď první číslo nebo největší ze zbývajících čísel., Zde je, jak budeme psát pseudokódu algoritmu:

Části Rekurzivní Algoritmus

Všechny rekurzivní algoritmy musí mít následující:

  1. Základní Případ (tj., kdy přestat)

  2. Pracovat na Základní Případ.

  3. Rekurzivní Volání (tj. říkáme)

„práce směrem k základní případ“ je místo, kde jsme, aby tento problém jednodušší (např., rozdělte seznam na dvě části, z nichž každá menší než původní). Rekurzivní volání je místo, kde používáme stejný algoritmus k vyřešení jednodušší verze problému., Základním případem je řešení „nejjednoduššího“ možného problému (například základní případ v problému „najít největší číslo v seznamu“ by byl, kdyby seznam měl pouze jedno číslo… a podle definice, pokud existuje pouze jedno číslo, je to největší).

jednoduchý příklad: přidání tří čísel

přidání tří čísel odpovídá přidání prvních dvou čísel a opětovnému přidání těchto dvou čísel.

(poznámka, v Matlabu lze volat funkci bez všech argumentů. Funkce nargin říká počítači, kolik hodnot bylo zadáno., Tak add_numbers(1) bude mít nargin 1; add_numbers(1,1) by nargin 2; add_numbers(1,1,1) by nargin 3.)

Identifikovat 3 části rekurzivní algoritmus:

Všechny rekurzivní algoritmus musí mít následující tři fáze:

Proč Rekurze Funguje

V rekurzivní algoritmus, počítač si „pamatuje“ každý předchozí stav problém. Tyto informace jsou“ drženy „počítačem na“ aktivačním zásobníku “ (tj.

každá funkce má svůj vlastní pracovní prostor na volání funkce.,

příklad bludiště:

zvažte obdélníkovou mřížku místností, kde každá místnost může nebo nemusí mít dveře na Severní, Jižní, východní a západní straně.

Jak se Vám najít cestu ven z bludiště? Zde je jeden možný „algoritmus“ pro nalezení odpovědi:

pro každé dveře v aktuální místnosti, pokud dveře vedou k východu, vezměte tyto dveře.

„trik“ zde je samozřejmě, jak víme, zda dveře vedou do místnosti, která vede k východu? Odpověď je, že ne, ale můžeme nechat počítač přijít na to pro nás.

jaká je rekurzivní část výše uvedeného algoritmu?, Jeho „dveře vedou z bludiště“. Jak můžeme vědět, jestli dveře vedou z bludiště? Víme, protože uvnitř další místnosti (procházející dveřmi) se ptáme na stejnou otázku, jak se dostaneme z bludiště?

co se stane, je počítač „pamatuje“ všechny „co ifs“. Co když vezmu první dveře, co když vezmu druhé dveře,co když vezmu další dveře atd. A pro všechny možné dveře se můžete pohybovat, počítač si pamatuje ty, co kdyby, a pro každé dveře poté, a poté, atd., až do konce.

zde je blízko ke skutečné implementaci kódu.,

otázka: Jaký je základní případ výše?

odpověď: (to byla triková otázka) v kódu není žádný základní případ. Na začátku je třeba zkontrolovat, zda je místnost východem. Pokud ano, žádná rekurze! 

  function success = find_way_out( maze, room ) if room is exit → return true room ← mark as visited % rest of code ... end

otázka: jak označíte místnost jako navštívenou?

odpověď: existují různé techniky. Pokud je místnost strukturou (nebo objektem), můžete do místnosti přidat směr navštíveného pole. (např. pokoj.navštívil = true;) pokud nepoužíváte objekty, můžete mít matici booleovských vlajek, která je stejná velikost / tvar jako bludiště a používat tyto hodnoty.,

otázka: jsou další problémy s výše uvedeným algoritmem?

Odpověď: odpověď lze nalézt, přemýšlet o tom následující otázku: Co by se stalo, kdyby bludiště, obří mřížku stejně velké obdélníkové místnosti, každá s dveřmi na každé zdi? Představte si, že jdete na sever přes první dveře, pak na východ přes vedlejší místnosti dveře, pak na jih přes ty pokoje dveře, a pak na západ přes ty pokoje dveře. Kde skončíš? Tam, kde jsi začal! Co je horší, můžete pokračovat v této smyčce navždy. Jak by tento problém vyřešil neohrožený dobrodruh?,

jedna odpověď na to je pomocí křídy a položením velkého X na podlahu každé místnosti, kterou zadáte. Když se tedy vrátíte do místnosti s X na podlaze, víte, že nemusíte vstoupit. V případě programu by měla být použita booleovská vlajka“ viděná“ nebo „navštívená“. Každý pokoj má vlajku. Každý pokoj začíná tím, že vlajka je nastavena na hodnotu false. Když navštívíte pokoj, nastavíte vlajku na true., A konečně, v „základní případ“ máte-line, jako jsou: 

  function success = find_way_out( maze, room ) % exit chack if room is visited → return false % rest of code ... end

Rekurze může být stejně dobře použita k počítačové algoritmy:

Některé Počítačové související příklady zahrnují: Přidání seznamu čísel, výpočet Fibonacciho posloupnost výpočet Faktoriálu, a Sudoku.

smyčky a rekurze ocasu

některé rekurzivní algoritmy jsou velmi podobné smyčkám. Tyto algoritmy se nazývají „rekurzivní ocas“, protože poslední příkaz v algoritmu je“ restartovat “ algoritmus. Tail rekurzivní algoritmy mohou být přímo přeloženy do smyček.