Rekurze

Rekurze je proces, který se vztahuje k předmětu tohoto procesu až k bodu, v tomto procesu. Jinými slovy, jedná se o přístup, jehož popis vede k opakování stejného pravidla. Následující případy tedy představují konkrétní případy rekurze:

V počítačové vědě

V informatice je definice určitých datových struktur , jako jsou seznamy nebo stromy , rekurzivní: zmiňuje definovaný typ dat. Například (viz obrázek) je binární strom buď prázdný, nebo uzel se dvěma menšími binárními stromy .

Kromě toho je funkce nebo více obecně algoritmus může obsahovat jeden nebo více volání k sobě, přičemž v tomto případě se uvádí, že jsou rekurzivní . Tato metoda se používá zejména ke zpracování rekurzivních datových struktur ak realizaci algoritmického paradigmatu „  rozděl a panuj  “.

Dva typy dat se mohou ve svých příslušných definicích navzájem odkazovat; podobně si mohou navzájem volat dva algoritmy. Mluvíme pak o křížové rekurzi nebo vzájemné rekurzi .

Stejně jako použití smyček umožňuje rekurze provádět řadu operací, které nejsou předem známy, protože je určeno vstupy programu; tyto dvě metody také umožňují psát programy, které se nekončí . Jazyk umožňující smyčky, stejně jako rekurze jazyka umožňuje, je obecně Turing-kompletní .

Rekurze je choulostivým bodem ve výuce informatiky, protože její přivlastnění si žákem vyžaduje dávku abstrakce.

Anglické rčení tak říká: „ Iterovat je lidské, opakovat je božské  “. Ve francouzštině můžeme přeložit jako „Iterace je lidská, ale rekurze je božská“

V lingvistice

Renomovaný americký lingvista Noam Chomsky mimo jiné tvrdí, že nedostatek horní hranice počtu gramatických vět a jejich délky (zůstávající v oblasti praktičnosti) je výsledkem rekurze přirozeného jazyka.

To je chápáno pomocí rekurzivní definice syntaktické kategorie, například věty. Věta může mít strukturu, ve které se za slovesem nachází vložená věta: Dorothy si myslí, že čarodějnice jsou nebezpečné , přičemž věta, která je nebezpečná, je ve větě, která je již přítomna. Větu lze tedy definovat rekurzivně (zhruba) jako něco, co má strukturu, která obsahuje podstatnou větu, sloveso a další (volitelnou) větu. Toto je opravdu speciální případ, kdy se projeví matematická definice rekurze.

Rekurze hraje důležitou roli nejen v syntaxi, ale také v sémantice přirozeného jazyka . Slovo a například lze na něj pohlížet jako na funkci, kterou lze použít na význam vět k vytvoření nových vět. To se také děje s ohledem na významy jmenných vět, verbálních, mimo jiné frázových tvarů. To platí také pro přechodná, nepřechodná nebo dokonce ditransitivní slovesa. Aby bylo možné poskytnout jedinou dostatečně flexibilní vyznačením, a je definována jednoduše jako mající možnost představuje argumenty přes jakékoliv smysluplné formě. To lze provést definováním a pro jednoduchý případ, ve kterém kombinujeme věty, a definováním dalších případů rekurzivně z hlediska jednoduchého případu.

Gramatika sanskrtu z Panini již používá rekurzi k V. th  století  před naším letopočtem. AD Budovy jsou v podstatě rekurzivní jazyky, například konstrukce podstatného jména: klíč od zámku na předních dveřích domu z ulice na konci vesnice . Práce provedená profesorem Danielem Everettem by však měla tendenci ukazovat na absenci rekurze v jazyce Pirahã .

Někteří autoři se domnívají, že schopnost budovat rekurzivní struktury je specifická pro lidské komunikační systémy, ale toto tvrzení je nyní zpochybňováno prací na poznávání zvířat.

Slovník (definiční slovník) je příkladem rekurze: každé slovo ve slovníku je definováno jinými slovy, která jsou sama definována jinými slovy ve stejném slovníku.

V umění

V oblasti umění se rekurzivní proces nazývá mise en abîme a nejvíce ho využívá umělec Maurits Cornelis Escher ; je známý svými pracemi inspirovanými rekurzí. Reklama také využívala rekurzi, díky níž se ve Francii proslavily La vache qui rit a Dubonnet .

V biologii

Rekurze je zvláště přítomná v biologii , zejména ve vzorcích rostlin a vývojových procesech. Tyto rozsivky mají obzvláště krásné rekurzivní struktury.

V matematice

Rekurzivně definovaná sekvence

Rekurzivní funkce

Funkce může být definována podle sebe. Známým příkladem je Fibonacciho posloupnost chápaná jako funkce , viz . Aby taková definice měla význam, musí vést k okamžitě vyhodnotitelným hodnotám: v případě Fibonacciho posloupnosti, kterou nastavíme, a .

Příklad: sněhová vločka Koch

Koch vločka je fraktální číslo pomocí jednoduchého rekurze procesu.

V počáteční fázi máme rovnostranný trojúhelník. Dalším krokem je konstrukce tří rovnostranných trojúhelníků, přičemž jako základ se použije střední třetina každé strany počátečního trojúhelníku. Opakováním tohoto procesu nejprve pro tři nové trojúhelníky, poté tolikrát, kolik chcete, získáte sněhovou vločku Koch.

Rekurze, nepředvídatelnost a odkaz na sebe

