Another Recursion: Pascal’s Triangle

Segitiga Pascal, deretan koefisien binomial yang disusun dalam bentuk segitiga. Namanya diambil dari ahli matematika Perancis, Blaise Pascal. Okay, a picture will explain it better:

source: Wikipedia

Setiap baris selalu diawali dan diakhiri dengan angka 1. Dan elemen-elemen di antaranya didapat dari penjumlahan dua angka diatasnya. Secara sederhana bisa dirumuskan sebagai berikut:

Untuk:

Nilai elemen segitiga pascal = f(indexBaris, indexElemen)

dengan indexBaris dan indexElemen dimulai dari nilai 0.

maka:

f(x, 0) = 1

f(x, x) = 1

f(x, y) = f(x-1, y-1) + f(x-1, y)

And the C# implementation will be:

public static int ComputeElementValue(int indexBaris, int indexElemen)
{
	if(indexElemen == 0) return 1;
	if(indexElemen == indexBaris) return 1;
	return ComputeElementValue(indexBaris-1, indexElemen-1) +
                   ComputeElementValue(indexBaris-1, indexElemen);
}

Untuk mendapatkan deret nilai dalam satu baris cukup dilakukan looping dari 0 sampai indexBaris yang diinginkan, dengan code sebagai berikut:

public static int[] GenerateLine (int indexBaris)
{
	int[] result = new int[indexBaris+1];
	for(int indexElemen = 0; indexElemen <= indexBaris; indexElemen++)
	{
		result[indexElemen] = ComputeElementValue(indexBaris,indexElemen);
	}
	return result;
}

Selanjutnya untuk membentuk array segitiga pascal tinggal dilakukan looping untuk meng-generate baris mulai dari baris awal hingga baris akhir yang diinginkan.

public static int[][] GenerateTriangleArray(int barisStart, int barisEnd)
{
	int[][] result = new int[barisEnd-barisStart][];
	for(int i=barisStart;i<barisEnd;i++)
	{
		result[i] = GenerateLine (i);
	}
	return result;
}

Looping dan rekursi yang dilakukan bisa dibilang terlalu banyak dan tidak efisien, karena untuk menghitung tiap elemen program akan selalu melakukan rekursi sampai ke base dari segitiga pascal, yaitu baris ke 0. Jadi ketika menghitung satu elemen di baris ke-n maka program akan melakukan rekursi hingga n+n kali (menghitung dua elemen di atasnya, baru kemudian menjumlahkannya). Ini terjadi karena program memang tidak menyimpan state dari segitiga pascal yang sudah terbentuk tiap kali iterasi, tetapi murni menggunakan rekursi. Well, it was meant for recursion demonstration for the first place anyway, so no biggie. Keuntungan dari penggunaan metode ini adalah kita bisa mendapatkan nilai elemen di level ke-x dan elemen ke-y tanpa perlu membentuk segitiga secara penuh.

That’s all, thanks for reading. Please feel free to comment.

Source Code

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