Memahami Fungsi Rekursif di Python

Sebagai programmer profesional, Anda perlu sangat mahir dalam hal-hal dasar seperti variabel, pernyataan kondisi, tipe data, spesifikator akses, pemanggilan fungsi, cakupan (scope), dan sebagainya. Apa pun jenis program yang Anda tulis—baik untuk Middleware, Web Development, atau Data Science—ini adalah beberapa hal paling mendasar yang perlu Anda kuasai dengan baik. Anda adalah seorang programmer terlebih dahulu, baru kemudian Anda menjadi Data Scientist, Web Developer, Machine Learning Engineer, dan seterusnya.

Salah satu konsep fundamental tersebut adalah Rekursi, dan sangat penting untuk dipahami saat Anda menulis fungsi jenis tertentu. Anda mungkin sudah tahu—"Disebut Rekursi ketika suatu fungsi memanggil dirinya sendiri." Namun apa yang terjadi di balik layar? Bagaimana memori fisik terpengaruh oleh Rekursi? Bisakah setiap fungsi diubah menjadi fungsi rekursif? Dalam tutorial ini, Anda akan menemukan jawaban atas pertanyaan-pertanyaan mendasar ini.

Anatomi Fungsi Rekursif:

Anda mungkin sudah menemukan istilah Rekursi dalam perkuliahan S1 Ilmu Komputer atau Teknologi Informasi. Pada bagian ini, Anda akan meninjau kembali konsep tersebut dengan cara yang menarik. Mari mulai.

Mari kembali ke definisi rekursi: "Disebut Rekursi ketika suatu fungsi memanggil dirinya sendiri". Mari ambil contoh untuk mendukung definisi ini:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Anda dapat melihat bahwa fungsi A() memanggil dirinya sendiri. Ini adalah contoh rekursi, dan A() adalah fungsi rekursif.

Sekarang mari pelajari beberapa dasar dari fungsi rekursif.

Dasar-dasar fungsi rekursif:

Sebuah fungsi rekursif harus memiliki dua sifat berikut:

• Relasi rekurensi
• Kondisi terminasi

Pertimbangkan potongan kode di atas untuk memahami poin-poin ini. Jelas, fungsi tersebut memiliki relasi rekurensi tertentu:

$n\le 1$ adalah kondisi terminasi / kondisi jangkar / kondisi dasar, dan jika terpenuhi, rekursi berhenti. Menentukan kondisi ini sangat penting. Jika tidak, fungsi akan masuk ke dalam loop tak berujung.

(Perlu dicatat bahwa potongan kode di atas tidak mengikuti bahasa pemrograman tertentu. Tujuan utamanya adalah menunjukkan contoh fungsi rekursif.)

Anda mungkin bertanya-tanya, mengapa seseorang menulis fungsi rekursif jika ada alternatif yang lebih baik? Ya, terkadang sulit menelusuri rekursi, tetapi setelah terbiasa, Anda akan menemukan rekursi itu indah dari segi keterbacaan program dan variabel. Rekursi tidak membutuhkan variabel tambahan untuk dijalankan, tetapi memerlukan kondisi terminasi yang tepat untuk berhenti. Sering kali, sulit menemukan kondisi terminasi untuk suatu rekursi. Sekali lagi, "Latihan membuat sempurna". Nanti dalam tutorial ini, Anda akan melihat betapa indah dan ringkasnya sebuah program jika diimplementasikan dengan rekursi dibandingkan cara konvensional. Sekarang, Anda akan mempelajari representasi memori dari fungsi rekursif.

Representasi Memori Fungsi Rekursif:

Pada bagian ini, Anda akan mempelajari bagaimana fungsi rekursif direpresentasikan secara fundamental di memori dengan menggunakan pohon dan stack. Mari pertimbangkan fungsi rekursif A() berikut untuk memahaminya:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Anda akan memahami representasi memori menggunakan pohon terlebih dahulu. Ini mungkin terdengar agak sulit, tetapi sebenarnya sangat mudah. Jika Anda menuliskan setiap pemanggilan fungsi dalam bentuk seperti pohon, akan terlihat seperti apa?

Sesuatu seperti berikut?

Beberapa poin yang perlu dicatat di sini:

• Fungsi dipanggil dengan A(3) dan untuk itu ada 4 (3+1) pemanggilan fungsi. Jika digeneralisasi, jika A(n) dipanggil maka total (n+1) pemanggilan fungsi diperlukan.
• Pemanggilan P() adalah hasil dari print(n).
• Fungsi berhenti pada pemanggilan A(0) karena pernyataan if (setelah pemanggilan fungsi A(0)) akan menerima n < 1 yang menyebabkan fungsi terminasi.

Anda melihat representasi mirip pohon ini terlebih dahulu karena untuk merepresentasikan fungsi rekursif pada sebuah stack, representasi ini diperlukan. Sekarang Anda akan melihatnya.

(Stack adalah struktur data yang mengikuti urutan elemen last in first out (LIFO))

Untuk representasi stack, Anda harus menelusuri pohon dari atas ke bawah dan dari kiri ke kanan. Gambar berikut akan memperjelas.

Menginterpretasikan bentuk (pohon) yang tampak aneh ini. Perlu diingat bahwa stack memiliki dua operasi—1. Push untuk memasukkan elemen ke dalam stack & 2. Pop untuk mengeluarkan elemen dari stack.

Sekarang, Anda mulai menelusuri pohon dari atas ke bawah dan kiri ke kanan:

• Setiap kali Anda melihat pemanggilan fungsi, Anda akan melakukan push ke stack tersebut.
• Jika Anda melihat pemanggilan print()/ P(), maka Anda cukup mencetak elemen yang bersesuaian.

Berikut ini akan menjadi elemen-elemen di dalam stack sebagai hasil dari penelusuran pohon dari A(3) ke A(0) hanya dalam arah atas ke bawah:

Sekarang Anda memulai paruh kedua dari penelusuran pohon, yaitu urutan kiri ke kanan. Setiap kali Anda melihat pemanggilan fungsi untuk kedua kalinya, Anda akan melakukan pop. Mengejutkan, elemen pertama dari stack (A(0)) yang akan dikeluarkan adalah yang terakhir masuk ke stack (ingat LIFO?). Sekarang, dalam perjalanan Anda akan menjumpai tiga pemanggilan P()—P(1), P(2), dan P(3). Anda akan mencetaknya sesuai urutan kemunculannya dalam penelusuran. Urutannya akan menjadi:

Akhirnya, ketika Anda menyelesaikan proses penelusuran, stack akan benar-benar kosong. Untuk lebih memahami operasi pop, berikut adalah gambar stack setelah seluruhnya di-pop.

Anda telah melihat cara merepresentasikan fungsi rekursif sederhana ke dalam memori menggunakan pohon dan stack. Sekarang, Anda akan melihat cara menelusuri sebuah rekursi.

Menelusuri Rekursi:

Pada bagian ini, Anda akan mempelajari cara menelusuri rekursi secara metodis. Pertimbangkan fungsi rekursif berikut:

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}

Satu poin krusial di sini adalah setiap kali sebuah fungsi dipanggil, sebuah activation record dibuat di memori yang berisi variabel lokal fungsi tersebut dan sebuah instruction pointer (yang menunjukkan tugas berikutnya yang akan dieksekusi ketika alur kembali ke fungsi itu). Misalnya sebuah fungsi bernama main() memanggil fungsi A() di atas sebagai A(3). Mari beri nomor baris A() mulai dari pernyataan if untuk pemahaman yang lebih baik:

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}

Activation record akan tampak seperti berikut:

