Recursion

Sebagian masalah memiliki struktur yang serupa dengan dirinya sendiri: faktorial lima adalah lima dikali faktorial empat, dan penelusuran folder adalah pemrosesan folder berisi folder yang lebih kecil. Untuk struktur demikian, Go membolehkan fungsi memanggil dirinya sendiri — teknik bernama recursion. Pada chapter ini kita akan melihat cara kerja recursion di atas call stack, membangun dua contoh klasik, lalu mempelajari dua batas pentingnya: base case yang wajib ada dan tail recursion yang tidak dioptimasi.

Cara Kerja Recursion #

Setiap pemanggilan fungsi menempati satu stack frame — sepetak memori berisi parameter dan variabel lokal pemanggilan tersebut. Pemanggilan rekursif menumpuk frame baru di atas frame lama, dan tumpukan itu terurai ketika base case tercapai. Recursion yang sehat selalu punya dua bagian: base case yang menghentikan pemanggilan, dan recursive case yang mendekatkan masalah ke base case. Fungsi faktorial berikut memuat keduanya:

// faktorial menghitung nilai faktorial dari n secara rekursif.
func faktorial(n int) int {
	if n <= 1 {
		return 1 // base case: rekursif berhenti di sini.
	}
	return n * faktorial(n-1)
}

Jejak pemanggilan faktorial(5) terurai seperti tabel berikut — setiap baris menunggu hasil baris di bawahnya sebelum mengalikan:

Nilai kemudian mengalir balik ke atas: 2, 6, 24, hingga 120 di pemanggil teratas.

Base Case Wajib Ada #

Recursive case yang tidak pernah mencapai base case berulang tanpa batas. Go menumbuhkan goroutine stack secara dinamis hingga batas sekitar satu miliar byte; melewatinya menghentikan program dengan pesan fatal error: stack overflow — bukan panic yang bisa dipulihkan. Faktor penyebabnya klasik: kondisi base case salah (n < 1 alih-alih n <= 1), parameter yang tidak mendekat (faktorial(n) tanpa n-1), atau base case yang terlewat pada satu cabang.

Fibonacci Naif #

Bentuk kedua yang paling terkenal adalah Fibonacci: setiap bilangan adalah jumlah dua bilangan sebelumnya. Versi naifnya menerjemahkan definisi itu secara harfiah menjadi dua pemanggilan rekursif:

// fibonacci menghitung bilangan Fibonacci ke-n secara naif.
func fibonacci(n int) int {
	if n <= 1 {
		return n // base case: F(0)=0 dan F(1)=1.
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

Program utuh memanggil fibonacci(25) dan menyelesaikannya dalam hitungan milidetik. Perhatikan pula pemanggilan fibonacci(0) di output: base case n <= 1 mengirim balik n itu sendiri, sehingga F(0) bernilai 0 — bukan 1 seperti pada faktorial.

Tail Recursion Tidak Dioptimasi #

Sebagian bahasa mengubah recursion posisi ekor (tail recursion) menjadi loop otomatis sehingga stack tidak bertambah. Kompiler Go tidak melakukan optimasi ini: return faktorial(n-1) * n tetap menumpuk frame karena perkalian menunggu hasil rekursif, dan bentuk posisi ekor sejati pun tetap dieksekusi apa adanya. Akibatnya, recursion dengan kedalaman puluhan ribu berisiko stack overflow meski logikanya benar.

Program Utuh #

Berkas recursion-demo.go menghitung faktorial dan deret Fibonacci dalam satu program. Jalankan dari direktori chapter:

go run recursion-demo.go

Output yang Dihasilkan:

faktorial(5) = 120
faktorial(0) = 1
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13
fibonacci(25) = 75025

Mari kita telaah baris demi baris program di atas:

1. Baris 6 (func faktorial(n int) int): fungsi faktorial yang memanggil dirinya sendiri dengan argumen lebih kecil, faktorial(n-1).
2. Baris 7–9 (if n <= 1 { return 1 }): base case — satu-satunya jalur keluar yang tidak memanggil ulang fungsi.
3. Baris 14 (func fibonacci(n int) int): memodelkan definisi F(n) = F(n-1) + F(n-2) sebagai dua pemanggilan rekursif.
4. Baris 15–17 (if n <= 1 { return n }): base case ganda F(0)=0 dan F(1)=1 dalam satu cabang.
5. Baris 25 (for i := range 8): loop range atas bilangan 0–7 untuk mencetak delapan suku pertama — bentuk loop modern sejak Go 1.22.

Fibonacci naif menghitung ulang submasalah yang sama berkali-kali — F(25) memanggil fungsi ratusan ribu kali. Teknik memoisasi dan pemrograman dinamis akan kita bahas nanti; keduanya membangun di atas satu kemampuan yang sudah kita kuasai sekarang: fungsi sebagai nilai yang bisa kosong. Chapter penutup section ini, Function Value dan nil , mengupas sisi nil dari kemampuan itu.

Referensi #

• Function calls — Go Spec — aturan pemanggilan, termasuk rekursif.
• Frequently Asked Questions — Go — perilaku stack goroutine yang tumbuh dinamis.
• A Tour of Go: more types — latihan resmi Fibonacci dengan closure.

package main

import "fmt"

// faktorial menghitung nilai faktorial dari n secara rekursif.
func faktorial(n int) int {
	if n <= 1 {
		return 1 // base case: rekursif berhenti di sini.
	}
	return n * faktorial(n-1)
}

// fibonacci menghitung bilangan Fibonacci ke-n secara naif.
func fibonacci(n int) int {
	if n <= 1 {
		return n // base case: F(0)=0 dan F(1)=1.
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

func main() {
	fmt.Println("faktorial(5) =", faktorial(5))
	fmt.Println("faktorial(0) =", faktorial(0))

	for i := range 8 {
		fmt.Printf("fibonacci(%d) = %d\n", i, fibonacci(i))
	}

	fmt.Println("fibonacci(25) =", fibonacci(25))
}