En rekursiv definition eller en induktiv definition definierar en entitet i termer av sig själv (det vill säga rekursivt ), om än på ett användbart sätt. För att detta ska vara möjligt måste definitionen i varje givet fall vara välgrundad och undvika oändlig regression .
De flesta rekursiva definitioner har tre baser: en bas, ett induktivt uttryck och ett extremalt uttryck.
Skillnaden mellan en cyklisk definition och en rekursiv definition är att den senare måste ha basfall som uppfyller definitionen utan att definieras i termer av själva definitionen, och alla andra fall som omfattas av definitionen måste vara "mindre" ( närmare dessa baser fall som bryter rekursionen).
Däremot har en cyklisk definition inga basfall och definierar sig själv i termer av sig själv snarare än som en version av sig själv närmare basklassen. Detta leder till en ond cirkel . Så ett skämt som "Rekursiv definition: se rekursiv definition " är felaktigt: det är faktiskt en cyklisk definition.
Primtal kan definieras som:
Heltalet 2 är vårt basfall; att testa primaaliteten för ett större tal X kräver att vi känner till primaaliteten för varje heltal mellan X och 2, men varje sådant tal är närmare basfallet 2 än vad X är.
Jämna tal kan definieras som bestående av
Exempel: