Fungsi Rekursif

            Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri.  Fungsi ini akan terus berjalan sampai kondisi berhenti terpenuhi, oleh karena itu dalam sebuah fungsi rekursif perlu terdapat 2 blok penting, yaitu blok yang menjadi titik berhenti dari sebuah proses rekursi dan blok yang memanggil dirinya sendiri.

Contoh – contoh penerapan rekursif:

1.      Fungsi cetak ke layar

Fungsi ini mencetak  nilai dari paremeter yang dilempar kepadanya.  Jika nilai dari parameter tersebut  > 0, fungsi akan mencetak nilai dari parameter tersebut dan kemudian memanggil dirinya lagi, jika tidak, program berhenti.

Untuk melihat lebih jelas, terapkan fungsi di atas dalam sebuah program.

2.      Fungsi pangkat

Fungsi ini digunakan untuk menghitung nilai: Xⁿ dengan n berupa bilangan bulat positif.  Solusi dari persoalan ini:

JIKA n = 1 MAKA Xⁿ = X

SELAIN ITU: Xⁿ = X * X^n-1

Sebagai contoh diambil nilai X=5 dengan n=3, pelukisan proses pemecahannya:

Berikut adalah fungsi pangkat dengan menggunakan solusi di atas:

a adalah bilangan yang dipangkatkan, sedangkan b adalah bilangan pemangkatnya.  Jika nilai dari b adalah 1, return a, lainnya return a dikali dengan fungsi pangkat dengan parameter a dan b-1.  Untuk lebih jelas, terapkan dalam program.

3.      Fungsi faktorial

Faktorial dapat dibuat dengan menerapkan rekursi.  Berikut ini adalah fungsi faktorial rekursif dari sebuah program.

Fungsi faktorial diatas akan melakukan rekursi selama nilainya > 1.  Sebagai contoh:

4!, pelukisan penyelesaiannya:

Untuk lebih jelas, terapkan fungsi di atas dalam sebuah program.

Latihan

1.      Buatlah program untuk menghitung FPB (faktor persekutuan terbesar) dari dua bilangan dengan menggunakan metode rekursif.  Untuk membantu, berikut diberikan penyelesaian secara rekursif dari FPB:

fpb(x,y) = y jika y <= x dan sisa_pembagian(x,y) = 0

fpb(x,y) = fpb(y,x) jika x < y

fpb(x,y) = fpb(y, sisa_pembagian(x,y)) untuk keadaan yang lain

2.      Buatlah fungsi untuk membalik suatu bilangan dengan cara rekursif.  Sebagai contoh, bilangan 1234 ditampilkan menjadi 4321!

3.      Buatlah deret fibonaci dengan menerapkan rekursi!

Tree..

Tree merupakan struktur hirarkis dari sebuah susunan data. Dalam tree,kita mempunyai sebuah Root yang nantinya akan menjadi awal dari tree tersebut. Untuk tree, kita juga membutuhkan struct. Ada banyak jenis-jenis Tree, tapi yang akan kita pelajari saat ini adalah implementasi dari Binary Tree, yaitu Tree yang hanya memiliki 2 tangan.

Langkah awal membuat Binary Tree adalah membuat struct seperti pada inisialisasi double linked list.

Setelah kita membuat struct, kita membuat void main yang di dalamnya kita deklarasikan sebuah variable yang bertipe data Node (struct yang telah kita buat) untuk nantinya digunakan sebagai root.

Setelah itu kita memanggil fungsi untuk tambah data.

Dalam fungsi tambah, parameter yang dikirim adalah “alamat dari Node root” dan data. Karena itu kita harus membuat parameter pada fungsi  tambah yang dapat menyimpan alamat dan data.

Jika ada masukkan data, fungsi yang kita buat harus selalu mengecek dari root, karena itu void main selalu mengirim alamat dari root. Mengapa bukan mengirim rootnya tetapi mengiri alamat root? Sebab root bukan variable global, sehingga kita harus mengakses alamatnya langsung. Setelah alamat dari root dikirim maka kita simpan alamat root tersebut dalam Node lain (sebut saja pohon). Ada 3 kondisi dalam memasukkan data:

1.      Jika nilai dari pohon adalah NULL. Maka kita buat Node baru untuk menampung nilai dan kemudian kita  copy Node baru ke Node pohon.

2.      Jika nilai dari pohon->data kurang dari databaru. Maka dia akan memanggil dirinya sendiri dengan parameter alamat dari (*pohon)->kiri dan databaru.

3.     

Jika nilai dari pohon->data lebih dari databaru. Maka dia akan memanggil dirinya sendiri dengan parameter alamat dari (*pohon)->kanan dan databaru.

è Di situ tertera **pohon,mengapa?? Karena yang dikirim adalah alamat (&root).

Sekarang kita coba membuat untuk menampilkan isi dari tree tersebut. Ada 3 cara untuk menampilkan isi dari Tree:

1.      Pre Order

Secara mudah adalah tampilkan,lalu  cek kiri, lalu cek kanan. (tampil-kiri-kanan)

2.      In Order

Beda dengan Pre Order, jika In Order maka ke kiri dulu kemudian di tampilkan, lalu setelah itu ke kanan. (kiri-tampil-kanan)

3.      Post Order

Jika Post Order, di tampilkan terakhir, jadi cek ke kiri, cek ke kanan, lalu terkhir baru di tampilkan. (kiri-kanan-tampil)

Sekarang ayo kita tambahkan menu pada void main untuk menampilkan tampilan PreOrder, InOrder, dan PostOrder. Ubah void main menjadi seperti berikut.

Setelah itu, kita buat fungsi untuk menampilkan ketiga cara tersebut

Algoritma Pre Order:

1.      Cek apakah tree kosong, jika tidak lakukan langkah selanjutnya.

2.      Tampilkan isi pohon

3.      Panggil fungsi diri sendiri dengan parameter pohon->kiri

4.      Panggil fungsi diri sendiri dengan parameter pohon->kanan

Algoritma In Order:

1.      Cek apakah tree kosong, jika tidak lakukan langkah selanjutnya.

2.      Panggil fungsi diri sendiri dengan parameter pohon->kiri

3.      Tampilkan isi pohon

4.      Panggil fungsi diri sendiri dengan parameter pohon->kanan

Algoritma Post Order:

1.      Cek apakah tree kosong, jika tidak lakukan langkah selanjutnya.

2.      Panggil fungsi diri sendiri dengan parameter pohon->kiri

3.      Panggil fungsi diri sendiri dengan parameter pohon->kanan

4.      Tampilkan isi pohon

è Pemahaman : Jika dalam suatu fungsi memanggil fungsi, bukan berarti fungsi yang memanggil akan berhenti ketika memanggil fungsi. Tetapi fungsi pemanggil akan berjalan lagi setelah fungsi yang di panggil selesai dijalankan. Misalnya saja pada InOrder, walaupun pada langkah ke 2 fungsi InOrder memanggil dirinya sendiri tetapi langkah ke 3 dan ke 4 tetap di jalankan setelah fungsi yang di panggil pada langkah ke 2 selesai di jalankan.

Posted in: Teori Pascal