rekursif

Praktikum Pemrograman Bahasa C

1

PENDAHULUAN REKURSI

TUJUAN BELAJAR: Setelah melakukan praktikum dalam bab ini, mahasiswa diharapkan mampu: 1. Memahami konsep rekursi dan mengerti kegunaannya 2. Mengimplementasikan rekursi dalam pemrograman 3. Mengidentifikasi permasalahan-permasalahan pemrograman yang harus diselesaikan dengan

menggunakan rekursi dan menyelesaikannya. TUGAS PENDAHULUAN: 1. Buatlah fungsi rekursi untuk menghitung faktorial dan faktorial tail 2. Buatlah fungsi rekursi untuk menampilkan deret fibonanci PEMBAHASAN

1. Proses Rekursi 0! = 1 1! = 1 * 0! 2! = 2 * 1! 3! = 3 * 2! Notasi matematis n!=1 jika n==0 n!=n * (n-1)! jika n > 0 Code

2. Deret Fibonacci merupakan deret integer berbentuk 0,1,1,2,3,5,8,13,21,34,… fib(0)= 0 ; fib(1)=1 Definisi rekursi untuk fibonacci fib(n)= n jika n==0 atau n==1 fib(n)= fib(n-2)+fib(n-1) jika n >=2 Alternative Code

int fact(int n) { int x, y; if(n==0) return(1); x=n-1; y=fact(x); return(n*y); }

int fibo_r (int n) { if(n==1) return 1; else if(n==2) return 1; else return fibo_r(n-1) + fibo_r(n-2); }

int fib(int n) { int x,y; if (n<=1) return(n);

x = fib(n-1); y = fib(n-2); return(x+y); }


2

REKURSI TUJUAN Setelah melakukan praktikum ini siswa diharapkan mengerti dan dapat: 1. Belajar berpikir secara rekursif 2. Belajar bagaimana cara penggunaan rekursif pada kasus-kasus dasar dan kasus-kasus rekursif 3. Belajar bagaimana cara memecah suatu permasalahan menjadi beberapa sub masalah 4. Menggunakan pemanggilan pohon dan melakukan trace agar supaya mengerti bagaimana program

rekursif bekerja SOAL 1. Untuk latihan program no 8 dan 9 buatlah tree dan trace untuk menunjukkan proses rekursifnya dan

faktorial (6) 2. Buatlah program fungsi rekursif untuk menghitung xn

• Power(x,0)=1.0 dan

nama fungsi power(x,n) dimana x mempunyai tipe float dan n adalah non negatif integer. Dengan ketentuan:

• Untuk n > 1 power(x,n) = x*power(x,n-1) Buatlah juga untuk contoh power(2,5) tree dan trace dari proses rekursif

3. Modifikasilah program no 2 menggunakan rekursif two half ranges, dimana separuh dari n = n/2, pangkatkan power(x,n/2) dan kalikan dengan x jika pangkatnya ganjil. Contoh x11 = (x5)*(x5)*x sedangkan x10 = (x5)*(x5

4. Buatlah program untuk menyelesaikan permainan Menara Hanoi. Permainan Menara Hanoi dimainkan menggunakan tiga tonggak, yaitu tonggak asal, tonggak tujuan dan tonggak bantu. Tujuan dari permainan ini adalah memindahkan piringan-piringan dari tonggak asal ke tonggak tujuan menggunakan tonggak bantu. Syarat pemindahan adalah jumlah piringan yang boleh dipindah dalam satu waktu hanya satu dan piringan yang kecil harus berada di piringan yang besar. Dengan kata lain, piringan besar tidak boleh berada di atas piringan kecil. Masukkan dari program ini adalah banyaknya piringan yang harus dipindah, dimana 3 <= piringan <=9. Keluaran dari program ini adalah langkah yang harus dilakukan untuk memindahkan piringan-piringan tersebut, misalnya:

)

• A pindah ke C • A pindah ke B • C pindah ke B • A pindah ke C • B pindah ke A • B pindah ke C

PEMBAHASAN 1. o Program 8

Tree


3

Faktorial (1)

Faktorial (2)

Faktorial (3)

Faktorial (4)

Faktorial (6)

Faktorial (5)

1*

