1. Pengertian Algoritma Rekursif

Algoritma rekursif adalah algoritma yang menyelesaikan suatu masalah dengan cara memanggil dirinya sendiri secara berulang sampai mencapai kondisi tertentu yang disebut basis (base case).

Ciri utama algoritma rekursif:

• Memiliki fungsi/prosedur yang memanggil dirinya sendiri

• Memiliki base case untuk menghentikan proses rekursi

• Setiap pemanggilan mengarah ke masalah yang lebih kecil

Contoh sederhana:
Perhitungan faktorial
n! = n × (n−1)!

2. Tujuan Algoritma Rekursif

Tujuan penggunaan algoritma rekursif antara lain:

1. Menyederhanakan masalah kompleks
   Masalah besar dipecah menjadi sub-masalah yang lebih kecil dan sejenis.

2. Mempermudah penulisan kode
   Untuk kasus tertentu (seperti struktur pohon atau graf), rekursif membuat kode lebih singkat dan jelas.

3. Mencerminkan konsep matematis
   Banyak rumus matematika secara alami bersifat rekursif.

4. Memudahkan pemrosesan struktur data tertentu
   Seperti:

   • Tree

   • Graph

   • Linked List

   • Divide and Conquer

3. Jenis-Jenis Algoritma Rekursif

1. Rekursi Langsung (Direct Recursion)

Fungsi memanggil dirinya sendiri secara langsung.

Contoh:

def faktorial(n):
if n == 0:
return 1
return n * faktorial(n-1)

2. Rekursi Tidak Langsung (Indirect Recursion)

Fungsi tidak memanggil dirinya sendiri secara langsung, tetapi melalui fungsi lain.

Contoh:

def fungsiA(n):
if n > 0:
fungsiB(n-1)

def fungsiB(n):
if n > 0:
fungsiA(n-1)

3. Rekursi Ekor (Tail Recursion)

Pemanggilan rekursif terjadi di akhir fungsi, sehingga tidak ada operasi lain setelahnya.

Contoh:

def faktorial(n, hasil=1):
if n == 0:
return hasil
return faktorial(n-1, hasil*n)

4. Rekursi Ganda (Multiple Recursion)

Fungsi memanggil dirinya lebih dari satu kali dalam satu pemanggilan.

Contoh:

def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)

1. Contoh Algoritma Rekursif Faktorial

Digunakan untuk menghitung nilai faktorial suatu bilangan.

Rumus:
n! = n × (n−1)!

Contoh (Python):

def faktorial(n):
if n == 0 or n == 1: # base case
return 1
else:
return n * faktorial(n-1)

Penjelasan:
Fungsi akan memanggil dirinya sendiri hingga mencapai kondisi dasar.

2. Contoh Algoritma Rekursif Fibonacci

Digunakan untuk menghasilkan deret Fibonacci.

Contoh (Python):

def fibonacci(n):
if n <= 1: # base case
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

def fibonacci(n):
if n <= 1: # base case
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

Penjelasan:
Fungsi memanggil dirinya dua kali dalam satu pemanggilan (rekursi ganda).

3. Contoh Algoritma Rekursif Menjumlahkan Elemen Array

Digunakan untuk menjumlahkan semua elemen dalam sebuah array.

Contoh (Python):

def jumlah_array(arr, n):
if n == 0: # base case
return 0
return arr[n-1] + jumlah_array(arr, n-1)

4. Contoh Algoritma Rekursif Pencarian Nilai Maksimum

Digunakan untuk mencari nilai terbesar dalam array.

Contoh (Python):

def maksimum(arr, n):
if n == 1:
return arr[0]
return max(arr[n-1], maksimum(arr, n-1))

5. Contoh Algoritma Rekursif Pengecekan Palindrom

Digunakan untuk mengecek apakah sebuah kata merupakan palindrom.

Contoh (Python):

def palindrom(teks):
if len(teks) <= 1:
return True
if teks[0] != teks[-1]:
return False
return palindrom(teks[1:-1])

Algoritma rekursif merupakan salah satu teknik pemrograman yang penting dalam menyelesaikan masalah yang bersifat berulang dan terstruktur. Dengan memanfaatkan pemanggilan fungsi terhadap dirinya sendiri, algoritma rekursif mampu menyederhanakan permasalahan kompleks menjadi bagian-bagian yang lebih kecil dan mudah dipahami.

Meskipun memiliki kelebihan dalam hal kejelasan logika dan kesederhanaan kode, penggunaan algoritma rekursif tetap perlu memperhatikan kondisi dasar (base case) agar tidak terjadi pemanggilan tak terbatas. Oleh karena itu, pemahaman yang baik mengenai konsep, tujuan, dan jenis-jenis algoritma rekursif sangat diperlukan agar dapat digunakan secara efektif dan efisien dalam pemrograman.

Dengan memahami algoritma rekursif, diharapkan pembaca mampu menerapkannya secara tepat dalam berbagai permasalahan komputasi serta memilih solusi terbaik sesuai kebutuhan.