Úvodní stránka | Tato stránka v originále

Rekurze

Rekurze je způsob, jak specifikovat proces prostředky k sobě. Více přesně (a rozptýlit vzhled circularity v definici), “komplikované” příklady procesu jsou definovány v podmínkách “jednodušších” příkladů a “nejjednodušší” příklady jsou dávány výslovně.

Příklad rekurzivního obrazu.

Matematický lingvista Noam Chomsky podal důkaz to neomezené rozšíření jazyka takový jak Angličtina je možná jen rekurzivním zařízením vět prostoupení ve větách. Tak, talky malá dívka může říkat, “Dorothy, kdo se setkal se zlou čarodějnicí západu v Munchkin zemi kde její zlá čarodějnická sestra byla zabita, likvidoval ji s kbelíkem vody.” jasně, dvě jednoduché věty -- “Dorothy se setkal se zlou čarodějnicí západu v Munchkin zemi”, a “její sestra byla zabita v Munchkin zemi” -- moci být zasazený ve třetí větě, “Dorothy likvidoval ji s kbelíkem vody”, získat velmi talky větu.

1984 laureáta Nobelovy ceny v medicíně a fyziologii, Niels K. Jerne, používal Chomsky transformational-generativní gramatika model vysvětlit lidský imunitní systém, vyrovnat “součásti generativní gramatiky... s různými rysy struktur bílkoviny”. Titul Jerne je Stockholm Nobelova přednáška byla “generativní gramatika imunitního systému”.

Tady je jiný, možná jednodušší způsob, jak rozumět rekurzivních postupů:

  1. My jsme hotoví přesto? Jestliže tak, vrátit výsledky. Bez takový podmínka ukončení rekurze by pokračovala navždy.
  2. Jestliže ne, zjednodušit problém, řešit ty jednodušší problém (s), a sestavit výsledky do řešení pro originální problém. Pak vraťte to řešení.

Vtipnější ilustrace jde: “aby rozuměl rekurzi, jeden musí nejprve rozumět rekurzi.”

Nebo možná přesnější je sledování způsobené Andrewem Plotkinem - “jestliže vy už znáte co rekurze je, jen pamatovat si odpověď. Jinak, najít někoho kdo stojí blíže k Douglas Hofstadter než vy jste; pak žádat o něj nebo ji jaká rekurze je.”

Příklady matematických objektů často vymezily rekurzívně být funkce a soubory.

Tabulka s obsahem
1 rekurzívně definoval soubory
2 rekurzívně definované funkce
3 rekurzivní algoritmy
4 rekurzivní teorém
5 seznamu vztahů opakování nebo algoritmů
6 vidět také
7 další četby a odkazy

Rekurzívně definované soubory

Příklad: přirozená čísla

Kanonický příklad rekurzívně definovaného souboru je přirozená čísla:

0 je v N
jestliže n je v N, pak n+ 1 je v N
Přirozená čísla je nejmenší soubor uspokojující předchozí dvě vlastnosti.

Here's alternativní rekurzivní definice N:

0, 1 být v N;
jestliže n a n+ 1 být v N, pak n+ 2 je v N;
N je nejmenší soubor uspokojující předchozí dvě vlastnosti.

Příklad: Soubor opravdových dostupných problémů

Další zajímavý příklad je soubor všech pravdivý “dostupné” problémy v axiomatickém systému.

Tento soubor je volán ' opravdové dostupné problémy protože: v nonconstructive přístupech k založením matematiky, soubor opravdových problémů je větší než soubor rekurzívně postavil od axiómů a pravidel závěru. Viz též Godels _ Incompleteness _ teorém

(To potřeby být poukázaly na to určovat zda jistý objekt je v rekurzívně definovaný soubor není algoritmická úloha.)

Formální definice

(Vložit definici rekurzívně definovaného souboru tady)

Rekurzívně definované funkce

Funguje jehož domény mohou být rekurzívně definované moci být dané rekurzivní definice vzorovaný po rekurzivní definici jejich domény.

