Rekurzivní definice

Rekurzivní definice nebo induktivní definice definuje entitu z hlediska sebe sama (tj. rekurzivně ), i když užitečným způsobem. Aby to bylo možné, musí být definice v každém daném případě dobře podložená a vyhýbat se nekonečné regresi .

Většina rekurzivních definic má tři základy: základ, induktivní výraz a extremální výraz.

Rozdíl mezi cyklickou definicí a rekurzivní definicí je v tom, že rekurzivní definice musí mít základní případy , které splňují definici , aniž by byly definovány z hlediska definice samotné, a všechny ostatní případy, na které se definice vztahuje, musí být „méně“ ( blíže k těmto základním případům). případy, které přeruší rekurzi).

Na rozdíl od toho cyklická definice nemá žádné základní případy a definuje se sama o sobě spíše než jako verze sebe sama blíže základní třídě. To vede k začarovanému kruhu . Takže vtip jako "Rekurzivní definice: viz Rekurzivní definice " je nesprávný: je to vlastně cyklická definice.

Příklady rekurzivních definic

Prvočísla

Prvočísla lze definovat jako:

• 2 , nejmenší prvočíslo;
• každé kladné číslo, které není dělitelné žádným prvočíslem menším než je ono samo.

Celé číslo 2 je náš základní případ; testování primality jakéhokoli většího čísla X vyžaduje, abychom znali primálnost každého celého čísla mezi X a 2, ale každé takové číslo je blíže základnímu případu 2 než X.

Nezáporná sudá čísla

Sudá čísla lze definovat jako skládající se z

• 0 v množině N nezáporných sudých čísel (základní výraz)
• Pro jakýkoli prvek x v N je x+2 také v N (indukční výraz)
• N obsahuje pouze ty prvky, které jsou získány ze základního a induktivního výrazu (extrémní výraz)

Rekurzivní definice v informatice

Příklady:

• GNU znamená „GNU (je) Not Unix“ (nebo „GNU není Unix“).
• PHP je zkratka pro "PHP: Hypertext Preprocessor"
• YAML - "YAML není značkovací jazyk "

Viz také

• sepulki