Stack Overflow??
Mencoba untuk menjelaskan Stack Overflow menurut pemahaman pribadi :D
Kalau di Java, ada tipe exception yang bernama StackOverflowException
. Exception jenis ini akan dilemparkan oleh JVM ketika pada pengeksekusian suatu kode program mengalami sesuatu yang bernama Stack Overflow. Nah sebenarnya, apa itu Stack Overflow?
Stack overflow adalah situs buat tanya-tanya masalah codingan, dan sumber source code buat di copas di tugas kuliah :p
Eh, bukan itu ya.. Baiklah, akan dibahas satu per satu.
Secara bahasa, stack overflow artinya stack nya meluap. Kepenuhan. Nah mengapa bisa kepenuhan? Penyebab stack overflow yang paling kentara adalah ketika ada suatu function yang memanggil dirinya sendiri (rekursif) tanpa henti. Biasanya hal ini terjadi ketika fungsi rekursif tidak dapat mencapai base case yang diinginkan supaya fungsi rekursif berhenti untuk memanggil dirinya sendiri.
Jadi, apa hubungannya infinite recursive dan stack overflow?
Method Call Stack
Sebelum membahas call stack, kita bahas sedikit dulu tentang struktur data stack.
Stack yang berarti tumpukan adalah suatu struktur data yang menerapkan prinsip LIFO (Last In, First Out). Jadi, data yang dimasukkan ke dalam stack terakhir kali (diletakkan di paling atas tumpukan), merupakan data yang nantinya akan keluar lebih dulu.
Kalau belum paham silakan bayangkan ketika akan mengambil karung semen dari tumpukan karung yang berisi 20 karung 😂
Ketika method, function, procedure atau istilah lain yang serupa dipanggil, maka informasi terkait method yang sedang dipanggil akan dimasukkan dalam call stack. Tiap data yang diproses dalam method tersebut akan dimasukkan ke dalam stack frame. Jadi isinya call stack itu adalah beberapa stack frame yang menyimpan informasi terkait parameter method/function maupun data yang diolah didalam method/function.
Misal ada sebuah Java snippet dibawah
public class Main {static int calculateFactorialNumber(int number) {
return (number == 1) ? 1 : number * calculateFactorialNumber(number - 1);
}public static void main(String[] args) {
int result = calculateFactorialNumber(5);
}
}
Proses eksekusi rekursif diatas adalah sebagai berikut
cfn(5) = 5 * cfn(4)
cfn(4) = 4 * cfn(3)
cfn(3) = 3 * cfn(2)
cfn(2) = 2 * cfn(1)
cfn(1) = 1so..cfn(1) = 1
cfn(2) = 2 * 1 = 2
cfn(3) = 3 * 2 = 6
cfn(4) = 4 * 6 = 24
cfn(5) = 5 * 24 = 120
Mengapa tidak terjadi infinite recursion? Karena ia telah memenuhi base case yang mana ketika number = 1
, maka fungsi rekursif akan berhenti memanggil dirinya sendiri (mengembalikan nilai 1), dan stack frame tersebut akan dihapus dari call stack, dan pemanggilan yang dilakukan sebelum base case akan diselesaikan sampai mendapatkan return value yang didapat di pemanggilan setelahnya. Misalnya begini, untuk mencari cfn(3)
, kalian harus mendapatkan nilai dari cfn(2)
dahulu. Jika ingin mencari nilai cfn(2)
, maka harus mendapatkan nilai dari cfn(1)
dahulu.
Lain cerita kalau fungsi diatas dihilangkan base case nya sehinga seperti ini,
static int calculateFactorialNumber(int number) {
return number * calculateFactorialNumber(number - 1);
}
Yang terjadi adalah seperti ini
Pemanggilan tadi akan terus menambahkan stack frame kedalam call stack, tanpa adanya stack frame yang telah selesai diproses ketika eksekusi. Hal inilah yang akan mengakibatkan call stack akan penuh, dan ketika eksekusi akan rewel StackOverflowException
, mengingat juga struktur data stack memiliki batas elemen maksimal yang bisa ditampung dalam stack tersebut.
Semoga bermanfaat 😅