Rekursif dalam Algoritma

Rekursif merupakan alat untuk memecahkan masalah dalam suatu fungsi atau procedure yang memanggil dirinya sendiri. Menurut Niclaus Wirth "An object is said be recursive if it partially consist or is defines in terms of itself".

Pada dasarnya rekursif sering digunakan dalam perhitungan matematika, sebagai contoh pertimbangan fungsi factorial dan juga bilangan Fibonacci.

Logika Rekursif. adalah suatu fungsi berparamater yang memanggil dirinya sendiri dengan harga parameter yang berbeda.  Logika ini dipakai sebagai pengganti proses iterasi.  Kelebihan logika bentuk ini mudah dipahami alurnya, namun kelemahannya pada penggunaan register stack yang sangat membebani kecepatan jalannya program.

Bentuk dan sifat rekursif

• Ada bagian base case dan ada bagian general case
• Paling sedikit mempunyai general base
• Selalu dalam bentuk fungsi-fungsi
• Selalu menggunakan statement percabangan

Faktorial

Salah satu yang digunakan untuk menjelaskan rekursif adalah fungsi faktorial.  Fungsi faktorial dari bilangan bulat positif n didefinisikan sebagai berikut:

n!=(n.(n.1)!,    jika n>1

n!=1,               jika n=0,1

Algoritma:

Function Faktorial (input n;integer) -> integer

Deklarasi

{tidak ada}

Deskripsi

if(n=0) or (n=1) then

    return(1)

else

    return(1)

else

    return (n*Faktorial(n-1))

endif

Kombinasi

Function Kombinasi (input n, r:integer) -> real

Deklarasi

If (n<r) Then

    return (0)

else

    return (Faktorial(n)/Faktorial(r)*Faktorial(n-r)))

endif

Permutasi

Function Permutasi (input n, r:integer) -> real

Deklarasi

{tidak ada}

Deskripsi

if (n<r) then

    return (0)

else

    return (Faktorial(n)/Faktorial(n-r))

endif

Bilangan Fibonacci

fn=fn-1 + fn-2 untuk n>1

f0=0

f1=1

berikut ini adalah barisan bilangan Fibonacci mulai dari n=1

1 1 2 3 5 8 13 21 34

Algoritma:

Funtion Fibonacci (input n:interger) -> integer

Deklarasi Lokal

{tidak ada}

Deskripsi

if(n==1 || n==2) then

    return(1)

else

    return(1)

else

     return (Fibonacci(n-1)+Fibonacci(n-2))

endif