Fungsi Rekursif

Daftar Isi
  1. Apa yang Kita Ketahui Tentang Algoritma Ini?
  2. Iteratif vs Rekursif
  3. Iteratif
  4. Rekursif
  5. Perbadingan Iteratif vs Rekursif
  6. Latihan
  7. Download Materi Power Point
  8. Referensi


Apa yang Kita Ketahui Tentang Algoritma Ini?

Algoritma di sebelah kiri merupakan algoritma rekursif sedangkan algoritma di sebelah kanan merupakan algoritma iteratif


Iteratif vs Rekursif

Dalam program komputer, pengulangan dilakukan dengan salah satu dari dua cara: baik melalui rekursi atau melalui iterasi.

 

Secara umum, rekursi dan iterasi melakukan jenis tugas yang sama:

menyelesaikan tugas yang rumit satu bagian pada satu waktu, dan menggabungkan hasilnya.

Kedua pendekatan menghasilkan proses yang diulang beberapa kali.

 

Dalam kasus Fibonacci:


Iteratif

Struktur iteratif biasanya mengacu pada struktur yang mengandung pengulangan eksplisit dari suatu proses, yaitu, loop atau perulangan.

Sebuah loop harus memiliki kriteria berhenti. Biasanya kriteria tersebut adalah salah satu dari dua jenis:

  • Jumlah iterasi yang telah ditentukan melalui loop
  • Kondisi tertentu yang tercapai.

Pentingnya iterasi: terus mengulang sampai sebuah tugas "selesai". Contohnya, penghitungan loop mencapai batas


Rekursif

Rekursi dalam ilmu komputer adalah metode di mana solusi untuk sebuah masalah bergantung pada solusi untuk instansi-instansi yang lebih kecil dari masalah yang sama. Pendekatan ini dapat diterapkan pada berbagai jenis masalah, dan rekursi adalah salah satu ide sentral dalam ilmu komputer. (Wikipedia).

 

Suatu fungsi rekursif f(x): adalah suatu fungsi dimana evaluasinya untuk suatu input xi (xi bukan initial input x0) memerlukan evaluasi fungsi dirinya sendiri untuk input xj yang lain.

 

Contoh:

Fact(n) = n * Fact(n-1),    dengan kondisi awal: Fact(1) = 1

Fibo(n) = Fibo(n-1)+Fibo(n-2),       dengan kondisi awal: Fibo(0)=0, Fibo(1)=1 Gcd(a,b)=Gcd(b, a mod b),            dengan kondisi awal: Gcd(a,0) = a

 

Definisi matematis dari suatu fungsi disebut rekursif jika fungsi tersebut didefinisikan dalam hal dirinya sendiri (dengan argumen yang sedikit lebih kecil), dan suatu fungsi komputer (subrutin) disebut rekursif jika ia memanggil dirinya sendiri (dengan argumen yang sedikit berbeda).

 

Pentingnya rekursi: menyelesaikan masalah besar dengan memecahnya menjadi potongan-potongan yang lebih kecil dan lebih kecil sampai Anda dapat menyelesaikannya; menggabungkan hasilnya.

Catatan: Kode rekursif tidak memiliki perulangan. Pengulangan tercapai ketika subprogram memanggil dirinya sendiri secara berulang sampai mencapai kasus dasar.


Perbadingan Iteratif vs Rekursif

Manakah yang Lebih Baik?

Tidak ada jawaban yang jelas, tetapi ada pertimbangan yang dikenal.

"Matematikawan" seringkali lebih suka pendekatan rekursif.

  • Solusi sering lebih pendek, lebih mendekati entitas matematika abstrak.
  • Solusi rekursif yang baik mungkin lebih sulit untuk dirancang dan diuji.

"Programmer", terutama yang tidak memiliki latar belakang pendidikan ilmu komputer, sering lebih suka solusi iteratif.

  • Secara umum, pendekatan iteratif tampak lebih menarik bagi banyak orang.
  • Kontrol tetap berada dalam loop, dan itu terasa lebih transparan daripada solusi rekursif yang terkadang tampak "ajaib".

Latihan


Download Materi Power Point

https://drive.google.com/drive/folders/1FgJORtgS1FbqJ_7B2bcb0gDc79KlAH7p?usp=drive_link


Referensi

-