Rekursija

Kakao paciņa, uz kā attēlota sieviete, kura tur rokā tādu pašu paciņu, uz kuras atkal attēlota šī sieviete utt.

Rekursija ir process, kurā kaut kādi objekti tiek atkārtoti vai definēti pašlīdzīgā veidā (tātad, sarežģītākus reducējot uz vienkāršākiem, tos uz vēl vienkāršākiem utt.). Piemēram, ja divu spoguļu virsmas ir paralēlas viena otrai, tad atkārtotie attēli, kas rodas, ir bezgalīgas rekursijas veids. Rekursijas jēdzienam ir daudzas nozīmes atkarībā no zinātnes nozares, piemēram, sākot ar lingvistiku un beidzot ar loģiku. Visizplatītākie rekursijas pielietojumi ir matemātikā un datorzinātnē, kurās tā veido funkciju definēšanas metodi, kurā funkcija tiek definēta ar pašas definīciju. Konkrētāk, tas definē bezgalīgu skaitu ar gadījumiem (funkcijas vērtībām), izmantojot galīgu izteiksmi, kas dažu instanču gadījumā var atsaukties uz citām instancēm, bet tā, ka neveidojas cilpa vai bezgalīga ķēde ar atsaucēm. Termins tiek lietots arī vēl vispārīgāk, lai aprakstītu procesu ar pašlīdzīgā veidā atkārtojošiem objektiem.

Formālas rekursijas definīcijas

Matemātikā un datorzinātnē objektu vai metožu klasei ir rekursīvs raksturs, ja tos var definēt, izmantojot divas īpašības:

1. Ir vienkāršs bāzes gadījums (vai gadījumi)
2. Ir likumu kopa, kas reducē visus citus gadījumus uz bāzes gadījumu.

Piemēram, zemāk parādīta rekursīva definīcija personas priekštečiem:

• Kāda vecāki ir viņa priekšteči (bāzes gadījums).
• Priekšteči kāda priekštečiem ir arī kāda priekšteči (rekursijas solis).

Fibonači skaitļi ir klasisks rekursijas piemērs:

${\text{Fib}}(0)=0{\text{ (1. bāzes gadījums),}}$

${\text{Fib}}(1)=1{\text{ (2. bāzes gadījums),}}$

${\text{Visiem naturāliem }}n>1,~{\text{ Fib}}(n):={\text{Fib}}(n-1)+{\text{Fib}}(n-2).$

Daudzas matemātiskas aksiomas ir balstītas uz rekursīviem soļiem. Piemēram, naturālo skaitļu formāla definīcija ar Peano aksiomām var tikt aprakstīta kā: 1 ir naturāls skaitlis, un katram naturālajam skaitlim ir pēctecis, kurš ir arī naturāls skaitlis. Ar šo bāzes gadījumu un rekursīvo likumu var ģenerēt visu naturālo skaitļu kopu.