Seperti disebutkan sebelumnya, setiap fungsi memiliki salinan variabel lokal dan instruction pointer masing-masing (dalam kasus ini berupa nomor baris). Setelah A(0) fungsi A() akan terminasi dan proses pop akan terjadi. Perhatikan bahwa di sini digunakan stack horizontal yang persis sama seperti yang telah Anda lihat sebelumnya dalam tutorial ini. Saat record didorong (push) ke stack, proses cetak juga akan terjadi dan elemen-elemen berikut akan tercetak:

Instruction pointer sangat penting untuk dicatat di sini karena sering kali dalam fungsi rekursif, kontrol kembali ke fungsi yang sama tetapi dengan nilai variabel berbeda. Jadi, untuk menjaga semuanya sinkron, pointer ini sangat membantu. Anda dapat mengikuti proses yang persis sama untuk menelusuri rekursi menggunakan representasi pohon.

Sekarang Anda akan mempelajari cara melakukan analisis ruang-waktu dari fungsi rekursif.

Analisis Ruang-Waktu Fungsi Rekursif:

DataCamp memiliki artikel yang sangat baik tentang Analisis Asimtotik di Python, dan disarankan untuk membacanya sebelum bagian ini. Mari rekap cepat apa yang dimaksud dengan analisis ruang dan waktu dari suatu fungsi (juga dikenal sebagai kompleksitas ruang dan kompleksitas waktu):

Untuk sebuah masukan, sebuah fungsi seharusnya menghasilkan keluaran. Untuk melakukannya, berapa banyak waktu yang dibutuhkan fungsi tersebut? Ukuran kompleksitas waktu mengaproksimasi waktu ini, dan sering disebut juga runtime dari fungsi. Demikian pula, ukuran kompleksitas ruang mengaproksimasi kebutuhan ruang (memori) dari suatu fungsi, yaitu untuk sebuah masukan tertentu. Lalu mengapa ini diperlukan?

• Alih-alih menjalankan fungsi pada rentang masukan dengan ukuran bervariasi, Anda dapat dengan mudah mengaproksimasi bagaimana suatu fungsi mungkin berperilaku pada masukan berbeda dengan ukuran bervariasi.
• Jika Anda memiliki dua fungsi yang memenuhi tujuan yang sama, mana yang akan Anda pilih? Ukuran apa yang akan Anda pertimbangkan untuk membuat keputusan? Ya, benar. Anda akan membandingkannya dengan menganalisis kompleksitas ruang dan waktu masing-masing dan melihat mana yang kinerjanya lebih baik.

Mari ambil fungsi rekursif sederhana sekarang dan analisis kompleksitas ruang dan waktunya.

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}

Mari lakukan analisis kompleksitas waktu terlebih dahulu. Asumsikan total waktu yang dibutuhkan untuk fungsi A() di atas adalah $T(n)$. Sekarang $T(n)$ adalah jumlah dari waktu untuk membandingkan apakah n lebih besar dari 1 dan waktu untuk mengeksekusi A(n-1). Jadi, $T(n)$ dapat dinyatakan sebagai -

Angka 1 adalah waktu yang dibutuhkan untuk perbandingan (Anda dapat menempatkan konstanta apa pun di sana). Sekarang, berapa waktu (dalam istilah $T(n)$) untuk mengeksekusi A(n-1)?

Demikian pula,

dan seterusnya.

Jika Anda memperhatikan dengan saksama persamaan-persamaan ini, semuanya saling terhubung. Bukan begitu? Jika Anda substitusikan satu per satu, Anda mendapatkan -

$T(n)$ = 1 + (1 + $T(n-2)$) = 2 + $T(n-2)$ = 3 + $T(n-3)$ = .... = k + $T(n-k)$ (setelah menjalankan fungsi selama k suku)

Sekarang, Anda perlu menentukan pada titik mana fungsi akan berhenti. Sesuai kondisi jangkar yang diberikan, Anda dapat menulis -

Asumsikan bahwa setelah berjalan selama k suku, fungsi berhenti berjalan. Jika demikian, maka haruslah -

$n - k = 1 => k = n - 1$

Sekarang substitusikan nilai k (= n -1) ke dalam $T(n) = k + T(n-k)$ :

$T(n) = (n-1) + T(n-(n-1))$
$=> T(n) = (n-1) + T(1)$
$=> T(n) = n-1 + 1 = n$ // Untuk T(1) hanya diperlukan perbandingan

Menurut aturan analisis asimtotik, $T(n) = n$ dapat ditulis ulang sebagai $T(n) = \mathcal{O}(n)$. Ini berarti kompleksitas waktu (terburuk) dari fungsi adalah $\mathcal{O}(n)$.

Anda mungkin ingin memperlambat sedikit di sini dan mengamati setiap langkah proses ini dengan saksama. Sangat disarankan Anda menuliskannya dengan pena dan kertas agar dapat memahami setiap bagiannya.

Analisis kompleksitas ruang dari fungsi ini sederhana. Fungsi ini adalah fungsi in-memory dan tidak menggunakan variabel tambahan. Jadi, Anda dapat menyimpulkan bahwa kompleksitas ruang fungsi adalah $\mathcal{O}(n)$.

Sekarang Anda akan menyatukan semuanya dan mengimplementasikan fungsi rekursif sederhana di Python.

Mengimplementasikan Fungsi Rekursif Sederhana di Python:

Anda akan menulis fungsi rekursif untuk mencari faktorial dari suatu bilangan. Kemudian Anda akan menulis versi iteratif dari fungsi yang sama. Mari mulai.

# Recursive function factorial_recursion()

def factorial_recursion(n):  
   if n == 1:  
       return n  
   else:  
       return n*factorial_recursion(n-1)

# Call the function

num = 7
print("The factorial of ",num," is ",factorial_recursion(num))

The factorial of  7  is  5040

Ingat dua bahan kunci untuk menulis fungsi rekursif?

• Relasi rekurensi
• Kondisi terminasi

Dalam kasus ini, relasi rekurensinya dapat berupa -

$f(n) = n!$
$f(n) = n * f(n-1)$ dan seterusnya.

Kondisi terminasi adalah ketika n sama dengan 1.

Sederhana, bukan?

Sekarang, Anda akan mengimplementasikan versi iteratif dari fungsi yang sama.

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)

factorial_iterative(7)

The factorial of 7 is 5040

Anda dapat dengan jelas melihat perbedaan antara kedua versi. Versi rekursif jauh lebih indah daripada versi iteratif. Bukan begitu?

Selamat!

Anda telah sampai di akhir. Dalam tutorial ini, Anda melakukan studi mendalam tentang fungsi rekursif. Mulai dari dasar-dasar hingga menganalisis kompleksitas ruang dan waktu dari fungsi rekursif, semuanya telah Anda bahas. Anda juga melihat bagaimana rekursi dapat bermanfaat untuk menyelesaikan masalah dengan karakteristik tertentu. Kini, Anda seharusnya berada pada posisi untuk menyelesaikan masalah (yang memiliki relasi rekurensi dan kondisi terminasi) menggunakan rekursi. Anda mungkin ingin menyelesaikan masalah mencari Bilangan Fibonacci dalam suatu rentang menggunakan rekursi.

Saya menganjurkan Anda untuk menyelesaikan beberapa masalah umum seperti Binary Search, Merge Sort, Tower of Hanoi, dan sebagainya menggunakan rekursi serta melakukan analisis ruang-waktu juga. Ini pasti akan membuat Anda menjadi programmer yang lebih baik.

Dari sisi pengantar, hal-hal yang Anda bahas sudah memadai. Namun jika Anda ingin mempelajari lebih lanjut tentang rekursi, pastikan Anda mengunjungi tautan berikut:

• Recursion and Dictionaries oleh Prof. Grimson
• Dynamic Programming untuk mengoptimalkan kinerja fungsi rekursif

Jika Anda ingin belajar lebih banyak tentang Python, ikuti kursus gratis DataCamp Intro to Python for Data Science.