Rekursi dan Induksi

            Di dalam mata kuliah matematika diskrit saya diajarkan tentang rekursi dan induksi. Dua hal tersebut sangatlah penting dalam matematika diskrit begitu juga untuk kelas pemrogaman. Di blog saya ini saya akan mencoba sedikit menjelaskan apa itu rekursi dan induksi. Sekedar berbagi saja kepada para mahasiswa lain yang juga belajar tentang matematika diskrit atau pemrogaman.
   

                                        Rekursi

*      Rekursi merupakan alat ataupun cara untuk memecahkan masalah dalam suatu fungsi yang memanggil dirinya sendiri
 

*       Rekursi juga dapat berarti algoritma yang dapat mengeksekusi dirinya sendiri
 

*     Tujuan dari algoritma rekursi ini adalah untuk memecah problem yang kompleks menjadi lebih simpel dan kecil dengan cara setiap problem kecil yang ada diselesaikan dan menjadi bagian dari solusi masalah utama
   

*       Salah satu pengaplikasian rekursi adalah pada deret bilangan fibbonaci.

Misalkan ada deret fibbonaci dimulai dari nol maka muncullah deret 0,1,1,2,3,5,8,…

Kemudian secara rekursif deret tersebut dapat didefinisikan sebagai

Deret Fibbonaci : x0, x1, x2, ….

Dimana : x0 = 0 dan x1=1

Sehingga bisa kita ketahui bahwa xn=xn-1+xn-2

Salah satu contohnya untuk mendapat x5 diperoleh dengan cara = x4+x3 = 1+2 =3
  

*       Salah satu penggunaan rekursi lainnya adalah pada bilangan faktorial.

Fungsi faktorial dari bilangan bulat positif n dapat didefinisikan seperti ini

n! = n.(n-1)!, jika n > 1 dan n! = 1, jika n = 0 atau 1

contoh : 4! = 4. 3! = 4. 3 . 2. 1 = 24

Fungsi penghitung faktorial bisa ditulis sebagai berikut:

1.                 int Faktorial(int n)

2.      {

3.                   if ((n == 0) || (n == 1 ))

4.                               return (1);

5.                   else

6.                               return (n * Faktorial(n-1));

7.      }

Dari perhitungan ini bisa dilihat kita terlebih dahulu melihat apakah nilai n itu 0 atau 1 kalau misalnya 0 atau 1 maka nilainya pasti 1. Jika nilai n tidak sama dengan 0 atau 1 maka kembali ke nilai n* faktorial (n-1). Inilah yang dinamakan proses rekursi dimana fungsi faktorial ini memanggil dirinya sendiri tetapi dengan parameter (n-1). 

Induksi

*    Induksi adalah sebuah cara untuk membuktikan bahwa sebuah persamaan bernilai benar untuk semua bilangan asli dan tidak terbatas

*        Langkah langkah pembuktian secara induksi adalah sebagai berikut:

1.      Buktikan bahwa P(1) adalah benar, sering juga disebut base case

2.      Buktikan jika P(n) benar, maka P(n+1) juga benar

3.      Jika telah dibuktikan bahwa P(n+1) itu juga benar maka dapat disimpulkan bahwa untuk semua nilai n dalam P(n) adalah benar

*        Contoh pembuktian secara induksi:

P(n) = 1+3+5+7+...+(2n-1) = n² atau jumlah n bilangan ganjil pertama sama dengan n²

Pertama kita menggunakan base case disini kita gunakan angka 1 sehingga

P(1) = 1² = 1 jadi pernyataan ini benar untuk base casenya

Kemudian kita anggap P(k) itu adalah benar untuk k = n sehingga

P(n) = 1+3+5+7+...+(2k-1) = n²

Kita anggap juga P(k+1) itu juga benar sehingga untuk k = (n+1) =

1+3+5+ …+(2n-1) +(2(n+1)-1) = n²

n² + {2(n+1) -1 } = n² + {2n+2 -1}

= n² + {2n+1} = (n+1)²

Karena P(n+1) telah dibuktikan benar maka bisa dipastikan fungsi ini benar semua bilangan n. Inilah pembuktian dengan cara induksi.