Rekursif

Rekursif
             Rekursif adalah salah satu metode dalam dunia matematika dimana definisi sebuah fungsi mengandung fungsi itu sendiri. Dalam dunia pemrograman, rekursi diimplementasikan dalam sebuah fungsi yang memanggil dirinya sendiri.
            Rekursif merupakan algoritma untuk memecahkan masalah menggunakan suatu fungsi yang memanggil dirinya sendiri. Sebenarnya permasalahan yang dapat diselesaikan menggunakan rekursi dapat diselesaikan tanpa rekursi namun hal tersebut sulit untuk dilakukan.Salah satu contoh implementasi rekusi adalah fungsi factorial
N! = 1 x 2 x 3 x 4 x … x(N-1) x N

Definisi
rekursif bisa menjelaskan situasi yang sangat kompleks dengan hanya sedikit kata-kata. Mendefinisikan istilah "ancestor" (nenek moyang) tanpa menggunakan rekursi mungkin akan sangat sulit seperti parent, atau grandparent, atau great-grandparent, atau great-great-grandparent, dan seterusnya. Tapi dengan mengatakan "dan seterusnya" maka tidak akan terlalu rumit. Hal yang sama terjadi ketika kita mendefinisikan sebuah "directory" sebagai "sebuah file yang merupakan daftar dari file-file, dimana beberapa file bisa merupakan daftar dari beberapa file, dimana beberapa dari file tersebut bisa merupakan daftar beberapa file, dan seterusnya". Begitu juga jika kita berusaha mendefinisikan statement dalam Java. Sebuah "statement" dalam Java bias berupa sebuah statement while, yang mana terdiri dari sebuah kata "while", sebuah kondisi bernilai boolean, dan suatu statement.
Rekursi bisa digunakan sebagai teknik programming. Sebuah subroutine rekursif adalah subroutine yang memanggil dirinya sendiri, baik secara langsung maupun tidak langsung. Program yang akan kita buat kali ini adalah algoritma rekursif untuk melakukan sorting pada sebuah array, mengurutkan item dari nilai terkecil ke yang terbesar. Algoritma Selection Sort dan Insertion sort cukup sederhana, tetapi keduanya agak lambat, ketika diterapkan pada array yang besar. Algoritma sortir yang paling cepat adalah Quicksort, sebuah algoritma rekursif.

List dan Rekursi
Rekursi dan list berjalan seiring seirama laksana fava beans dan chianti yang nikmat. Sebagai contoh, berikut ini merupakan algoritma untuk mencetak sebuah list dari bagian belakang:

1. Pisahlah list ke dalam dua bagian: node pertama (sebagai kepala (head)) dan sisanya (sebagai ekor (tail)).
2. Cetak ekornya dari belakang.
3. Cetak kepalanya.

Tentu saja, langkah kedua, pemanggilan rekursinya, mengasumsikan bahwa kita sudah mempunyai suatu cara untuk mencetak list dari belakang. Tapi jika kita menganggap bahwa pemanggilan rekursi ini bekerja dengan baik – leap of faith – barulah kita boleh yakin kepada diri kita sendiri kalau algoritma ini telah bekerja dengan baik dan benar. Yang kita butuhkan adalah base case, lalu sebuah cara untuk membuktikan bahwa untuk seamyp list yang kita gunakan, kita akan bisa kembali lagi ke base case. Pilihan paling wajar untuk base case adalah sebuah list dengan satu elemen tunggal, tapi akan lebih baik kalau kita mau menggunakan list kosong, yang direpresentasikan dengan null.

public static void printBackward (Node list) {
if (list == null) return;
Node head = list;
Node tail = list.next;
printBackward (tail);
System.out.print (head);
}

Baris pertama merupakan base case yang tidak mengembalikan nilai apapun. Dua baris berikutnya memecah list menjadi dua; head dan tail. Sementara dua baris terakhir digunakan untuk mencetak list itu sendiri. Kita memanggil metode ini dengan cara yang sama seperti ketika kita memanggil printList: printBackward (node1);Hasilnya adalah sebuah backward list. Algoritma Quicksort didasarkan pada sebuah ide yang sederhana: Diberikan sebuah array, pilih item manapun dari array. Item yang dipilih tersebut selanjutnya kita sebut pivot. (Dalam praktek kali ini, kita akan gunakan item pertama dari array.) Pindah semua item yang lebih kecil dari pivot ke bagian awal list, dan pindahkan semua item yang lebih besar dari pivot ke akhir dari list. Sekarang, taruh pivot diantara dua kumpulan item tadi. Posisi pivot tersebut sudah tidak akan dipindah-pindah lagi. Kita sebut prosedur tersebut QuicksortStep.
  
contoh implementasi dari rekursif misalnya anagram.
algoritma anagram:
Start:

int size;
int count;
char[] charArray;


