Konsep Rekursif & Fibonacci

Pada pemrograman, rekursif adalah sebuah fungsi dengan konsep memanggil dirinya sendiri, biasanya digunakan untuk algoritma pengurutan/sorting, pemrograman dinamis, dan untuk membetuk struktur parent-child seperti struktur direktori atau drop-down. Berikut contoh implementasi sederhana rekursif tak menentu, sehingga dapat mengakibatkan terjadinya infinite-loop yang menyebabkan penggunaan resource secara terus menerus. Meskipun demikian kejadian ini dapat memicu terjadinya interrupt/trap/exception dengan memberikan pesan seperti Maximum call stack size exceeded, yang berarti tumpukan pemanggilan fungsi tersebut telah mencapai batas maksimal yang dijalankan padaengine PHP. Tentunya penggunaan exception ini sangat diperlukan untuk melindungi penggunaan resource komputasi secara berlebihan, sehingga tidak menganggu program/aplikasi lainnya.

Gambar Analogika Diagram Recursif. (Sumber: https://study.cs50.net/recursion, 2018)

Contoh implementasi diagram rekursif yang dapat menyebabkan infinite-looping kedalam bahasa pemrograman PHP.

	function countDown($number) {
		echo $number . '<br/>';
	  	countDown($number - 1);
	}
	countDown(5);

Berikut potongan output dari rekursif infinite-looping pada program diatas yang dijalankan pada Web Browser Chrome.

	5
	4
	3
	2
	1
	0
	-1
	-2
	-3
	-4
	-5
	-6
	.
	.
	.
	RangeError: Maximum call stack size exceeded (Chrome)

Contoh penggunaan rekursif yang paling terkenal adalah perhitungan angka fibonacci. Secara sederhana angka fibonacci adalah deret bilangan yang susunan angkanya merupakan penjumlahan dari dua angka sebelumnya, misal dua deret angka awalannya adalah 0 dan 1, maka deret angka selanjutya adalah 1, 2, 3, 4, 5, 6, dan seterusnya.

Gambar Rekursif Fibonacci. (Sumber: https://levelup.gitconnected.com/a-second-thought-on-recursion-6575efeb2934)

Pembahasan lebih lanjut mengenai deret fibonacci sangatlah menarik, karena tidak terlepas dari membandingkan angka satu dengan angka lainnya, sehingga terciptanya suatu hubungan, dan hal ini disebut dengan golden rasio, namun pembahasan mengenai hal ini kita lewatkan terlebih dahulu.

Gambar Persamaan Fibonacci. (Sumber: https://levelup.gitconnected.com/a-second-thought-on-recursion-6575efeb2934)

Berikut ini implementasi dari persamaan fibonacci gambar diatas kedalam kode program menggunakan PHP.

	function Fibonacci($number) { 
	      
	    // if dan else if berikut digunakan untuk membuat dua angka pertama 
	    if($number == 0) return 0;     
	    else if($number == 1) return 1;     
	      
	    // Fungsi rekursif dipanggil untuk menghitung angka selanjutnya
	    return (Fibonacci($number-1) +  Fibonacci($number-2)); 
	} 
	  
	$number = 10; // variabel pengendali
	for ($counter = 0; $counter < $number; $counter++) {
	    echo Fibonacci($counter) . ' ';
	     
	}

Berikut ini output dari program rekursif fibonacci diatas yang dijalankan pada Web Browser Chrome.

	0 1 1 2 3 5 8 13 21 34

Kesimpulan

Rekursif adalah sebuah cara elegan untuk menyelesaikan beberapa masalah dalam pemrograman. Rekursif juga merupakan salah satu kemampuan fundamental yang diharapkan sudah dikuasai oleh teman-teman yang ingin terjun ke dunia pemrograman. Maka tak heran, jika beberapa pertanyaan terkait rekursif kerap muncul ketika kita melakukan coding interview di perusahaan teknologi.