Rekursi dan Greedy

Rekursi adalah teknik pemrograman di mana sebuah fungsi...

• Memanggil dirinya sendiri

• Memanggil fungsi lain

• Tidak memiliki kondisi dasar

• Memiliki beberapa variabel global

Apakah syarat utama agar suatu fungsi rekursif dapat berakhir ?

• Menggunakan loop di dalam fungsi

• Memiliki kondisi dasar (base case)

• Memanggil fungsi lain di dalamnya

• Menggunakan variabel lokal

Fungsi rekursif biasanya lebih sederhana dalam menulis kode jika dibandingkan dengan fungsi iteratif, namun salah satu kelemahan dari rekursi adalah ...

• Memerlukan lebih banyak waktu untuk menulis kode

• Menghabiskan lebih banyak memori karena penggunaan stack

• Hanya dapat digunakan untuk masalah kecil

• Memerlukan lebih banyak operator matematika

Manakah dari berikut ini yang merupakan contoh masalah yang cocok diselesaikan dengan rekursi ?

• Pengurutan bubble (bubble sort)

• Pencarian biner (binary search)

• Pengurutan seleksi (selection sort)

• Pencarian linier (linear search)

Manakah dari berikut ini yang bukan contoh rekursi ?

• Menghitung faktorial

• Mencari nilai maksimum dalam array

• Mencetak elemen dari array secara terbalik

• Menentukan apakah suatu bilangan adalah bilangan prima

Ketika sebuah fungsi rekursif dipanggil tanpa kondisi dasar yang tepat, apa yang mungkin terjadi ?

• Program akan berjalan lebih cepat

• Program akan mengalami stack overflow

• Fungsi akan mengembalikan nilai acak

• Fungsi tidak akan pernah dipanggil

Algoritma greedy adalah algoritma yang menyelesaikan masalah dengan cara. ..

• Memecahkan masalah secara menyeluruh dan menyimpan hasilnya

• Memecahkan masalah dengan memilih solusi lokal terbaik pada setiap langkah

• Menguji semua kemungkinan solusi dan memilih yang terbaik

• Membagi masalah menjadi sub-masalah yang lebih kecil

Pada masalah knapsack, algoritma greedy akan memilih ...

• Barang dengan nilai paling tinggi terlebih dahulu

• Barang dengan berat paling ringan terlebih dahulu

• Barang dengan rasio nilai per berat paling tinggi terlebih dahulu

• Semua barang yang bisa dimasukkan ke dalam tas

Manakah dari berikut ini yang merupakan masalah yang tidak dapat diselesaikan dengan algoritma greedy ?

• Pencarian lintasan terpendek pada graf

• Knapsack 0/1

• Pengurutan elemen

• Pembagian kerja optimal

Algoritma greedy optimal pada masalah pencarian lintasan terpendek, dikenal dengan ...

• Algoritma Kruskal

• Algoritma Prim

• Algoritma Dijkstra

• Algoritma Floyd-Warshall