Rekursi adalah salah satu hal yang sulit diterima oleh pikiran saya. Apa maksudmu suatu fungsi dapat memanggil dirinya sendiri? Apa? Pikiran meledak! Rekursi dalam ilmu komputer didefinisikan sebagai berikut dari wikipedia.

'rekursi adalah metode pemecahan masalah di mana solusinya tergantung pada solusi untuk contoh yang lebih kecil dari masalah yang sama. Masalah seperti itu umumnya dapat diselesaikan dengan iterasi, tetapi ini perlu mengidentifikasi dan mengindeks instance yang lebih kecil pada waktu pemrograman. Rekursi memecahkan masalah rekursif tersebut dengan menggunakan fungsi yang memanggil dirinya sendiri dari dalam kode mereka sendiri.'

Rekursi adalah salah satu ide sentral dari ilmu komputer tetapi terlebih lagi dalam algoritma. Pada artikel ini saya akan berbicara tentang rekursi yang berkaitan dengan algoritma. Biasanya ada dua cara untuk menyelesaikan algoritma, iteratif atau rekursif. Rekursi digunakan dalam algoritma traversal Dom, traversal Object/Hash, Depth-first search traversal (DFS), Breadth-first search traversal (BFS), dll.

Tumpukan panggilan:

Rekursi menggunakan apa yang dikenal sebagai tumpukan panggilan. Ketika suatu fungsi memanggil dirinya sendiri, ia masuk ke dalam tumpukan, dan ketika rekursi mengenai kasus dasar, ia keluar dari tumpukan satu per satu. Stack adalah struktur data yang menggunakan first in, last out (LIFO). Ini mirip dengan piring susun, saat mengeluarkannya Anda harus mengambilnya dari atas.

Kasus dasar:

Satu hal yang menakutkan jika Anda belum pernah mengalaminya adalah memasuki infinite loop dan tidak tahu cara menutupnya. Hal menakutkan lain yang terkait dengan itu adalah stack overflow. Apa yang terjadi adalah fungsi tersebut terus memanggil dirinya sendiri dan tidak pernah berhenti memanggil dirinya sendiri! Kiat pro: tekan ctrl c. Kesalahan stack overflow dapat terjadi dalam program komputer karena penggunaan memori yang berlebihan. Penggunaan memori yang berlebihan ini terjadi pada call stack, yaitu tempat penyimpanan informasi yang berkaitan dengan subrutin aktif dalam program. Tumpukan panggilan memiliki jumlah memori terbatas yang tersedia untuk itu. Ukurannya ditentukan oleh bahasa pemrograman, arsitektur, apakah multi-threading tersedia di CPU, dan berapa banyak memori yang tersedia. Selain itu, Anda akan menemukan kesalahan stack overflow jika Anda tidak memiliki kasus dasar dalam fungsi rekursi Anda, dan mungkin perlu pergi kestackoverflow.com untuk memeriksa apa artinya. Anda dapat memikirkan kasus dasar di mana panggilan berakhir/berhenti. Setelah Anda menekan kasus dasar Anda dapat bekerja mundur sampai Anda kembali ke panggilan fungsi awal.

Algo yang menggunakan rekursi

Mari kita jelajahi pertanyaan seperti apa yang diselesaikan secara rekursif. Salah satu yang mungkin sering Anda lihat adalah deret Fibonacci di mana setiap angka dalam deret tersebut adalah jumlah dari dua angka yang mendahuluinya. Jadi, urutannya adalah: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, dan seterusnya. Anda mungkin diminta untuk memecahkan nomor fib ke-n dan Anda mungkin ingin menggunakan rekursi untuk menyelesaikan masalah ini.

Deret Fibonacci

function fib(n){
  if (n <= 2) return 1;
  return fib(n-1) + fib(n-2);
}
console.log(fib(10))

function reverse(str){
 if(str.length <= 1) return str;
 return reverse(str.slice(1)) + str[0];
}
// reverse('awesome') // 'emosewa'