2*

3*

4*

5*

6

720

720

120

6

30

360

o Program 9

Trace faktorial(6) 6 * faktorial(5) 6 * 5 * faktorial(4) 6 * 5 * 4 * faktorial(3) 6 * 5 * 4 * 3 * faktorial(2) 6 * 5 * 4 * 3 * 2 * faktorial(1) 6 * 5 * 4 * 3 * 2 * 1 = 720

product (1,6)

product (1,3)

product (1,2)

product (3,3)

product (1,1)

product (2,2)

product (4,6)

product (4,5)

product (6,6)

product (4,4)

product (5,5)

4

5

20

6

120

2

1

2

3

6

720

Tree

2.

Trace faktorial(6) product(1,6) product(1,3) * product(4,6) product(1,2) * product(3,3) * product(4,5) * product(6,6) product(1,1) * product(2,2) * product(3,3) * product(4,4) * product(5,5) * product(6,6) 1 * 2 * 3 * 4 * 5 * 6 = 720

#include<stdio.h> #include<string.h>


4

#include<stdlib.h> #include<conio.h> double hasil; double rekursif(double x,int n); void main() { char input[3]; int n; double x; printf("\n\tPROGRAM PENGITUNG NILAI x^n\n"); printf("\t---------------------------\n"); printf("\n\tMasukkan nilai x dan n,\n\tuntuk menghitung nilai x pangkat n\n"); printf("\n\tMasukkan nilai x: "); gets(input); x=atof(input); printf("\tMasukkan nilai n:"); gets(input); n=atoi(input); rekursif(x,n); printf("\tHasil = %g\n",hasil); getche(); } double rekursif(double x,int n) { if(n==0) return 1; else { hasil=x*rekursif(x,n-1); return hasil; } }

Preview :

Tree


5

rekursif (2,0)

rekursif (2,1)

rekursif (2,2)

rekursif (2,3)

rekursif (2,5)

rekursif (2,4)

1*

2*

2*

2*

2*

2

32

32

8

2

4

16

3.

Trace rekursif(2,5) 2 * rekursif(2,4) 2 * 2 * rekursif(2,3) 2 * 2 * 2 * rekursif(2,2) 2 * 2 * 2 * 2 * rekursif(2,1) 2 * 2 * 2 * 2 * 2 * rekursif(2,0) 2 * 2 * 2 * 2 * 2 * 1 = 32

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<conio.h> int hasil; int rekursif(int x,int n); void main() { char input[3]; int n,x; printf("\n\tPROGRAM PENGITUNG NILAI x^n\n"); printf("\t---------------------------\n"); printf("\n\tMasukkan nilai x dan n,\n\tuntuk menghitung nilai x pangkat n\n"); printf("\n\tMasukkan nilai x: "); gets(input); x=atoi(input); printf("\tMasukkan nilai n: "); gets(input); n=atoi(input); hasil=n; rekursif(x,n); printf("\tHasil = %d\n",hasil); getche(); }


6

int rekursif(int x,int n) { if(hasil==n) { if(n%2==0) { hasil=rekursif(x,n/2)*rekursif(x,n/2); return hasil; } else { hasil=rekursif(x,n/2)*rekursif(x,n/2)*x; return hasil; } } else { if(n==0) return 1; else { hasil=x*rekursif(x,n-1); return hasil; } } }

Preview :

4. #include<stdio.h> #include<conio.h> int jumlah=0; main() { void pindah(int,char,char,char); int n; printf("\n"); printf(" ^_^\n");


7

printf(" (^ ^) \n"); printf(" - \n"); printf(" /| || \n"); printf(" |||\n"); printf("\n\tSELAMAT DATANG DI TOWERS OF HANOI\n\n"); printf("\n\tMasukkan banyaknya piringan emas = "); scanf("%d",&n); pindah(n,'A','C','B'); printf("\n\tjumlah=%d",jumlah); getch(); } void pindah(int n,char dari,char ke,char temp) { if(n>0) { pindah(n-1,dari,temp,ke); printf("\tPindahkan Piringan %d dari %c ke %c\n",n,dari,ke); jumlah++; pindah(n-1,temp,ke,dari); } return; }

Preview :


8

rekursif

Documents