Pertemuan 5:

INF202: Struktur Data

REKURSI

Dosen: Wayan Suparta, PhD

REKURSIF

• Rekursif adalah salah satu metode dalam dunia matematika

dimana definisi sebuah fungsi mengandung fungsi itu sendiri.

• Dalam dunia pemrograman, rekursi diimplementasikan dalam

sebuah fungsi atau procedure yang dapat memanggil dirinya

sendiri baik langsung maupun tidak langsung.

• Contoh;

Jika y > 0, bentuk pemangkatan muncul kembali di sisi

kanan. Itulah yang disebut rekursif.

1,0

1

1

)(*

)(

njika

njikanFn

nF

Contoh:

Iterasi

• Artinya

– perkataan berulang-ulang

– peralatan yang lebih efisien jika dibandingkan

dengan rekursif tetapi recursion menyediakan

solusi yang lebih baik untuk suatu masalah.

• Jadi:

– Pada rekursif, metode dapat memanggil dirinya

sendiri.

– Data yang berada dalam metode tersebut seperti

argument disimpan sementara ke dalam stack

sampai metode pemanggilnya diselesaikan.

Contoh Fungsi Rekursif

Misalkan F = faktorial (5)

• Konsep Faktorial

n! = n(n-1)(n-2)…

• Dapat diselesaikan

dengan

– Cara Biasa

– Rekursif

Faktorial: Cara Biasa

• int Faktorial(int n)

• {

• if (n<0) return -1 ;

• else if (n>1)

• {

• S = 1 ;

• for(i=2 ;i<=n;i++) S = S * n ;

• return S ;

• }

• else return 1 ;

• }

Faktorial Cara

Rekursif

• int Faktorial (int n)

• {

if (n<0) return -1

else if (n>1)

return (n*Faktorial(n-1))

else return 1 ;

• }

Bilangan Fibonacci

Bilangan Fibonacci

• Baris dari n=1

1 1 2 3 5 8 13 21 34 55 89 ….

• Algoritma (untuk n > 2):

fn = fn-1 + fn-2

f1 = 1

f2 = 1

int main(){

int n,a,b,f,c;

cout<<"Masukan banyaknya bilangan: ";

cin>>n;

a=0; b=1;

cout<<"1";

Misal: n= 4 f4 = f3+f2

f4 = (f2+f1) + f2 f4 = (1+1) +1 f4 = 3

for(c=1;c<=n-1;c++){

f=a+b;

a=b;

b=f;

cout<<" "<<f;

}

system ("pause"); }

Jadi, fungsi Fibonacci

Basis: fib(0) = 0; fib(1) = 1

Rekursif: fib(n) = fib(n – 1) + fib(n – 2)

Ditulis dengan cara lain:

n jika n = 0, 1

fib(n) =

fib (n – 1) + fib (n – 2) jika n > 1

Kombinasi

int faktorial (int n)

{

int fak;

if (n<=1) {

fak=1; }

else {

fak=n*faktorial(n-1); }

return (fak);

}

Permutasi

int faktorial (int n)

{

int r, hasil;

if (n<r)

{

hasil=1;

}

else

{

hasil = faktorial(n)/faktorial(n-r); //Proses perhitungan permutasi akan dijalankan

}

return (hasil);

}

Flowchart Permutasi dan Kombinasi

Kasus-1: Output deretS

=1+2+3+4+5+...+n

int n=5,i,bil;

for(i=1; i<=n; i++)

{

bil=i;

printf(" %d",bil);

}

Kasus-2; Output deret S =

2+4+6+8+10+...+2n

int n=5,i,bil;

for(i=0; i<=n; i++)

{

bil=2*i;

printf(" %d",bil);

}

Menara Hanoi

Menara Hanoi

Untuk memindahkan n piringan dari tiang A ke tiang B:

1. Pindahkan (n-1) piringan dari tiang A ke tiang C

2. Pindahkan 1 piringan (terbesar) dari tiang A ke tiang

C

3. Pindahkan (n-1) piringan dari tiang B ke tiang C

H(n) : untuk memindahkan n piringan

1. H(n-1) pemindahan

2. 1 pemindahan total: 2 H(n-1) + 1

3. H(n-1) pemindahan

Jika n = 3, maka ada 7 kali pemindahan

Menara Hanoi

1.

2.

3.

4.

5.

6.

7.

A B C

CONTOH:

#include <stdio.h>

#include <iostream>

using namespace std;

int faktorial (int x);

int main()

{

int n,r, kombinasi;

cout<<"Program Menghitung Kombinasi (nCr)"<<endl;

cout<<"Masukkan Nilai n : "; cin>>n;

cout<<"Masukkan Nilai r : "; cin>>r;

kombinasi=faktorial(n)/(faktorial(r)*faktorial(n-r));

cout<<" Kombinasinya adalah: "<<kombinasi;

}

…………. Sambungan lihat slide sebelumnya (kombinasi)

LATIHAN 10 A. Buat program yang dapat menampilkan deret Fibonacci

hingga mendekati nilai 1000.

B. Buatlah sebuah program pemangkatan dengan rekursif.

C. Buat sebuah program yang dapat menghitung berapa cara

memasang 5 umbul-umbul sepanjang suatu gang yang terdiri

dari 2 umbul-umbul merah dan 3 umbul-umbul kuning?

D. Buat sebuah program yang dapat menghitung jumlah jabatan

tangan antara mereka dalam suatu pertemuan yang dihadiri

15 peserta, jika masing-masing peserta saling berjabat

tangan.

E. Buat sebuah flowchart dan program yang dapat membalikkan

kata, misalnya ”MALANG” ”GNALAM”.

LATIHAN 12

Realisasikan dalam sebuah program.

Jika banyak piring ada 5, berapa kali perpindahannya ke B?

LATIHAN 13

a). b).

Realisasikan dalam sebuah program: