Recursive Function

Recursive Function adalah function yang memanggil dirinya sendiri untuk menyelesaikan sebuah masalah.

Dengan recursive function, sebuah masalah dapat dipecah menjadi beberapa masalah yang lebih kecil sampai mencapai kondisi tertentu yang menghentikan proses pemanggilan function.

Secara sederhana:

Function → memanggil dirinya sendiri → memanggil dirinya sendiri → ...

Recursive function harus memiliki base case, yaitu kondisi yang menghentikan proses recursion.

Konsep Dasar Recursive Function

Struktur umum recursive function:

fun namaFunction(value: Int): Int {
    return if (kondisiBerhenti) {
        hasil
    } else {
        namaFunction(value - 1)
    }
}

Ada dua bagian penting:

1. Base Case
   Kondisi yang menghentikan recursion.

2. Recursive Case
   Bagian function yang memanggil dirinya sendiri.

Jika tidak terdapat kondisi berhenti, function akan terus memanggil dirinya sendiri dan dapat menyebabkan StackOverflowError.

Contoh Factorial

Salah satu contoh sederhana untuk memahami recursive function adalah menghitung factorial.

Factorial dari sebuah bilangan n ditulis:

n!

Contoh:

5! = 5 × 4 × 3 × 2 × 1

Hasilnya:

5! = 120

Secara matematis, factorial dapat didefinisikan sebagai:

n! = n × (n - 1)!

Dengan kondisi berhenti:

1! = 1

Konsep tersebut sangat cocok diterapkan menggunakan recursive function.

Factorial Menggunakan For Loop

Sebelum menggunakan recursive function, kita dapat menghitung factorial menggunakan for loop.

Contoh:

fun factorialLoop(value: Int): Int {
    var result = 1

    for (i in value downTo 1) {
        result *= i
    }

    return result
}

Function tersebut melakukan perulangan dari nilai value sampai 1.

Jika dipanggil:

println(factorialLoop(5))

Prosesnya:

result = 1

result = 1 × 5
result = 5 × 4
result = 20 × 3
result = 60 × 2
result = 120 × 1

result = 120

Output:

120

Factorial Menggunakan Recursive Function

Sekarang kita dapat membuat factorial menggunakan recursive function.

fun factorialRecursive(value: Int): Int {
    return when (value) {
        1 -> 1
        else -> value * factorialRecursive(value - 1)
    }
}

Perhatikan bagian:

factorialRecursive(value - 1)

Function factorialRecursive() memanggil dirinya sendiri dengan nilai yang lebih kecil.

Sedangkan:

1 -> 1

merupakan base case yang menghentikan recursion.

Cara Kerja Recursive Function

Misalnya kita memanggil:

factorialRecursive(5)

Maka prosesnya menjadi:

factorialRecursive(5)
= 5 × factorialRecursive(4)

= 5 × 4 × factorialRecursive(3)

= 5 × 4 × 3 × factorialRecursive(2)

= 5 × 4 × 3 × 2 × factorialRecursive(1)

Ketika mencapai:

factorialRecursive(1)

kondisi:

1 -> 1

terpenuhi.

Function mengembalikan:

1

Kemudian proses perhitungan kembali:

5 × 4 × 3 × 2 × 1

Hasilnya:

120

Contoh Program Lengkap

Berikut contoh perbandingan factorial menggunakan for loop dan recursive function:

fun main() {

    // Factorial menggunakan For Loop
    fun factorialLoop(value: Int): Int {
        var result = 1

        for (i in value downTo 1) {
            result *= i
        }

        return result
    }

    println(factorialLoop(10))

    // Factorial menggunakan Recursive Function
    fun factorialRecursive(value: Int): Int {
        return when (value) {
            1 -> 1
            else -> value * factorialRecursive(value - 1)
        }
    }

    println(factorialRecursive(10))
}

Output:

3628800
3628800

Kedua function menghasilkan nilai yang sama.

Memahami Base Case

Base case merupakan bagian yang sangat penting dalam recursive function.

Pada contoh factorial:

when (value) {
    1 -> 1
    else -> value * factorialRecursive(value - 1)
}

Bagian:

1 -> 1

adalah base case.

Ketika value mencapai 1, function tidak memanggil dirinya sendiri lagi.

Tanpa base case, recursion akan terus berjalan.

Contoh yang salah:

fun recursive(value: Int): Int {
    return value * recursive(value - 1)
}

Function tersebut tidak memiliki kondisi untuk berhenti.

Akibatnya function akan terus memanggil dirinya sendiri hingga stack penuh dan dapat menghasilkan:

StackOverflowError

Recursive Case

Selain base case, recursive function memiliki recursive case.

Pada contoh factorial:

else -> value * factorialRecursive(value - 1)

Bagian tersebut disebut recursive case karena function memanggil dirinya sendiri:

factorialRecursive(value - 1)

Nilai value dikurangi 1 pada setiap pemanggilan agar akhirnya mencapai base case.

Struktur Recursive Function

Secara sederhana, recursive function factorial dapat digambarkan seperti berikut:

factorial(5)
    ↓
5 × factorial(4)
        ↓
    4 × factorial(3)
            ↓
        3 × factorial(2)
                ↓
            2 × factorial(1)
                    ↓
                    1

Setelah mencapai 1, hasil kemudian dikembalikan:

1
↓
2 × 1 = 2
↓
3 × 2 = 6
↓
4 × 6 = 24
↓
5 × 24 = 120

Recursive Function vs Loop

Factorial dapat dibuat menggunakan loop maupun recursion.

Menggunakan Loop

fun factorialLoop(value: Int): Int {
    var result = 1

    for (i in value downTo 1) {
        result *= i
    }

    return result
}

Menggunakan Recursion

fun factorialRecursive(value: Int): Int {
    return when (value) {
        1 -> 1
        else -> value * factorialRecursive(value - 1)
    }
}

Keduanya menghasilkan hasil yang sama.

Perbedaannya adalah cara penyelesaiannya.

Loop menggunakan perulangan secara langsung, sedangkan recursive function menyelesaikan masalah dengan memanggil dirinya sendiri.

Kapan Menggunakan Recursive Function?

Recursive function cocok digunakan untuk masalah yang secara alami dapat dibagi menjadi masalah yang lebih kecil dengan pola yang sama.

Beberapa contoh penggunaannya:

• Factorial.
• Fibonacci.
• Struktur data tree.
• Struktur data folder dan subfolder.
• Algoritma pencarian tertentu.
• Algoritma sorting tertentu.
• Traversal tree.
• Masalah yang memiliki struktur berulang.

Namun, tidak semua masalah harus diselesaikan menggunakan recursion.

Jika masalah lebih sederhana dan mudah diselesaikan menggunakan loop, penggunaan loop sering kali lebih mudah dipahami.

Contoh Recursive Function Sederhana

Contoh function untuk menghitung mundur:

fun countdown(value: Int) {
    if (value == 0) {
        println("Selesai")
    } else {
        println(value)
        countdown(value - 1)
    }
}

Pemanggilan:

countdown(5)

Output:

5
4
3
2
1
Selesai

Pada contoh tersebut:

if (value == 0)

merupakan kondisi berhenti.

Sedangkan:

countdown(value - 1)

merupakan recursive case.

Kesimpulan

Recursive Function adalah function yang memanggil dirinya sendiri.

Contoh:

fun factorialRecursive(value: Int): Int {
    return when (value) {
        1 -> 1
        else -> value * factorialRecursive(value - 1)
    }
}

Recursive function memiliki dua bagian penting:

• Base Case — kondisi yang menghentikan recursion.
• Recursive Case — bagian function yang memanggil dirinya sendiri.

Pada factorial:

1 -> 1

adalah base case.

Sedangkan:

value * factorialRecursive(value - 1)

adalah recursive case.

Prinsip sederhananya:

tip

Recursive Function adalah function yang menyelesaikan masalah dengan memanggil dirinya sendiri sampai mencapai kondisi berhenti atau base case.