Algoritma Rekursif: Pengertian,Tujuan dan Jenisnya

Algoritma Rekursif

Algoritma rekursif adalah jenis algoritma yang cukup menarik karena memungkinkan sebuah fungsi atau prosedur untuk memanggil dirinya sendiri dengan input yang semakin menyempit.

Dalam bahasa yang lebih sederhana, algoritma ini adalah cara untuk memecahkan masalah dengan memecahkannya menjadi beberapa versi yang lebih kecil dari masalah itu sendiri.

Algoritma rekursif dapat digunakan dalam berbagai jenis masalah, seperti pengurutan, pencarian, pemecahan masalah kombinatorial, dan banyak lagi. Namun, penting untuk memperhatikan bahwa penggunaan rekursi harus hati-hati dan memperhatikan efisiensi dan penggunaan memori.

Jika tidak dikendalikan dengan baik, rekursi dapat menyebabkan masalah memori (stack overflow) dan kinerja yang buruk.

Tujuan Algoritma Rekursif

Algoritma rekursif memiliki beberapa tujuan, antara lain:

1. Dapat digunakan untuk memecahkan masalah yang kompleks menjadi sub masalah yang lebih sederhana.
2. Algoritma ini sering digunakan dalam implementasi struktur data seperti pohon, graf, atau daftar terhubung.
3. Serta dapat digunakan untuk melakukan pengulangan secara efisien.

Jenis Algoritma Rekursif

a. Factorial

Algoritma factorial digunakan untuk menghitung faktorial dari suatu bilangan. Faktorial dari suatu bilangan n (ditulis n!) adalah hasil perkalian semua bilangan bulat positif dari 1 hingga n.

Contoh implementasi algoritma rekursif factorial dalam bahasa Python:

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

b. Tower of Hanoi

Algoritma Tower of Hanoi digunakan untuk memindahkan tumpukan cakram dari satu tiang ke tiang lainnya, dengan aturan bahwa hanya satu cakram yang dapat dipindahkan pada satu waktu dan cakram yang lebih besar tidak boleh ditempatkan di atas yang lebih kecil.

Contoh implementasi algoritma Tower of Hanoi dalam bahasa Python:

def tower_of_hanoi(n, source, destination, auxiliary):
    if n > 0:
        tower_of_hanoi(n-1, source, auxiliary, destination)
        print("Move disk", n, "from", source, "to", destination)
        tower_of_hanoi(n-1, auxiliary, destination, source)

c. DFS of Graph

Algoritma Depth-First Search (DFS) digunakan untuk melakukan pencarian pada struktur data graf secara rekursif. Algoritma ini mengunjungi semua simpul dalam graf dengan mengikuti jalur secara mendalam sebelum kembali.

Contoh implementasi algoritma DFS dalam bahasa Python:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next_node in graph[start] - visited:
        dfs(graph, next_node, visited)
    return visited

d. Eksponential

Algoritma eksponensial digunakan untuk menghitung hasil dari suatu operasi eksponensial dengan memanggil diri sendirI.

Contoh implementasi algoritma eksponensial dalam bahasa Python:

def exponential(a, n):
    if n == 0:
        return 1
    else:
        return a * exponential(a, n-1)

Dengan menggunakan algoritma ini, kita dapat mengatasi berbagai macam masalah dengan cara yang lebih efisien dan terstruktur.

Algoritma rekursif adalah alat yang kuat untuk menyelesaikan masalah yang melibatkan pemecahan masalah menjadi bagian-bagian yang lebih kecil dan sering digunakan dalam berbagai bidang seperti pemrograman komputer, matematika, dan ilmu komputer