doAnagram(int newSize) {
    int limit;
    if (newSize == 1) // if too small, return;
      return;// for each position,
    for (int i = 0; i < newSize; i++) {
      doAnagram(newSize - 1); // anagram remaining
      if (newSize == 2) // if innermost,
        display();
      rotate(newSize); // rotate word
    }
  }

 // rotate left all chars from position to end
 rotate(int newSize) {
    int i;
    int position = size - newSize; // save first letter
    char temp = charArray[position]; //shift others left
    for (i = position + 1; i < size; i++)
      charArray[i - 1] = charArray[i]; //put first on right
    charArray[i - 1] = temp;
  }

Berikut adalah programnnya:
import java.io.*; // for I/O
//////////////// AMY ///////////////////
class anagram
{
 static int size;
 static int count;
 static char[] arrChar = new char[100];
 public static void main(String[] args) throws IOException
 {
  System.out.print("Masukkan Kata : "); // get word
  System.out.flush();
  String input = getString();
  size = input.length(); // find its size
  count = 0;
  for(int j=0; j<size; j++) // put it in array
  arrChar[j] = input.charAt(j);
  doAnagram(size); // anagram it
} // end main()

public static void doAnagram(int newSize)
{
 if(newSize == 1) // if too small,
 return; // go no furt her
 for(int j=0; j<newSize; j++) // for each position,
{
 doAnagram(newSize-1); // anagram remaining
 if(newSize==2) // if innermost,
 displayWord(); // display it
 rotate(newSize); // rotate word
  }
}
// rotate left all chars from position to end

public static void rotate(int newSize)
{
 int j;
 int position = size - newSize;
 char temp = arrChar[position]; // save first letter
 for(j=position+1; j<size; j++) // shift others left
 arrChar[j-1] = arrChar[j];
 arrChar[j-1] = temp; // put first on right
}


public static void displayWord()
{
 if(count < 99)
 System.out.print(" ");
 if(count < 9)
 System.out.print(" ");
 System.out.print(++count + " ");
 for(int j=0; j<size; j++)
 System.out.print( arrChar[j] );
 System.out.print(" ");
 System.out.flush();
 if(count%6 == 0)
 System.out.println("");
}

public static String getString() throws IOException
{
 InputStreamReader isr = new InputStreamReader(System.in);
 BufferedReader br = new BufferedReader(isr);
 String s = br.readLine();
 return s;
 }
}

hasil running program :

TEKNIK ITERATIF & REKURSIF

TEKNIK ITERATIF
Teknik Iteratif merupakan suatu teknik pembuatan algoritma dengan pemanggilan procedure beberapa kali atau hingga suatu kondisi tertentu terpenuhi
Contoh :
Teknik Iteratif pada algoritma untuk menghitung faktorial dari bilangan bulat positif n, adalah sebagai berikut :
Function FAK (n : integer) : integer
FAK=1
For i = 1 TO n
FAK = FAK * i
NEXT i
END FAK
Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka : FAK = 1, kemudian

i                            FAK      
1                        1 * 1 = 1
2                        1 * 2 = 2
3                        2 * 3 = 6
4                        6 * 4 = 24
5                        24 * 5 = 120

Contoh :
BARISAN BILANGAN FIBBONACI → 1, 1, 2, 3, 5, 8, 13, 21, . . .
Teknik Iteratif pada algoritma untuk menentukan suku ke-n dari barisan bilangan Fibbonaci, adalah sebagai berikut :

1. Set x, y, n, i, f : integer
2. x ← 1 ; y ← 1
3. If n 〉 2 then
                       begin
4. for i ← 3 to n do
                      begin
5. F ← x + y
6. x ← y
7. y ← F
                        end
                       else
8. F ← x
9. Write(F)
                        End

Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka :
x=1, y=1, kemudian

i                   F                        x                        y
3           1 + 1 = 2                 1                        2
4           1 + 2 = 3                 2                        3
5           2 + 3 = 5                 3                        5

TEKNIK REKURSIF
Teknik Rekursif merupakan salah satu cara pembuatan algoritma dengan pemanggilan procedure atau function yang sama
Contoh :
Teknik Rekursif pada algoritma untuk menghitung faktorial dari bilangan bulat positif n, adalah sebagai berikut :

Function FAK (n : integer) : integer
1. If n := 0 then FAK := 1
2. Else FAK := n * FAK(n-1)

Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka :

Contoh :
BARISAN BILANGAN FIBBONACI → 1, 1, 2, 3, 5, 8, 13, 21, . . .
Teknik Rekursif pada algoritma untuk menentukan suku ke-n dari barisan bilangan Fibbonaci, adalah sebagai berikut :

Procedure F(n : integer) : integer
1. If n ≤ 2 then F(n) = 1
    else F(n) = F(n-1) + F(n-2)
    Endif
    End
Gambaran jalannya proses algoritma tersebut adalah sebagai berikut :
Misal n = 5, maka :

Perbedaan Antara Teknik Iteratif dan Rekursif : 
            ITERATIF                                                 REKURSIF                          
Tidak ada variabel lokal baru                  Ada variabel lokal baru
Program tidak sederhana                       Program menjadi lebih sederhana