Rekursiv definition

En rekursiv definition eller en induktiv definition definerer en enhed ud fra sig selv (det vil sige rekursivt ), omend på en nyttig måde. For at dette er muligt, skal definitionen i et givet tilfælde være velbegrundet og undgå uendelig regression .

De fleste rekursive definitioner har tre baser: et grundlag, et induktivt udtryk og et ekstremalt udtryk.

Forskellen mellem en cyklisk definition og en rekursiv definition er, at sidstnævnte skal have basistilfælde, der opfylder definitionen uden at være defineret i forhold til selve definitionen, og alle andre tilfælde, der er omfattet af definitionen, skal være "mindre" ( tættere på disse basis ). tilfælde, der bryder rekursionen).

I modsætning hertil har en cyklisk definition ingen basistilfælde og definerer sig selv ud fra sig selv snarere end som en version af sig selv tættere på basisklassen. Dette fører til en ond cirkel . Så en joke som "Rekursiv definition: se rekursiv definition " er forkert: det er faktisk en cyklisk definition.

Eksempler på rekursive definitioner

Primtal

Primtal kan defineres som:

• 2 , det mindste primtal;
• hvert positivt tal, der ikke er deleligt med et primtal mindre end sig selv.

Heltallet 2 er vores basistilfælde; at teste primaliteten af ​​et hvilket som helst større tal X kræver, at vi kender primaliteten af ​​hvert heltal mellem X og 2, men hvert sådant tal er tættere på grundtilfældet 2, end X er.

Ikke-negative lige tal

Lige tal kan defineres som bestående af

• 0 i sættet N af ikke-negative lige tal (grundlæggende udtryk)
• For ethvert element x i N er x+2 også i N (induktivt udtryk)
• N indeholder kun de elementer, der er opnået fra basis- og induktivt udtryk (ekstremt udtryk)

Rekursive definitioner i datalogi

Eksempler:

• GNU står for "GNU (er) Not Unix" (eller "GNU's Not Unix").
• PHP står for "PHP: Hypertext Preprocessor"
• YAML - "YAML Ain't Markup Language "

Se også

• sepulki