DASAR-DASAR REKURSIF

DASAR-DASAR REKURSIF


ITERASI  VS  REKURSI

o   Iterasi adalah perulangan (looping) dengan menggunakan perintah perulangan :

·         For (………………..)

·         While ( ……………)

·         Do …………… While(………..)

o   Rekursi adalah Method yang memanggil dirinya sendiri baik secara langsung maupun secara tidak langsung.



 CONTOH KASUS

o   Bilangan Faktorial

o   Faktorial ( 4)

Ø  4 * 3 * 2 * 1

Ø  24



FAKTORIAL DENGAN ITERASI

// Faktorial ( 4)  1 * 2 * 3 * 4

Int hasil = 1;

 For (int i=4; i >=1; i- -) {

hasil * i ;

  hasil =

}

System.out.println(“Bilangan Faktorial = “ + hasil);



FAKTORIAL DENGAN REKURSI

public static int faktorial(int n){

        if(n==1){

            return 1;

        } else {

            return(n * faktorial(n - 1));

        }

    }

 public static void main(String[] args) {

    int bilangan = 4;

    jawab = faktorial(bilangan);

     System.out.println("Faktorial dari " + bilangan + " = " + jawab);

}



PENYELSEAIAN

public static int faktorial(int n){

        if(n==1){

            return 1;

        } else {

            return(n * faktorial(n - 1));

        }

    }







Faktorial(4)

(4 * Faktorial(3))

                           (3 * Faktorial(2))

                                                      (2 * Faktorial(1))

1



 APA ITU REKURSIF?



Method yang memanggil dirinya sendiri baik secara langsung maupun secara tidak langsung.



v  f(0) = 0; f(x) = 2 f(x-1) + x2

v  f(1) = 1; f(2) = 6; f(3) = 21; f(4) = 58



public static int f (int x) {

    if (x == 0) return 0;

    return 2 * f (x - 1) + x * x;

}



v  fib(n) = fib(n - 1) + fib(n - 2)





 PENYELESAIAN



public static int f (int x) {

    if (x == 0) return 0;

    return 2 * f (x - 1) + x * x;

}



X = 3

f(3) = 2 * f(2) + 3 * 3

   f(2) =  2 * f(1) + 2 * 2

        f(1) = 2 * f(0) + 1 * 1

            f(0) = 0

 f(3) = 21





METHOD/FUNGSI RECURSION



Fungsi yang memanggil dirinya, secara langsung atau lewat fungsi lain, disebut fungsi rekursif

Proses pemanggilan diri itu disebut rekursi (recursion).

Contoh:

Memangkatkan bilangan real tak nol dengan suatu pangkat bilangan bulat



Xn  = 1                                            jika n = 0

Xn  =  X * Xn – 1jika n > 0

Xn  = 1 / X-n  jika n < 0



/**

    Menghitung pangkat sebuah bilangan real

    (versi rekursif).

    @param x bilangan yang dipangkatkan (x != 0)

    @param n pangkatnya

*/

public static



double pangkatRekursif (double x, int n)



{

    if (n == 0) {

        return 1.0;

    } else if (n > 0) {



        return (x * pangkatRekursif (x, n - 1));

    } else {

        return (1 / pangkatRekursif (x, -n));



    }



}





BERAPA NILAI PANGKAT 4







 ALGORITME REKURSIF



v Ciri masalah yang dapat diselesaikan secara rekursif adalah masalah itu dapat di-reduksi menjadi satu atau lebih masalahmasalah serupa yang lebih kecil



v Secara umum, algoritme rekursif selalu mengandung dua macam kasus:



§  kasus induksi: satu atau lebih kasus yang pemecahan masalahnya dilakukan dengan menyelesaikan masalah serupa yang lebih sederhana (yaitu menggunakan recursive calls)

§  kasus dasar atau kasus penyetop (base case): satu atau lebih kasus yang sudah sederhana sehingga pemecahan masalahnya tidak perlu lagi menggunakan recursive-calls.



v  Supaya tidak terjadi rekursi yang tak berhingga, setiap langkah rekursif haruslah mengarah ke kasus penyetop (base case).



ATURAN REKURSIF

1.Punya kasus dasar

Kasus yang sangat sederhana yang dapat memproses input tanpa perlu

melakukan rekursif (memanggil method) lagi

2.Rekursif mengarah ke kasus dasar

3. Percaya.

Pada proses pemanggilan rekursif, asumsikan bahwa pemanggilan rekursif (untuk problem yang lebih kecil) adalah benar.



o   Contoh: pangkatRekursif (x, n)



§  Asumsikan: pangkatRekursif (x, n - 1) menghasilkan nilai yang benar.

§  Nilai tersebut harus diapakan sehingga menghasilkan nilai pangkatRekursif (x, n) yang benar?

§  Jawabannya: dikalikan dengan x



4. Aturan penggabungan: Hindari duplikasi pemanggilan rekursif untuk sub-problem yang

sama.





INFINITE RECURSION

public static int bad (int n)

{

    if (n == 0) return 0;

    return bad (n * 3 - 1) + n - 1;

}





N = 2

bad(2) = bad(5) + 1

Bad(5) = bad(14) + 4

Bad(14) = bad(41) + 13

Bad(41) =  bad(122) + 40





HOW IT WORKS?

·         Java VM menggunakan internal stack of activation records

·         Activation record dapat dilihat sebagai kertas yang berisi informasi tentang method

o   nilai parameter

o    variabel lokal

o   program counter (PC)

·         Ketika suatu method pR dipanggil, sebuah activation record untuk pR dibuat dan di-push ke dalam stack; saat ini pR adalah method yang sedang aktif

·         Ketika method pR selesai (return), stack di-pop;

method dibawah pR yang dipanggil.









TOO MUCH RECURSION



public static long s (int n){

    if (n == 1) {

        return 1;

    } else {

        return s (n - 1) + n;

    }



}



Di sebuah system, n >= 9410 tidak dapat dieksekusi





BILANGAN FIBONACCI



F0 = 0, F1 = 1, FN =  FN-1+ FN-2

0,1,1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...









 TUGAS



Buatlah Program Deret Fibonaci dengan menggunakan Rekursi



RINGKASAN





·         Method rekursif adalah method yang memanggil dirinya sendiri baik secara langsung maupun secara tidak langsung.

·         Aturan Rekursif

o   Definisikan base case: yang dapat memproses input tanpa perlu recursive lagi

o   Pada bagian rekursif pastikan akan bergerak menuju base case.

o   Asumsikan bahwa pemanggilan rekursif terhadap sub problem berjalan benar.

o   hindari duplikasi proses untuk nilai input yang sama dalam recursive call yang terpisah.

·         Bila memungkinkan lakukan tail recursive.