REKURSIF

contoh fungsi rekursif

#include<stdio.h>

void rekursi(int n);

main()

{ int x=3;

rekursi(x);

/* Pemanggilan Fungsi */

}

void rekursi(int n) { static int j=0;

if(n<=0) return;

printf("rekursi ke-%d\n",++j); rekursi(n-1);

/* Kondisi Perhentian pemanggilan fungsi kembali */

/* Pemanggilan fungsi rekursi di dalam fungsi rekursi */

}



Program Fibonacci dengan Rekursif

#include <stdio.h>

int fibo(int n);

int main () {

int x;

printf("Menampilkan deret Fibonacci\n"); printf("Batas suku bilangan ke : "); scanf("%d", &x);

printf(“Deret ke %d = %d”, x, fibo(x)); printf("\n\nDeret fibonacci : \n");

for(int i=1; i<=x; i++)

printf("%d ",fibo(i)); /* Pemanggilan deret Fibonacci sebanyak x kali */

return 0;

}

int fibo(int n) {

if (n==1) return 1;

else if(n==2) return 1;

else

return fibo(n-2)+ fibo(n-1);

}

Hasil Running:

Menampilkan deret Fibonacci Batas suku bilangan ke : 5 Deret ke 5 = 5

Deret fibonacci : 1 1 2 3 5

Penjelasan program:

Deret fibonacci mempunyai nilai suku-suku bilangan berikut:

0, 1, 1, 2, 3, 5, 8, 13, 21, ............

96


Ciri khusus deret ini adalah tiap-tiap suku adalah hasil penjumlahan dari nilai dua suku sebelumnya. Misalnya adalah nilai suku ke dua adalah penjumlahan nilai suku ke 0 (bernilai 0) dengan suku ke 1 (bernilai 1) jadi nilai suku ke 2 adalah sama dengan 1 (0 + 1). Nilai suku ke tiga adalah nilai suku ke dua ditambah nilai suku ke satu. Misalnya untuk mencari bilangan fibonacci ke- 5, maka urutan pengerjaannya adalah sebagai berikut:

fibo(5)

fibo(3)
 fibo(4)

fibo(1)
 fibo(2)
 fibo(2)

fibo(1)

fibo(3)

fibo(2)

Dari diagram terlihat bahwa untuk mendapatkan deret ke 5 dari deret fibonacci maka fungsi fibo(4) dihitung satu kali, fungsi fibo(3) dihitung dua kali, fungsi fibo(2) dihitung tiga kali dan fungsi fibo(1) dihitung dua kali. Hal ini menyebabkan proses lebih lama dan juga sumber daya yang dibutuhkan untuk menangani proses ini lebih banyak.

Listing Program 11.4 Program Fibonacci dengan Iteratif

#include <stdio.h>

int fibo(int n);

int main () {

int x;

printf("Menampilkan deret Fibonacci\n"); printf("Batas suku bilangan ke : "); scanf("%d", &x);

printf(“Deret ke %d = %d”, x, fibo(x)); printf("\n\nDeret fibonacci : \n");

for(int i=1; i<=x; i++)

printf("%d ",fibo(i)); /* Pemanggilan deret Fibonacci sebanyak x kali */

return 0;

}

int fibo(int n) {

int fb1, fb2, fn, i; if (n==1) return 1; if(n==2) return 1; fb1=1; fb2=1;

for (i=3; i<=n; i++) { fn = fb1 + fb2;

fb2= fb1; fb1= fn;

}

return fn;

}

97


Hasil Running:

Menampilkan deret Fibonacci Batas suku bilangan ke : 5 Deret ke 5 = 5

Deret fibonacci : 1 1 2 3 5

Penjelasan Program:

Dari listing program 11.4, terlihat bahwa setiap kali akan menghitung suku ke-n, maka nilai-nilai suku sebelumnya akan digunakan kembali, yaitu nilai dari n-1(variabel fb1) dan nilai dari n-2(variabel fb2). Pertama dihitung nilai dari deret ke-n, kemudian nilai dari deret n-1 diberikan kepada deret n-2, dan nilai dari deret n diberikan kepada deret n-1.



Referensi:

Deitel & Deitel, C How to Program 3rd Edition , Prentice Hall, New Jersey, 2001

Jogiyanto, Konsep Dasar Pemrograman Bahasa C , Andi Offset, Yogyakarta, 1993

Thompson Susabda Ngoen, Pengantar Algoritma dengan Bahasa C , Salemba Teknika, Jakarta, 2004