Rekursiyon

Ang rekursiyon (sa Ingles ay recursion) ang proseso ng pag-uulit ng mga item sa paraang katulad sa sarili nito. Halimbawa, kung ang dalawang surpasiyo ng salamin ay eksaktong magka-paralelo sa isa't isa, ang mga magkakapatong na larawan na makikita ay isang anyo ng walang hanggang rekursiyon. Ang terminong ito ay may iba't ibang mga kahulugan na spesipiko sa iba't ibang mga larangan na sumasaklaw mula sa linggwistika hanggang sa lohika. Ang pinakakaraniwang aplikasyon ng rekursiyon ay sa matematika at agham pangkompyuter kung saan ito ay tumutukoy sa paraan ng paglalarawan (o paglikha) ng mga punsiyon kung saan ang ang punsiyong inilalarawan ay nilalapat sa loob ng sarili nitong depinisyon. Sa spesipikong paglalarawan, ito ay naglalarawan ng walang hanggang bilang ng mga instansiya (mga halaga ng punsiyon) gamit ang may hanggang ekspresyon na para sa ilang mga instansiya ay maaaring tumukoy sa ibang mga instansiya ngunit sa paraang paikot (loop) o walang hanggang kadena (chain) ng mga reperensiya ay mangyayari. Ang termino ay ginagamit rin sa pangkalahatan upang ilarawan ang proseso ng pag-uulit ng mga obhekto sa paraang tulad ng sarili nito.

Mga pormal na depinisyon ng rekursiyon

Sa matematika at agham pangkompyuter, ang klase ng mga obhekto o metodo (method) ay nagpapakita ng pag-aasal na rekursibo kung maaaring ilarawan ang mga ito sa dalawang katangian:

Ang simpleng kaso base (o mga kaso)
Isang pangkat ng mga patakaran na nagpapaliit ng lahat ibang mga kaso patungo sa isang kasong base.

Halimbawa, ang sumusunod ay isang rekursibong depinisyon ng mga ninuno ng isang tao:

Ang magulang ng isang tao ang ninuno ng isang tao(kasong base).
Ang mga magulang ng isang ninuno ang mga ninuno nito(hakbang na rekursiyon).

Ang sekwensiyang Fibonacci ang isang klasikong halimbawa ng rekursiyon:

Ang Fib(0) ay 0 [kasong base]
Ang Fib(1) ay 1 [kasong base]
Para sa lahat ng mga intedyer na n > 1: ang Fib(n) ay (Fib(n-1) + Fib(n-2)) [rekursibong depinisyon]

Maraming mga aksiomang matematikal ang nakabatay sa mga patakarang rekursibo. Halimbawa, ang pormal na depinisyon ng natural na bilang sa teoriya ng pangkat ang sumusunod: ang 1 ay isang natural na bilang at ang bawat natural na bilang ay may kahalili na isang ring natural na bilang. Sa pamamagitan ng kasong base at patakrang rekursibong ito, maaaring lumikha ng pangkat ng lahat ng mga natural na bilang.

Ang mga obhektong matematikal na inilalarawang rekursibo ay kinabibilangan ng mga punsiyon, pangkat at lalo na ang fractal.