Rekursif. Overview. Tujuan Instruksional

Rekursif

Pertemuan : 6 - 7 Disusun oleh : Danang Junaedi

Jurusan Teknik Informatika – Universitas Widyatama

Pemrograman Pemrograman IIII (Terstruktur (Terstruktur II) II)

Overview Tujuan Instruksional Review Fungsi & Prosedur

Introduction of Recursion Definition Recursion Method Contoh Kasus

Recursion vs Iteration Kasus Tugas Presentasi

Jurusan Jurusan Teknik Teknik Informatika Informatika

VI-VII VI-VII -- 22

Universitas Universitas Widyatama Widyatama


Tujuan Instruksional Menjelaskan pengertian dan manfaat rekursif, serta cara penulisannya dalam program Menjelaskan kelebihan dan kekurangan rekursif dalam pemrograman Menjelaskan penggunaan rekursif dalam program Menggunakan rekursif dalam program


VI-VII VI-VII -- 33


1


Review Fungsi dan Prosedur Fungsi tipe_fungsi nama_Fungsi(argumen1, argumen2,....) { xxxx xxxx tubuh Fungsi xxxx }

definisi Fungsi

contoh : double Absolut(double X) { if (X,0) X=-X; return(X); }

Prosedur void nama_Prosedur(argumen1, argumen2,....) { xxxx xxxx tubuh Prosedur xxxx }

definisi Prosedur

contoh : void Tampil(char Nama[15], int Kali) { int I; for(I=0;I

VI-VII VI-VII -- 44



Introduction of Recursion So far, we have seen methods that call other methods. For example, the main() method calls the square() method. main() square()

Recursive Method: A recursive method is a method that calls itself. compute()


VI-VII VI-VII -- 55



Definition A recursive function is a function that calls itself either directly or indirectly through another function. The function launches (calls) a fresh copy of itself to work on the smaller problem – this is referred to as recursive call and is also called as recursion step. The recursion step often includes the keyword return The function recognizes the base case and returns a result to the previous copy of the function and a sequence of returns ensues all the way up the line until the original function call eventually returns the final result to main


VI-VII VI-VII -- 66


2


Recursion Method The important thing to remember when creating a recursive function is to give an 'end-condition'. We don't want the function to keep calling itself forever, now, do we? Somehow, it should know when to stop. There are many ways of doing this. One of the simplest is by means of an 'if condition' statement A recursive method generally has two parts. A termination part that stops the recursion. This is called the base case. The base case should have a simple or trivial solution. One or more recursive calls. This is called the recursive case. The recursive case calls the same method but with simpler or smaller arguments. Jurusan Jurusan Teknik Teknik Informatika Informatika

VI-VII VI-VII -- 77



Example (1) Fungsi Faktorial

C++

Secara Iterasi

int Fakt(int n) { Fak=1; if (n > 1) { for(i=1;i<=n;i++) { Fak=Fak*I;} } return Fak; }

atau n! = n * (n - 1) * (n - 2) * ... * 1

Secara Rekursif

int Fakt(int n) { if (n == 1 || n == 0) { return 1;} else {return n * Fakt(n-1);} }

atau n! = n * (n - 1)! dan 0! = 1 Jurusan Jurusan Teknik Teknik Informatika Informatika

VI-VII VI-VII -- 88



Example (2) Ilustration 5!

5!

5 * 4!

5 * 4!

5! = 5 * 24 = 120 returned 4! = 4 * 6 = 24 returned

4 * 3!

4 * 3! 3! = 3 * 2 = 6 returned

3 * 2!

3 * 2! 2! = 2 * 1 = 2 returned

2 * 1!

2 * 1!

1

1

1 returned

a. Process of recursive calls


b. Values returned from each recursive calls

VI-VII VI-VII -- 99


3


Recursion vs Iteration Iteration Uses repetition structures (for, while or do…while) Repetition through explicitly use of repetition structure Terminates when loop-continuation condition fails Controls repetition by using a counter

Recursion Uses selection structures (if, if…else or switch) Repetition through repeated method calls Terminates when base case is satisfied Controls repetition by dividing problem into simpler one More overhead than iteration More memory intensive than iteration Can also be solved iteratively Often can be implemented with only a few lines of code


VI-VII VI-VII -- 10 10



Studi Kasus Towers of Hanoi game (Game invented by French mathematician Edouard Lucas in 1883)

Rules for the Towers of Hanoi game

1. Move one disk at a time. Each disk you move must be a topmost disk. 2. No disk may rest on top of a disk smaller than itself. 3. You can store disks on the second pole temporarily, as long as you

observe the previous two rules.

Fibonacci (F(n)=F(n-1) + F(n-2) + ……)

Binary Search secara rekursif Jurusan Jurusan Teknik Teknik Informatika Informatika




Tugas Buat Laporan berdasarkan kasus yang sudah kelompok anda pilih dengan susunan

Bab I Pendahuluan (Latar Belakang, Tujuan, Batasan Masalah) Bab II Dasar Teori Bab III Analisa & Perancangan Bab IV Implementasi (Listing Program dan Hasil Running Program) Bab V Penutup (Kesimpulan & Saran) Referensi

Laporan (Tidak perlu dijilid) Bahan presentasi dan program dikumpulkan dalam bentuk file (maksimum 4 hari sebelum presentasi dilaksanakan) Presentasi pada pertemuan ke-9




4


Untuk bahan renungan bersama 1. Jadilah Jagung, Jangan Jambu Monyet. Jagung membungkus bijinya yang banyak, sedangkan jambu monyet memamerkan bijinya yang cuma satu-satunya. Artinya : Jangan suka pamer 2. Jadilah Duren, jangan kedondong. Walaupun luarnya penuh kulit yang tajam, tetapi dalamnya lembut dan manis. hmmmm, beda dengan kedondong, luarnya mulus, rasanya agak asem dan di dalamnya ada biji yang berduri. Artinya : Don't Judge a Book by The Cover.. jangan menilai orang dari Luarnya saja. 3. Jadilah bengkoang. Walaupun hidup dalam kompos sampah, tetapi umbinya isinya putih bersih. Artinya : Jagalah hati jangan kau nodai. 4. Jadilah Tandan Pete, bukan Tandan Rambutan. Tandan pete membagi makanan sama rata ke biji petenya, semua seimbang, tidak seperti rambutan.. ada yang kecil ada yang gede. Artinya : Selalu adil dalam bersikap. 6. Jadilah Cabe. Makin tua makin pedas. Artinya : Makin tua makin bijaksana. 7. Jadilah Buah Manggis. Bisa ditebak isinya dari pantat buahnya. Artinya : Jangan Munafik 8. Jadilah Buah Nangka. Selain buahnya, nangka memberi getah kepada penjual atau yg memakannya. Artinya : Berikan kesan kepada semua orang (tentunya yg baik). Jurusan Jurusan Teknik Teknik Informatika Informatika



Pertemuan 8 : UTS Pertemuan 9 : Presentasi Pengelolaan File dan Rekursif

Jurusan Teknik Informatika – Universitas Widyatama

5

Rekursif. Overview. Tujuan Instruksional

Recommend Documents