By: William Hartanto

Rekursif adalah fungsi yang memanggil dirinya sendiri secara langsung ataupun tidak. Tujuan rekursif adalah untuk melakukan pengulangan, atau looping seperti for dan while, namun dengan cara yang berbeda. Berikut ini contoh implementasi algoritma rekursif dalam Bahasa pemrograman Python:

n  = int(input(“Input Number : “))
def rek(angka):
if angka > 0:
print(angka)
angka = angka – 1
rek(angka)
else:
print(angka)
rek(n)

Output ketika di Run :

Input Number : 5

5

4

3

2

1

0

Contoh Lain :

def faktorial(n):
if n <= 1:
return 1

else:
return n * faktorial(n – 1)
i = 0
x = int (input(“Masukkan Bilangan : “))
while i<=x :
print (i,’! = ‘,faktorial(i))
i+=1

Output ketika memasukan angka 5 :

Masukkan Bilangan : 5

0 ! =  1

1 ! =  1

2 ! =  2

3 ! =  6

4 ! =  24

5 ! =  120

Konsep Dasar Fungsi Rekursif

Pada dasarnya, sebuah fungsi rekursif terdiri dari dua komponen utama:

  1. Base Case (Kasus Dasar): Ini adalah kondisi di mana fungsi tidak akan memanggil dirinya sendiri lagi dan langsung memberikan hasil. Base case diperlukan untuk menghentikan rekursi dan mencegah terjadinya loop tak berujung.
  2. Recursive Case (Kasus Rekursif): Bagian ini adalah di mana fungsi memanggil dirinya sendiri dengan versi yang lebih sederhana atau lebih kecil dari masalah aslinya.

Contoh klasik dari fungsi rekursif adalah perhitungan faktorial dari suatu bilangan nnn. Faktorial dari nnn (ditulis sebagai n!n!n!) adalah produk dari semua bilangan bulat positif dari 1 hingga nnn. Ini dapat didefinisikan secara rekursif sebagai:

  • n!=n×(n−1)!n! = n \times (n-1)!n!=n×(n−1)! dengan 0!=10! = 10!=1 sebagai kasus dasar.

Berikut adalah implementasi fungsi rekursif untuk menghitung faktorial dalam Python:

def faktorial(n):

    if n == 0:

        return 1  # Base case

    else:

        return n * faktorial(n – 1)  # Recursive case

Cara Kerja Fungsi Rekursif

Saat fungsi faktorial dipanggil dengan suatu nilai, misalnya faktorial(5), fungsi ini akan terus memanggil dirinya sendiri dengan nilai nnn yang lebih kecil hingga mencapai base case (faktorial(0)). Setelah mencapai base case, nilai dikembalikan dan setiap panggilan fungsi sebelumnya akan dihitung hingga kembali ke panggilan fungsi awal.

Ilustrasi langkah-langkah untuk faktorial(5):

  1. faktorial(5) memanggil faktorial(4)
  2. faktorial(4) memanggil faktorial(3)
  3. faktorial(3) memanggil faktorial(2)
  4. faktorial(2) memanggil faktorial(1)
  5. faktorial(1) memanggil faktorial(0) yang mengembalikan 1
  6. Hasilnya diurutkan kembali: 1 * 1 * 2 * 3 * 4 * 5 = 120

Keunggulan dan Kekurangan Fungsi Rekursif

Keunggulan:

  • Kesederhanaan: Fungsi rekursif sering lebih mudah ditulis dan dibaca untuk masalah tertentu.
  • Struktur yang Jelas: Cocok untuk masalah yang secara alami dapat dibagi menjadi submasalah yang lebih kecil.

Kekurangan:

  • Efisiensi: Rekursi dapat memakan lebih banyak memori dan waktu karena setiap pemanggilan fungsi membutuhkan stack frame tambahan.
  • Potensi Overhead: Terlalu dalam rekursi bisa menyebabkan stack overflow.