Rekursif

Rekursif

         Salah satu konsep paling dasar dalam ilmu komputer dan pemrograman adalah pengunaan fungsi sebagai abstraksi untuk kode-kode yang digunakan berulang kali. Kedekatan ilmu komputer dengan matematika juga menyebabkan konsep-konsep fungsi pada matematika seringkali dijumpai. Salah satu konsep fungsi pada matematika yang ditemui pada ilmu komputer adalah fungsi rekursif: sebuah fungsi yang memanggil dirinya sendiri.

Kode berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari dua bilangan:

def kali(a, b):

    return a if b == 1 else a + kali(a, b - 1)

Bagaimana cara kerja fungsi rekursif ini? Sederhananya, selama nilai b bukan 1, fungsi akan terus memanggil perintah a + kali(a, b - 1), yang tiap tahapnya memanggil dirinya sendiri sambil mengurangi nilai b. Mari kita coba panggil fungsi kali dan uraikan langkah pemanggilannya:

kali(2, 4)

  -> 2 + kali(2, 3)

  -> 2 + (2 + kali(2, 2))

  -> 2 + (2 + (2 + kali(2, 1)))

  -> 2 + (2 + (2 + 2))

  -> 2 + (2 + 4)

  -> 2 + 6

  -> 8

Perhatikan bahwa sebelum melakukan penambahan program melakukan pemanggilan fungsi rekursif terlebih dahulu sampai fungsi rekursif mengembalikan nilai pasti (2). Setelah menghilangkan semua pemanggilan fungsi, penambahan baru dilakukan, mulai dari nilai kembalian dari fungsi yang paling terakhir. Mari kita lihat contoh fungsi rekursif lainnya, yang digunakan untuk melakukan perhitungan faktorial:

def faktorial(n):

    return n if n == 1 else n * faktorial(n - 1)

Fungsi faktorial memiliki cara kerja yang sama dengan fungsi kali. Mari kita panggil dan lihat langkah pemanggilannya:

faktorial(5)

  -> 5 * faktorial(4)

  -> 5 * (4 * faktorial(3))

  -> 5 * (4 * (3 * faktorial(2)))

  -> 5 * (4 * (3 * (2 * faktorial(1))))

  -> 5 * (4 * (3 * (2 * 1)))

  -> 5 * (4 * (3 * 2))

  -> 5 * (4 * 6)

  -> 5 * 24

  -> 120

Dengan melihat kemiripan cara kerja serta kode dari fungsi faktorial dan kali, kita dapat melihat bagaimana fungsi rekursif memiliki dua ciri khas:

1. Fungsi rekursif selalu memiliki kondisi yang menyatakan kapan fungsi tersebut berhenti. Kondisi ini harus dapat dibuktikan akan tercapai, karena jika tidak tercapai maka kita tidak dapat membuktikan bahwa fungsi akan berhenti, yang berarti algoritma kita tidak benar.
2. Fungsi rekursif selalu memanggil dirinya sendiri sambil mengurangi atau memecahkan data masukan setiap panggilannya. Hal ini penting diingat, karena tujuan utama dari rekursif ialah memecahkan masalah dengan mengurangi masalah tersebut menjadi masalah-masalah kecil.

Setiap fungsi rekursif yang ada harus memenuhi kedua persyaratan di atas untuk memastikan fungsi rekursif dapat berhenti dan memberikan hasil. Kebenaran dari nilai yang dihasilkan tentu saja memerlukan pembuktian dengan cara tersendiri. Tetapi sebelum masuk ke analisa dan pembuktian fungsi rekursif, mari kita lihat kegunaan dan contoh-contoh fungsi rekursif lainnya lagi.

Fungsi Rekursif dan Iterasi

Pembaca yang jeli akan menyadari bahwa kedua contoh fungsi rekursif yang diberikan sebelumnya, faktorial dan kali, dapat diimplementasikan tanpa menggunakan fungsi rekursif. Berikut adalah contoh kode untuk perhitungan faktorial tanpa menggunakan rekursif:

def faktorial_iterasi(n):

    hasil = 1

    for i in range(1, n + 1):

        hasil = hasil * i

    return hasil

Dalam menghitung nilai faktorial menggunakan iterasi, kita meningkatkan nilai hasil terus menerus, sampai mendapatkan jawaban yang tepat. Yang perlu kita pastikan benar pada fungsi ini adalah berapa kali kita harus meningkatkan nilai hasil. Jika jumlah peningkatan salah, maka hasil akhir yang didapatkan juga akan salah.

Pendekatan iteratif berbeda dengan rekursif dalam hal ini: jika pendekatan rekursif memecah-mecah masalah untuk kemudian menyelesaikan masalah sedikit demi sedikit, pendekatan iteratif justru langsung mencoba menyelesaikan masalah, tanpa memecah-mecahkan masalah tersebut menjadi lebih kecil terlebih dahulu. Untungnya, baik teknik iterasi maupun rekursi sama-sama memiliki tingkat ekspresi yang sama: segala hal yang dapat diselesaikan dengan itearsi akan dapat diselesaikan dengan rekursif. Lalu, kapan dan kenapa kita harus menggunakan rekursif?

Meskipun dapat menyelesaikan masalah yang sama, terdapat beberapa permasalahan atau solusi yang lebih tepat diselesaikan dengan menggunakan fungsi rekursif. Salah satu contoh dari masalah ini adalah penelurusan data di dalam sebuah binary tree. Sebuah binary tree, yang dapat didefinisikan sebagai sebuah pohon dengan jumlah cabang yang selalu dua, secara alami adalah struktur data rekursif.

Binary Tree

Sebagai struktur rekursif, tentunya penelusuran binary tree akan lebih mudah dilakukan secara rekursif dibandingkan iterasi. Hal ini sangat kontras dengan, misalnya, pencarian karakter di dalam string. Sebagai data yang disimpan secara linear, pencarian karakter dalam string akan lebih mudah untuk dilakukan secara iteratif.

Untuk mempermudah ilustrasi, mari kita lakukan perbandingan antara implementasi rekursif dan iteratif untuk masalah yang lebih cocok diselesaikan dengan masing-masing pendekatan. Misalnya, implementasi algoritma euclidean untuk menghitung faktor persekutuan terbesar (FPB) yang lebih cocok untuk diimplementasikan dengan metode rekursif seperti berikut:

def gcd(x, y):

    return x if y == 0 else gcd(y, x % y)

yang jika diimplementasikan dengan menggunakan iterasi adalah sebagai berikut:

def gcd_iterasi(x, y):

    while y != 0:

        temp = y

        y = x % temp

        x = temp

    return x

Jika dibandingkan dengan fungsi matematis dari algoritma euclidean:

gcd(x,y)={xgcd(y,remainder(x,y))if y=0if y>0

tentunya implementasi secara rekursif lebih sederhana dan mudah dimengerti dibandingkan dengan secara iterasi.

Sekarang mari kita lihat contoh algoritima yang lebih cocok diimplementasikan secara iteratif, misalnya linear search. Implementasi standar linear search secara iteratif adalah sebagai berikut:

def linear_search(lst, search):

    for i in range(0, len(lst)):

        if lst[i] == search:

            print("Nilai ditemukan pada posisi: " + str(i))

            return 0

    print("Nilai tidak ditemukan")

    return -1

yang jika diimplementasikan secara rekursif akan menjadi:

def linear_search_rec(lst, search, pos):

    if len(lst) <= pos:

        print("Nilai tidak ditemukan.")

        return -1

    elif lst[pos] == search:

        print("Nilai ditemukan di posisi: " + str(pos))

        return 0

    else:

        return linear_search_rec(lst, search, pos + 1)

Perhatikan bagaimana diperlukan lebih banyak pengecekan pada fungsi rekursif, serta tambahan parameter pos yang berguna untuk menyimpan posisi pengujian dan ditemukannya elemen yang dicari. Jika menggunakan iterasi variabel pos tidak dibutuhkan lagi karena posisi ini akan didapatkan secara otomatis ketika sedang menelusuri list. Dengan melihat jumlah argumen dan pengecekan yang harus dilakukan, dapat dilihat bahwa implementasi linear search menjadi lebih sederhana dan mudah dengan menggunakan metode iterasi.

Tail Call

Sesuai definisinya, dalam membuat fungsi rekursif pada satu titik kita akan harus memanggil fungsi itu sendiri. Pemanggilan diri sendiri di dalam fungsi tentunya memiliki konsekuensi tersendiri, yaitu pengunaan memori. Dengan memanggil dirinya sendiri, secara otomatis sebuah fungsi akan memerlukan memori tambahan, untuk menampung seluruh variabel baru serta proses yang harus dilakukan terhadap nilai-nilai baru tersebut. Penambahan memori ini seringkali menyebabkan stack overflow ketika terjadi pemanggilan rekursif yang terlalu banyak.

Untuk menanggulangi kesalahan stack overflow ini, para pengembang bahasa pemrograman mengimplementasikan apa yang dikenal dengan tail call optimization. Dalam merancang dan menganalisa algoritma rekursif, pengertian akan tail call optimization merupakan hal yang sangat penting. Jadi, apa itu tail call?

Tail call merupakan pemanggilan fungsi sebagai perintah terakhir di dalam fungsi lain. Sederhananya, ketika kita memanggil sebuah fungsi pada bagian akhir dari fungsi lain, kita melakukan tail call, seperti pada kode di bawah:

def fungsi(x):

    y = x + 10

    return fungsi_lain(y)

Pada kode di atas, pemanggilan fungsi_lain sebagai kode terakhir yang dieksekusi oleh fungsi dapat dikatakan sebagai tail call. Ingat juga bahwa pemanggilan tidak harus berada di akhir fungsi secara fisik. Yang penting adalah bahwa kode terakhir yang dieksekusi adalah pemanggilan fungsi lain:

def tail_call(n):

    if n == 0:

         return fungsi_1(n + 1)

    else:

         return fungsi_2(n)

Pada contoh fungsi tail_call di atas, pemanggilan terhadap fungsi_1 maupun fungsi_2 adalah tail call, meskipun pemanggilan fungsi_1 tidak berada pada akhri fungsi secara fisik. Bandingkan dengan kode berikut:

def bukan_tail_call(n):

    result = fungsi_lain(n % 5)

    return result * 10

yang bukan merupakan tail call, karena kode terakhir yang dieksekusi (result * 10e) adalah sebuah operasi, bukan pemanggilan fungsi. Cara kerja ini tentunya juga dibawa ke fungsi rekursif, di mana:

def faktorial(n):

    if n == 1:

         return 1

    else:

        return n * faktorial(n - 1)

bukan merupakan tail call karena baik return 1 maupun n * faktorial(n - 1) bukanlah pemanggilan fungsi. Ingat bahwa n * faktorial(n - 1)merupakan operator perkalian, bukan pemanggilan fungsi karena faktorial(n - 1) akan harus mengembalikan hasil terlebih dahulu agar bisa dikalikan dengan n. Jika ingin membuat fungsi rekursif yang memanfaatkan tail call, kita harus memastikan kode terakhir yang dieksekusi adalah fungsi lain, tanpa operasi lanjutan. Misalnya, kita dapat menyimpan hasil kalkulasi sebagai parameter, seperti berikut:

def faktorial_tc(n, r = 1):

    if n <= 1:

        return r

    else:

        return faktorial_tc(n - 1, n * r)

untuk memastikan terdapat tail call di dalam fungsi.

Implementasi algoritma rekursif disarankan untuk mengadopsi tail call, karena natur dari fungsi rekursif yang memakan banyak memori. Tail call optimization, jika diimplementasikan oleh bahasa pemrograman, akan mendeteksi adanya tail call pada sebuah fungsi untuk kemudian dijalankan sebagai perulangan untuk menghindari penggunaan memori berlebihan.

Bahasa pemrograman yang mendukung tail call optimization biasanya adalah bahasa pemrograman fungsional seperti Haskell, LISP, Scheme, dan Erlang. Python, sayangnya, tidak mendukung optimization.

Analisis Algoritma Rekursif

Melakukan analisis untuk algoritma rekursif pada dasarnya sama dengan melakukan analisis terhadap algoritma imparatif lain. Perbedaan utama pada algoritma rekursif ialah kita tidak dapat secara langsung melihat berapa kali bagian rekursif dari algoritma akan dijalankan. Pada algoritma yang menggunakan perulangan for misalnya, kita dapat langsung menghitung jumlah perulangan untuk menghitung total langkah yang dibutuhkan. Dalam algoritma rekursif, jumlah perulangan tidak secara eksplisit bisa didapatkan karena informasi yang kita miliki adalah kapan algoritma berhenti, bukan berapa kali kode dieksekusi.

Misalnya, algoritma perhitungan faktorial yang telah dibahas sebelumnya:

def faktorial(n):

    return n if n == 1 else n * faktorial(n - 1)

Salah satu informasi yang didapatkan di sini adalah kapan algoritma berhenti melakukan rekursif, yaitu n == 1. Informasi lain yang kita miliki adalah berkurangnya jumlah data pada setiap pemanggilan faktorial. Bagaimana kita melakukan analisis algoritma ini? Cara termudahnya adalah dengan menggambarkan fungsi matematika dari faktorial terlebih dahulu:

faktorial(n)={1n∗faktorial(n−1)remainder(x,y))if n=1if n>1

Melalui fungsi matematika ini, kita dapat mulai melakukan penurunan untuk fungsi perhitungan langkah fungsi faktorial untuk kasus n>1:

f(n)=1+f(n−1)=1+1+f(n−2)=1+1+1+f(n−3)...=n+f(n−k)

Dan tentunya kita dapat mengabaikan penambahan langkah n di awal, serta dengan syarat bahwa fungsi berhenti ketika n−k=1:

n−kk=1=n−1

Maka dapat disimpulkan bahwa fungsi faktorial memiliki kompleksitas n−1, atau O(n). Ingat bahwa kunci dari perhitungan kompleksitas untuk algoritma rekursif terdapat pada fungsi matematis algoritma dan definisi kapan berhentinya fungsi rekursif tersebut.