Samotné definování konceptu označili logici a matematici za nepředvídatelnost a nemělo by být zaměňováno s rekurzí, i když je tomu podobné. Mluvíme také o sebereferenci . Existují logické nepředvídatelné teorie (jako systém F kvůli Jean-Yves Girardovi ), ale je třeba je definovat opatrně, pokud chceme zachovat jejich soudržnost, protože paradoxy nejsou daleko. V teorii množin tedy Russellův paradox ukazuje, že nemůže existovat sada složená ze sad, které neobsahují samy sebe (popularizované jako paradox holičství , ve skutečnosti „pokud je holič tím, kdo holí ty, kdo se neholí sami, kdo se holí holič? “). Stále v teorii množin axiom nadace zakazuje množiny, které obsahují samy sebe.

Právě na těchto principech mají hrát záludní počítačoví vědci definici rekurzivních zkratek, které nic nedefinují, protože jsou nepředvídatelné a nesouvislé. Podobně následující aforismus: „Abychom porozuměli principu rekurze, je třeba nejprve pochopit princip rekurze“ , je nepředvídatelný a lze jej považovat za prosbu o vyúčtování .

V systémech, neurovědách a komplexních systémech, poznání

Edgar Morin velmi často používal koncept rekurze, kterou nazývá rekurzivní smyčka , zejména ve svých dílech tvořících metodu . Rekurzivní smyčka má kruhovou kauzalitu: důsledek působí na příčinu účinku. Příkladem rekurzivní smyčky je plasticita mozku, tvořená plasticitou neuronů a synaptickou plasticitou . Například: mozek má schopnost řídit sekvenci různých ovládacích svalů během prvního učení komplexního pohybu (golfový švih). Opakování gesta modifikuje neurální a synaptické sítě, které se tak stávají schopné nových schopností: učení gest pro účinky dané míči.

„  Princip organizace rekurze jde nad rámec principu zpětné vazby ( zpětné vazby ); jde nad rámec regulace pro vlastní produkci a sebeorganizaci . Jedná se o generativní smyčku, ve které jsou produkty a účinky samy producenty a původci toho, co je produkuje. [...] lidských jedinců produkují společnost a skrze jejich interakce, ale společnost, jako rozvíjející celek , vytváří lidstvo těchto jedinců tím, že jim s jazykem a kulturou“ .

V 6. ročníku opusu metodou , Edgar Morin navrhuje etický rekurzi.

"Sebezkoumání, sebekritika a psychická gymnastika se shodují v rekurzivní praxi hodnocení našich hodnocení, posuzování našich úsudků a kritiky naší kritiky." […]

Etická rekurze také smyčky s porozuměním / vysvětlením (tj. Objektivní / subjektivní zkoumání): jakékoli vysvětlení musí být doplněno porozuměním, celé porozumění musí být doplněno vysvětlením.

A konečně, etická rekurze nás imunologicky posiluje proti naší tendenci přimět ostatní cítit se provinile a stát se obětním beránkem za naše chyby “.

Podívejte se také

Související články

externí odkazy

Poznámky a odkazy

  1. „  RECURSIVITÉ: Definice RECURSIVITÉ  “ na www.cnrtl.fr (přístup k 17. prosinci 2017 ) .
  2. Editions Larousse , „  Definitions: recursivity - Dictionary of French Larousse  “ , na www.larousse.fr (konzultováno 22. prosince 2017 ) .
  3. Dubonnet reklamy .
  4. V algoritmech se běžně používají rekurzivní algoritmy .
  5. Všimněte si, že systém wiki detekuje hypertextové odkazy, které odkazují na stránku, která je zmiňuje, a odstraňuje je, aby se zabránilo problémům se smyčkami pro roboty procházející stránky.
  6. (in) Matthias Hauswirth a The Education Column od Juraje Hromkoviče , „  Si vous-have rodiče, můžeš se naučit rekurzi.  ” , Bulletin of EATCS , sv.  3, n o  123,12. října 2017( číst online , konzultováno 17. prosince 2017 ).
  7. Pinker, Steven, 1954- , Jazykový instinkt: nová věda jazyka a mysli , Penguin,2008, 494  s. ( ISBN  978-0-14-103765-3 a 0-14-103765-2 , OCLC  277159505 , číst online )
  8. (in) Steven Pinker a Ray Jackendoff , „  Fakulta jazyků: co je na tom zvláštní?  » , Cognition , sv.  95, n O  2Březen 2005, str.  201–236 ( DOI  10.1016 / j.cognition.2004.08.004 , číst online , přistupováno 6. dubna 2020 )
  9. (in) Paul Portner a Barbara H. Partee , Formal Semantics , al.  "Základní čtení",1 st 01. 2002( ISBN  978-0-631-21541-7 , DOI  10.1002 / 9780470758335 , číst online )
  10. René Lemieux, „  Od Weltanschauung dobrého divocha ke kontroverzím MIT: Everett contra Chomsky  “ , Laboratoř sémiotické rezistence (přístup k 5. lednu 2016 ) .
  11. (in) A. Rey, P. a J. Perruchet Bundle, „  Centrum Integrované struktury jsou vedlejším produktem omezení asociativního učení a pracovní paměti: Důkazy od paviánů (Papio papio)  “ Cognition , 123, 180-184.
  12. Edgar Morin a Jean-Louis Le Moigne, Inteligence složitosti , Paříž, L'Harmattan ,1999, 332  s. ( ISBN  978-2-7384-8085-9 , číst online ) , s.  255, Pokračoval s mírnými modifikacemi Edgar Morin, "  Směrem k nové paradigma  ", Human Sciences , n o  47,Února 1995, str.  20-23.
  13. Edgar Morin, Metoda: Etika , t.  6, Prahová hodnota ,2004, 285  s. ( ISBN  978-2-7578-0183-3 ) , str.  120-121.