Kanonický příklad rekurzívně definované funkce je následující definice faktoriálové funkce f(n):

f(0) = 1
f(n) = n · f(n- 1) pro nějaké přirozené číslo n > 0

Daný tato definice, také volal vztah opakování, my cvičíme f(3) takto:

f(3) = 3 · f(3-1) = 3 · f(2) = 3 · 2 · f(2-1) = 3 · 2 · f(1) = 3 · 2 · 1 · f(1-1) = 3 · 2 · 1 · f(0) = 3 · 2 · 1 · 1 = 6
Další příklad je definice Fibonacci čísel.

Rekurzivní algoritmy

Obyčejná metoda zjednodušení má rozdělit problém na subproblems stejného typu. Jak technika programování je volána rozdělit se a podmanit si a je klíč k návrhu mnoha důležitých algoritmů jak studně jako bytí základní část dynamického programování.

Doslova všechny programovací jazyky v použití dnes dovolit přímou specifikaci rekurzivních funkcí a procedur. Když takový funkce je volána, počítač drží dráhu různých příkladů funkce tím, že používá hromadu. Naopak, každá rekurzivní funkce může být transformována do opakovací funkce tím, že používá hromadu.

Nějaká funkce, která může být ohodnocena počítačem může být vyjádřena v podmínkách rekurzivních funkcí, bez použití iterace, a naopak.

Opravdu, některé jazyky určené pro logické programování a funkční programování poskytují rekurzi jako jediné prostředky k opakování přímo dostupný programátorovi. Takové jazyky obecně dělají rekurzi ocasu jak účinný jako iterace, nechávat programátory vyjadřovat jiné struktury opakování (takový jak Schéma je mapa a pro) v podmínkách rekurze.

Rekurze je hluboce zasazená v teorii počítání, s teoretickou rovnocenností rekurzivních funkcí a Turing stroji u založení myšlenek na univerzálnost moderního počítače.

John Mccarthy' s fungovat, Mccarthy je 91 je jiný příklad rekurzivní funkce.

Rekurzivní teorém

V teorii množin, toto teorém garantuje, že rekurzívně určené funkce existují. Daný soubor X, element X a funkce f : X -> X, teorém říká, že to tam je jedinečná funkce F : N -> X (kde N označuje soubor přirozených čísel) takový to

F(0) =
F(n+ 1) = f(F(n))
pro nějaké přirozené číslo n.

Důkaz jedinečnosti

Vzít dvě funkce f a g domény N a codomain takový to:

f(0) =
g(0) =
f(n+ 1) = F(f(n))
g(n+ 1) = F(g(n))

kde je element . My chceme ukázat se jako to f = g. Dvě funkce jsou se rovnat jestliže oni:

i. mít se rovnat doménám/codomains;
ii. mít stejný grafický.

i. Hotový!
ii. Matematické přerušení: pro všechny n v N, f(n) = g(n)? (my budeme volat tuto podmínku, říkat, Eq (n)):
1.: Eq (0) iff f(0) = g(0) iff = a. hotový!
2.: nechaný n být element N. Předpokládat ten Eq (n) držení, my chceme ukazovat ten Eq (n+ 1) držení také, který je snadný protože: f(n+ 1) = F(f(n)) = F(g(n)) = g(n+ 1). Hotový!

Důkaz existence

My vymezíme F na nule, pak jeden a tak dále. Vymezit F(0) = ;

Nyní předpokládat, že F byl definován na všech číslech méně než se rovnat k n my vymezíme F(N+ 1) = f( F(N)). Si všimnout toho protože F(N) byl definován hypotézou a to f je funkce X k X tak strana pravé ruky je opravdu člen X a tak toto správná definice.

Jinak, a informally, F(N) je výsledek nanášení f k N časy.

Seznam vztahů opakování nebo algoritmy

Vztahy opakování jsou rovnice, které definují sebe rekurzívně. Některé specifické druhy vztahu opakování mohou být “řešené” dostat definici nonrecursive.

Nějaké obyčejné opakování vztahy jsou:

Viz též

Další četby a odkazy