String & Rekursif : Call Trace Ackerman Function & Fungsi Rekursif Tanpa Base Case

7 12 2009

5.   Ackerman function merupakan fungsi yang menerima dua argument bertipe integer. Fungsi ini didefinisikan sebagai berikut.

A(0, n) = n + 1                  untuk n >= 0

A(m, 0) = A(m-1, 1)          untuk m >= 0

A(m, n) = A(m-1, A(m, n-1))        untuk m, n>0

Dengan menggunakan call trace, carilah nilai A(3, 3)!

  • Call Trace Ackerman Function :

A(3, 3) = A(2, A(3, 2))

A(2, A(2, A(3, 1)))

A(2, A(2, A(2, A(3, 0))))

A(2, A(2, A(2, A(2, 1))))

A(2, A(2, A(2, A(1, A(2, 0)))))

A(2, A(2, A(2, A(1, A(1, 1)))))

……………………………………… Dan Seterusnya.

Note : Jika diteruskan sampai akhir akan mendapatkan output 61

6.  Amati dan analisislah potongan program berikut ini:

void CobaRekursi(int n) {
         printf("Ini fungsi CobaRekursi\n");
         CobaRekursi(n-1);
}
  • Apa yang salah dalam potongan program diatas? Berikan alasan dan bukti Anda!

Kesalahan dari potongan program tersebut adalah tidak terdapat base case pada fungsi tersebut yang dapat menghentikan proses pemanggilan berulang pada fungsi tersebut saat dipanggil. Fungsi tersebut bila dipanggil akan menghasilkan perulangan tak terbatas sebagai akibat tidak adanya base case yang dapat digunakan untuk menghentikan proses perulangan tersebut.

  • Jika potongan program tersebut disusun dalam bentuk utuh menjadi :

Algoritma Program :

  1. Program menampilkan statemen ”Menguji program CobaRekursi”.
  2. Program menampilkan instruksi kepada user untuk memasukkan input.
  3. Program memanggil fungsi cobarekursi.
  4. Fungsi cobarekursi menampilkan string ”Ini fungsi CobaRekursi” tanpa batas.

Source Code Program :

#include<stdio.h>

#include<conio.h>

void CobaRekursi(int);

void main()

{

int m;

puts("Menguji program CobaRekursi");

printf("Masukkan nilai input: ");

scanf("%d", &m);

CobaRekursi(m);

getch();

}

void CobaRekursi(int n) {

printf("Ini fungsi CobaRekursi\n");

CobaRekursi(n-1);

}

Note : Jika program tersebut dikompile, compiler  akan mengalami error karena program akan dijalankan terus – menerus tanpa batas. Walaupun demikian, output program masih bisa ditampilkan.

Posted By : Evan Yofiyanto @ Evan’s Blog : Kuliah Informatika (kuliahinformatika.wordpress.com)

[FREAX]


Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: