PENGULANGAN DAN PROGRAM REKURSIF

 Recursive

 Definisi Recursive

Recursive adalah proses pemanggilan dirinya sendiri (fungsi atau prosedur). Fungsi maupun prosedur yang memanggil dirinya disebut fungsi atau prosedur rekursif. Fungsi untuk suatu bagian program yang mengembalikan (menghasilkan) hanya satu nilai. Sebuah function call adalah suatu ekspresi jadi ia memberikan satu nilai.Procedure adalah suatu bagian program yang melakukan aksi/fungsi khusus, biasanya berdasarkan sekumpulan parameter. Sebuah procedure call adalah suatu statemen, jadi ia melakukan aksi. Banyak obyek dalam matematika didefinisikan dengan menampilkan suatu proses untuk  menghasilkan obyek-obyek tsb.

Misalnya : n faktorial (n!)didefinisikan sebagai produk dari semua integer diantara n dan 1. Contoh lain adalah bilangan asli. 1 adalah bilangan asli.Successor dari 1 adalah bilangan asli.

Perbedaan rekursi dengan prosedur/fungsi adalah rekursi bisa memanggil kedirinya sendiri tetapi prosedur atau fungsi harus dipanggil lewat pemanggil prosedur/fungsi. Ciri masalah yang dapat diselesaikan secara rekursif adalah masalah tersebut dapat direduksi menjadi satu atau lebih masalah-masalah serupa yang lebih kecil. Secara umum suatu algoritma rekursif selalu mengandung 2 macam kasus :

1. satu atau lebih kasus yang pemecahan masalahnya dilakukan dengan menyelesaikan masalah serupa yg lebih sederhana (menggunakan recursive call).

2. satu atau lebih kasus pemecahan masalahnya dilakukan tanpa recursive call. Kasus ini disebut kasus dasar atau penyetop. Supaya tidak terjadi rekursif tak hingga, maka setiap langkah rekursif haruslah mengarah ke kasus penyetop.

Sistem komputer mengikuti jalannya program yang rekursif biasanya dengan menggunakan suatu struktur data yang disebut stack. Ketika eksekusi program sampai pada suatu rekursif call, ia menghentikan sementara komputasi yg sedang dilaksanakannya sekarang untuk melakukan recursive call tsb, agar ia dapat kembali ke keadaan semula setelah recursive call itu selesai , ia harus menyimpan informasi yang cukup. Informasi yg diperlukan disebut activation frame.  Activation frame disimpan pada bagian memori yg diatur dalam benruk stack.  Rekursif yang berlapis-lapis dapat menghabiskan memori yang mengakibatkan stack overflow.  Masalah yg mempunyai solusi rekursif juga mempunyai solusi iteratif(menggunakan loop).  Versi iteratif seringkali lebih efisien daripada versi rekursif karena rekursif biasanya menggunakan memori yg lebih besar dan memerlukan waktu ekstra u/ penanganan stack of activation frame.

Contoh 1 menghitung faktorial :

n ! = 1 jika n = 0 atau n=1

n ! = n * (n-1) * (n-2) *…* 1, jika n > 0

FUNGSI REKURSIF

fungsi struktural rekursif adalah bahwa argumen untuk setiap panggilan rekursif adalah isi dari bidang input asli . Rekursi struktural mencakup hampir semua traversals pohon , termasuk pengolahan XML , pembuatan pohon biner dan pencarian, dan lain-lain . Dengan mempertimbangkan struktur aljabar dari alam nomor (yaitu , nomor alam adalah baik nol atau penerus nomor alam ) , fungsi seperti faktorial juga dapat dianggap sebagai rekursi struktural .

Rekursi generatif adalah alternatif :

Banyak algoritma rekursif terkenal menghasilkan sepotong yang sama sekali baru data dari data yang diberikan dan kambuh di atasnya . HtDP ( Cara Desain Program ) mengacu pada jenis ini sebagai rekursi generatif . Contoh rekursi generatif meliputi: gcd , quicksort , pencarian biner , mergesort , metode Newton , fraktal , dan integrasi adaptif [ 5 ] .

Pembedaan ini penting dalam membuktikan penghentian fungsi. Semua fungsi struktural rekursif pada terbatas ( didefinisikan secara induktif ) struktur data dapat dengan mudah ditampilkan untuk mengakhiri , melalui induksi struktural : intuitif , setiap panggilan rekursif menerima bagian yang lebih kecil dari input data , sampai kasus dasar tercapai . Generatif fungsi rekursif , sebaliknya, tidak selalu memberi masukan yang lebih kecil untuk panggilan rekursif mereka, sehingga bukti pemutusan mereka tidak selalu sebagai sederhana, dan menghindari loop tak terbatas membutuhkan perawatan yang lebih besar . Fungsi-fungsi rekursif generatif sering dapat diartikan sebagai fungsi corecursive - setiap langkah menghasilkan data baru , seperti pendekatan berturut-turut dalam metode Newton - dan mengakhiri corecursion ini mensyaratkan bahwa data akhirnya memenuhi beberapa kondisi , yang tidak selalu dijamin .

Dalam hal varian lingkaran , rekursi struktural adalah ketika ada loop varian yang jelas , yaitu ukuran atau kompleksitas , yang dimulai terbatas dan menurun pada setiap langkah rekursif . Sebaliknya , rekursi generatif adalah ketika tidak ada seperti loop varian jelas, dan pemutusan tergantung pada fungsi, seperti " kesalahan pendekatan " yang tidak selalu menurun ke nol , dan dengan demikian pemutusan tidak dijamin tanpa analisis lebih lanjut

 Parameter and local Variable

Stacks  adalah Struktur data dimana data yang terkhir masuk adalah data yang akan diproses terlebih dahulu. Stack biasanya dimplementasikan dengan menggunakan sebuah array,dalam stack kita bisa menambah data dengan perintah operasi push,dan menghapus data dengan menggunakan perintah operasi pop

•   Fungsi Rekursi pada Matematika

Banyak fungsi matematika yang dapat didefinisikan dengan rekursi.

Contoh: fungsi faktorial dari n (n!), dapat didefinisikan secara iteratif :

0! Adalah 1 dan  n! Adalah n x (n-1)!, untuk n>0

Misal: 4! Adalah 4 x 3!, yang artinya 4 x 3 x 2 x 1, atau 24

             

•   Fungsi rekursi untuk faktorial

Program :

//menghitung n! Menggunakan definisi rekursi

//pre : n>=0

int factorial (int n){

int ans;

if (n == 0)

ans = 1;

else

ans = n * factorial (n-1);           return(ans);

}

1.  Iteratif untuk faktorial

Program :

//menghitung n! Menggunakan iteratif

//pre : n>=0

int factorial (int n){

int i; /*variabel lokal */

Product =1;

for (i=n; i>1; –i) {

product=product * i;

}

return(product);

}

Contoh :

package praktikGolD;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class RekursifFaktorial {
    public static void main(String[] args){
        System.out.print("Masukkan Bilangan yang akan difaktorialkan :");
        final int bilangan = inputData();
        System.out.print("Faktorial dari \n "+bilangan+" adalah \n"+FAKTORIAL(bilangan)+" \n mudahkan");
    }
    private static int FAKTORIAL(int bilangan) {
        if(bilangan == 0)
            return 1;
        else
            bilangan = (bilangan * FAKTORIAL(bilangan - 1));
            return bilangan;
     
    }

    private static int inputData() {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        String angkaInput = null;
        try{
            angkaInput = bfr.readLine();
        }
        catch(IOException e){
            e.printStackTrace();
        }
        int Data = Integer.valueOf(angkaInput).intValue();
        return Data;
    }
}// ahir coding

contoh keluaran dari program

  Iteratif  dan  rekursi

1.      Persamaan dan perbedaan Iteraktif dan rekursif

• Persamaan

–        Sama-sama merupakan bentuk perulangan

–        Dilakukan pengecekan kondisi terlebih dahulu sebelum mengulang

• Perbedaan

–        Pada rekursi, dikenal adanya istilah recursive step

–        Sedangkan pada iteratif ada decrement

2.     Kelebihan dan kekurangan recursive

• Kelebihan

–        solusi sangatlah efisien

–        dapat memecahkan masalah yang sulit dengan tahapan yang mudah dan singkat

• Kelemahan

–        sulit dipahami

–        perlu stack besar (stack overrun)

 

Faktorial

Sebuah contoh klasik dari prosedur rekursif adalah fungsi yang digunakan untuk menghitung faktorial nomor alami:

    \ Operatorname {} fakta (n) = \ begin {} kasus 1 & \ mbox {if} n = 0 \ \ n \ cdot \ operatorname {} fakta (n-1) & \ mbox {if} n> 0 \ \ \ {kasus} end

Pseudocode (rekursif):

fungsi faktorial adalah:
Input: integer n sehingga n> = 0
Output: [n × (n-1) × (n-2) × ... × 1]

    1. jika n adalah 0, kembali 1
    2. jika tidak, kembali [n × faktorial (n-1)]

mengakhiri factorial

Fungsi ini juga dapat ditulis sebagai relasi rekurensi :

    b_n = nb_ { n - 1 }
    b_0 = 1

Ini evaluasi relasi rekurensi menunjukkan perhitungan yang akan dilakukan dalam mengevaluasi pseudocode di atas :
Komputasi relasi rekurensi untuk n = 4 :

b4 = 4 * b3
             = 4 * ( 3 * b2 )
             = 4 * ( 3 * ( 2 * b1 ) )
             = 4 * ( 3 * ( 2 * ( 1 * b0 ) ) )
             = 4 * ( 3 * ( 2 * ( 1 * 1 ) ) )
             = 4 * ( 3 * ( 2 * 1 ) )
             = 4 * ( 3 * 2 )
             = 4 * 6
             = 24

Fungsi faktorial ini juga dapat digambarkan tanpa menggunakan rekursi dengan memanfaatkan khas looping konstruksi ditemukan dalam bahasa pemrograman imperatif :
Pseudocode ( berulang ) :

fungsi faktorial adalah :
Input : integer n sehingga n > = 0
Output : [ n × ( n - 1 ) × ( n - 2 ) × ... × 1 ]

    1 . menciptakan variabel baru yang disebut running_total dengan nilai 1

    2 . mulai lingkaran
          1 . jika n adalah 0 , keluar dari loop
          2 . mengatur running_total ke ( running_total × n )
          3 . penurunan n
          4 . ulangi lingkaran

    3 . kembali running_total

mengakhiri faktorial

Kodepentingdi atas adalahsetara dengandefinisimatematikainimenggunakanakumulatorvariabelt:

Definisi di atas diterjemahkan langsung untuk bahasa pemrograman fungsional seperti Skema, ini adalah contoh dari iterasi dilaksanakan secara rekursif.
Greatest pembagi umum

Algoritma Euclidean, yang menghitung pembagi bersama terbesar dari dua bilangan bulat, dapat ditulis secara rekursif.

Fungsi Definisi: 

Pseudocode (rekursif):

Fungsi FPB adalah:
Input: integer x, integer y sehingga x> = y dan y> = 0

     1. jika y adalah 0, kembali x
     2. jika tidak, kembali [gcd (y, (sisa x / y))]

end FPB

Relasi rekurensi untuk pembagi terbesar umum, di mana x% y mengungkapkan sisa x / y:

     \ FPB (x, y) = \ gcd (y, x% y)
     \ FPB (x, 0) = x

Komputasi relasi rekurensi untuk x = 27 dan y = 9:

FPB (27, 9) = FPB (9, 27% 9)
              = FPB (9, 0)
              = 9

Komputasi relasi rekurensi untuk x = 259 dan y = 111:

FPB (259, 111) = FPB (111, 259% 111)
                 = FPB (111, 37)
                 = FPB (37, 0)
                 = 37

Program rekursif di atas adalah tail-rekursif, itu adalah setara dengan sebuah algoritma iteratif, dan perhitungan di atas menunjukkan langkah-langkah evaluasi yang akan dilakukan oleh bahasa yang menghilangkan panggilan ekor. Di bawah ini adalah versi algoritma yang sama dengan menggunakan iterasi eksplisit, cocok untuk bahasa yang tidak menghilangkan panggilan ekor. Dengan mempertahankan keadaan sepenuhnya di variabel x dan y dan menggunakan konstruksi perulangan, program ini menghindari membuat panggilan rekursif dan berkembang panggilan stack.

Pseudocode (berulang):

Fungsi FPB adalah:
Input: integer x, integer y sehingga x> = y dan y> = 0

     1. membuat variabel yang disebut baru sisanya
     2. mulai lingkaran
           1. jika y adalah nol, keluar dari loop
           2. mengatur sisanya untuk sisa x / y
           3. set x ke y
           4. mengatur y ke sisa
           5. ulangi lingkaran
     3. kembali x

end FPB

Algoritmaiteratifmemerlukanvariabel sementara, danbahkan diberipengetahuan tentangalgoritmaEuclideanlebih sulituntuk memahamiproses denganpemeriksaansederhana, meskipun duaalgoritmayang sangat mirip dalamlangkah-langkah mereka.

Pada kesempatan kaliini,, saya akan menjelaskan tentang cara menghitung faktorial.....
faktorial dari bilangan asli n adalah hasil perkalian antara bilangan bulat positif yang kurang dari atau sama dengan n

:: lambang faktorial adalah !

contoh pengerjaan faktorial sebagai berikut ::
3 ! = 3 x 2 x 1 = 6

import javax.swing.JOptionPane;

public class Faktorial {
static int faktorial(int h) {
int r = 1;
for(int i = h; i >= 1; i--) {
r *= i;
}
return r;
}
public static void main(String[] args) {
String numStr = JOptionPane.showInputDialog("Masukkan angka integer");
int numInt = Integer.parseInt(numStr);

int hasil = faktorial(numInt);

JOptionPane.showMessageDialog(null, "Nilai Faktorial " + numStr + "\n" +
hasil);
}
}

#include <stdio.h>
int faktorial (int N);             /*prototype fungsi factorial*/
void main()
{
int N;
printf (“berapa factorial ? “);scanf(“%d”,&N);
faktorial(N);                 /* pemanggilan fungsi faktorial */
}

/* fungsi untuk menghitung nilai N factorial */
int faktorial(int N)             /* definisi fungsi */
{
int I;
int F=0;
int Fak;
int Terakhir=1;
if(N==0)                       /* ingat! bahwa faktor dari 0 adalah 1 */
return(faktorial(1));          /*rekursi*/
else
for(I=N;I>1;I–)
{
printf(“%d+”, I);
F=F+I;                   /* fungsi penjumlahan untuk setiap perulangan */
}
Fak=F+1;                       /* mengembalikkan nilai N */
printf(“%d=%d\n”,Terakhir,Fak);          /* 1 merupakan angka BANTU */

}

 MENARA HANOI

Menara Hanoi adalah sebuah permainan matematis atau teka-teki.Permainan ini terdiri dari tiga tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja.Permainan dimulai dengan cakram-cakram yang tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, cakram terkecil diletakkan teratas, sehingga membentuk kerucut.
Tujuan dari teka-teki ini adalah untuk memindahkan seluruh tumpukan ke tiang yang lain, mengikuti aturan berikut:

• Hanya satu cakram yang boleh dipindahkan dalam satu waktu.
• Setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain, di atas cakram lain yang mungkin sudah ada di tiang tersebut.
• Tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil. 

menara hanoi

Asal
Teka-teki ini ditemukan Édouard Lucas, ahli matematika Perancis di tahun 1883.Ada sebuah legenda tentang candi Indian yang berisi ruang besar dengan tiga tiang yang dikelilingi 64 cakram emas. Pendeta Brahma, melaksanakan tugas dari peramal di masa lalu, sesuai dengan aturan teka-teki ini. Menurut legenda ini, bila teka-teki ini diselesaikan, dunia akan kiamat. Tidak jelas benar apakah Lucas menemukan legenda ini atau terinspirasi olehnya.
Bila legenda ini benar, dan pendeta itu bisa memindahkan satu cakram tiap detik, menggunakan pemindahan paling sedikit, maka akan memakan waktu 2⁶⁴−1 detik atau kurang lebih 584,582 milyar tahun.

Penerapan

Permainan Menara Hanoi sering digunakan dalam penelitian psikologis dalam hal pemecahan masalah.Selain itu, juga sering digunakan dalam pengajaran algorima rekursif bagi pelajar pemrograman.Permainan ini juga digunakan sebagai ujian ingatan oleh ahli psikolog syaraf dalam berupaya mengevaluasi amnesia.

Solusi 
Dengan berbagai macam metode penghitungan dan penelitiannya, permainan Menara Hanoi ini akhirnya terpecahkan dengan solusi :

Jika terdapat sejumlah n cakram pada permainan menara hanoi, maka banyaknya perpindahan yang terjadi (tetap mengikuti aturan permainan) hingga semua n cakram sampai di tiang tujuan adalah 2ⁿ − 1 perpindahan.  

 Jadi begini, asumsikan bahwa tiang pertama merupakan tiang asal, tiang yang di tengah merupakan tiang bantu, dan yang disebelah kanan merupakan tiang tujuan. Jadi terdapat 4 buah cakram yang terdapat pada tiang asal, yang akan dipindahkan ke tiang tujuan. Cara memindahkannya yaitu dengan memanfaatkan tiang bantu yang ada di tengah. Mulailah memindahkan cakram yang paling atas, yaitu yang paling kecil.Dilanjutkan dengan memindahkan cakram yang paling atas dari tiang asal ke tiang lainnya yang masih kosong.Demikian selanjutnya, anda harus menyusun cakram tersebut mulai yang terbesar diletakkan di bawah, dan semakin ke atas ukuran cakramnya semakin kecil, dengan syarat dalam satu perpindahan hanya satu cakram yang dipindahkan.

Untuk kasus seperti pada contoh animasi pemecahan Menara Hanoi di atas, terdapat 4 cakram yang akan dipindahkan. Jadi menurut solusi permindahan Hanoi, maka
perpindahan.

Dan, dengan semakin majunya ilmu pengetahuan, atau entah karena semakin pinternya manusia jaman sekarang, maka mulailah dibuat program untuk memecahkan masalah Tower of Hanoi tadi. Untuk menyelesaikan puzzle di atas dalam pemrograman, kita dapat menggunakan teknik rekursif. Rekursif adalah fungsi atau prosedure yang dapat memanggil dirinya sendiri.

Berikut ini contoh program java nya :

import java.util.*;
public class hanoi
{
    static int i = 1;
    public static void main (String [] args)
    {
        Scanner var = new Scanner (System.in);
        System.out.print ("Banyaknya piringan = ");
        int n = var.nextInt ();
        hanoi (n, 'A', 'B', 'C');
    }
   
    public static void hanoi (int n, char Asal, char Bantu, char Tujuan)
    {
        if (n == 1)
        {
            System.out.println("Langkah ke "+i+++", pindahkan piringan ke "+n+" dari "+Asal+" ke "+Tujuan);
           
        }
        else
        {
            hanoi(n-1, Asal, Tujuan, Bantu);
            System.out.println ("Langkah ke "+i+++", pindahkan piringan ke "+n+" dari "+Asal+" ke "+Tujuan);
            hanoi (n-1, Bantu, Asal, Tujuan);
}}}

Outputnya :

 

Jika anda mengalami stuck dalam permainan Tower of Hanoi tadi, anda dapat menggunakan program di atas untuk menyelesaikan puzzle tersebut dengan cara mengikuti langkah-langkahnya satu persatu.
Selamat mencoba :)

Jadi apa sih Menara Hanoi itu ?

Sebuah permainan dimana sejumlah piringan dipindahkan dari tonggak satu ke tonggak lainnya dan dapat menggunakan tonggak bantuan .

 
 

Caranya semua piringan di tonggak A akan dipindahkan ke tonggak C secara satu persatu dan piringan yang besar tidak boleh diletakkan di atas piringan yang kecil.

Untuk lebih jelasnya soal prosesnya bisa lihat gambar di bawah ini 

Untuk menyelesaikan puzzle di atas dalam pemrograman, kita dapat menggunakan teknik rekursif. Rekursif adalah fungsi atau prosedure yang dapat memanggil dirinya sendiri.

Jadi algoritmanya adalah …

Kalau N = 1 maka

N dipindahkan dari A ke C secara langsung

Tapi kalau N > 1 maka

pindahkan N-1 dari A ke B

pindahkan N dari A ke C

pindahkan N-1 dari B ke C

catatan :

N = banyaknya piringan

 

Deskripsi Tree

—  Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon.

—  Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah.

—  Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.

- Contoh penggunaan struktur pohon :

• Silsilah keluarga
• Parse Tree (pada compiler)
• Struktur File
• Pertandingan

Struktur Pohon

Operasi-operasi Pada Tree

• Insert: menambah node ke dalam Tree secara rekursif.  Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri.  Untuk data pertama akan menjadi elemen root.
• Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu.  Syaratnya adalah tree tidak boleh kosong.
• Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.
• Count: menghitung jumlah node dalam Tree.
• Height : mengetahui kedalaman sebuah Tree.

·      Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree.

·      Child : mengetahui anak dari sebuah node (jika punya).

·      Daun/leaf : Simpul yang derajat = 0 disebut daun / leaf

·      Hubungan antar simpul : bapak, ,anak, paman, dll

·      Tingkat (level)

·      Derajat (degree)

·      Tinggi (height)/kedalaman (depth) : height = tingkat maksimum – 1

·      Ancestor : semua simpul yang terdapat pada lintasan/jalur dari akar sampai simpul tersebut

·      Forest (Hutan) : kumpulan sejumlah pohon yang tidak saling berhubungan

- Jenis Tree

• Berdasarkan banyaknya anak :

1. binary tree / pedigree chart : Complete Binary Tree tingkat N,Skewed BinaryTree
2. Non Binary Tree (N-ary) & lineal chart

• Dari pentingnya urutan Isi :

1. Ordered tree
2. non ordered tree

- Jenis Traverse

1. PreOrder: cetak node yang dikunjungi, kunjungi left, kunjungi right
2. InOrder: kunjungi left, cetak node yang dikunjungi, kunjungi right
3. PostOrder: kunjungi left, kunjungi right, cetak node yang dikunjungi.

- Cara Penulisan Tree :

• 1. Diagram venn
• 2. Notasi Kurung

- Representasi Lojik

Type Infotype : …………{terdefinisi}
Type address : ………{terdefinisi, sesuai dengan representasi fisik}
Type Node : < Info : Infotype,
Left : address,
Right : address >
Type BinTree : address
Jika P adalah binary tree, maka
Left (P) : mendapatkan alamat cabang kiri dari P
right (P) : mendapatkan alamat cabang kanan dari P
info (P) : mendapatkan bagian info dari node yang ditunjuk P

PRIMITIF-PRIMITIF

• Make Tree

  

• Menyisipkan simpul baru pada binary search Tree

 

• Pengecekan predikat penting

 

- Algoritma Traversal Tree