Tugas Rekursif
Nama : Indah Zalika
Nim : 09031181320020
Kelas : SI.2B
Rekursif adalah suatu proses yang bisa memanggil dirinya sendiri. Dalam Rekursif sebenarnya terkandung pengertian prosedurdan fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil lewat pemanggil prosedur dan fungsi. Di Dalam C++, rekursif mengambil bentuk suatu fungsi yang memanggil diri sendiri. Suatu cara untuk berpikir tentang fungsi-fungsi rekursif dengan menggambarkan sebagai suatu proses yang sedang melaksanakan salah satu perintah untuk mengulangi proses. Hal ini sangat serupa dengan suatu pengulangan karena mengulangi kode yang sama, dan dalam beberapa hal yang serupa dengan rekursif. Selain itu, rekursif membuat pengulangan lebih mudah untuk menyatakan gagasan-gagasan di mana hasil dari panggilan yang berulang digunakan untuk melengkapi task (instruksi).
Suatu algoritma recursif adalah satu algoritma yang memanggil diri sendiri dengan nilai masukan lebih sederhana, dan memperoleh hasil dengan masukan yang sederhana dengan menerapkan operasi yang sederhana untuk mengembalikan nilai masukan yang lebih sederhana. Lebih umum lagi jika suatu masalah dapat dipecahkan menggunakan solusi-solusi dengan versi-versi yang lebih kecil pada masalah yang sama, dan semakin kecil versi-versi akan mengurangi kasus-kasus dan dengan mudah dapat dipecahkan, lalu seseorang dapat menggunakan suatu algoritma yang berulang untuk memecahkan masalah itu. sesuatu secara berulang didefinisikan sebagai fungsi yang diperoleh oleh suatu algoritma yang berulang. Jika seperangkat atau suatu fungsi digambarkan secara berulang, lalu suatu algoritma yang berulang untuk menghitung para anggota atau nilai-nilai yang mencerminkan definisi. Langkah awal dari algoritma rekursif berpasangan dengan ketentuan dasar dari definisi rekursif dan mereka mengidentifikasi unsur-unsur dasar. Kemudian mengikuti langkah demi langkah sesuai dengan ketentuan yang induktif, yang mengurangi perhitungan untuk satu unsur dibangkitkan tersebut dari unsur-unsur yang dibangkitkan terdahulu. Umumnya, program komputer yang berulang memerlukan lebih banyak memori dan perhitungan dibandingkan dengan algoritma-algoritma berulang-ulang, tetapi mereka bersifat lebih sederhana untuk banyak kasus terhadap suatu cara berpikir yang alami tentang pemecahan masalah.
Fungsi rekursif adalah suatu fungsi yang memanggil dirinya sendiri. Pada beberapa persoalan, fungsi rekursif sangat berguna karena mempermudah solusi. Namun demikian, fungsi rekursif juga memiliki kelemahan, yakni memungkinkan terjadinya overflow padastack, yang berarti stack tidak lagi mampu menangani permintaan pemanggilan fungsi karena kehabisan memori stack adalah area memori yang dipakai untuk variable lokal untuk mengalokasikan memori ketika suatu fungsi dipanggil. Oleh karena itu, jika bisa diselesaikan dengan metode iteratif, gunakanlah metode iteratif.
Bentuk umum fungsi rekursif:
Nama_fungsi(parameter_list)
{
...
Nama_fungsi(parameter_list);
...
}
Dengan metode rekursif program menjadi lebih singkat dan untuk beberapa kasus program lebih mudah menggunakan fungsi yang rekursif. Fungsi rekursif memakan memori yang lebih besar, karena setiap kali bagian dirinya dipanggil, membutuhkan sejumlah ruang memori tambahan. Ketika efisiensi dan kecepatan dikorbankan fungsi rekursif seringkali tidak bisa “berhenti” sehingga memori akan habis dan komputer menjadi tidak aktif (hang). Dengan demikian, jika memang bisa diselesaikan dengan iteratif, gunakanlah iteratif. Contoh sederhana rekursif
void recurse()
{
recurse(); /* Pemanggilan Fungsi dirinya sendiri */
}
int main()
{
recurse(); /* Set pengulangan */
return 0;
}
Komputer menjaga pemanggilan fungsi pada suatu tumpukan dan ketika terlalu banyak panggilan tanpa akhir, program itu akan crash. Mengapa tidak menulis suatu program untuk melihat berapa kali fungsi itu dipanggil sebelum program berakhir? Dengan demikian diperlukan perintah untuk melakukan hitungan terhadap panggilan fungsi, menggunakan program sederhana yang akan menunjukkan seringnya fungsi rekursif kembali dipanggil dengan inisialisasi setiap panggilan fungsi dihitung sebagai satu variabel yang lebih besar dari yang sebelumnya dengan melewatkan hitungan + 1. Mengingat bahwa panggilan fungsi tidak dimulai dari diri sendiri; karena itu, ratusan panggilan fungsi yang lain masing-masing menjadi tidak selesai.
Contoh penggunaan hitungan pada panggilan fungsi rekursif
#include <stdio.h>
/* Setiap pemanggilan mendapat hitungan kopian */
void recurse ( int count )
{
printf( "%d\n", count );
recurse ( count + 1 );
}
int main()
{
/* pemanggilan fungsi pertama, jadi dimulai dari satu */
recurse ( 1 );
return 0;
}
Cara terbaik untuk berpikir tentang rekursif adalah bahwa setiap panggilan fungsi adalah satu proses yang dilaksanakan oleh komputer. Jika kita berpikir tentang suatu program yang dilaksanakan oleh suatu kelompok orang yang dapat memberikan informasi tentang status dari suatu task dan instruksi pada hasil task, dimana setiap panggilan fungsi yang berulang merupakan permintaan yang berikutnya untuk mengikuti set instruksi yang sama di beberapa bagian dari task selagi orang pertama menunggu hasil.
Pada saat tertentu, kita akan kehabisan orang-orang untuk menyelesaikan instruksi, sama seperti fungsi-fungsi rekursif yang kehabisan ruang di tumpukan. Dimana perlu suatu cara untuk menghindari hal ini! Untuk menghentikan satu rangkaian panggilan rekursif, suatu fungsi rekursif akan memiliki suatu kondisi yang mengendalikan kapan fungsi itu akan berakhir memanggil diri sendiri. Kondisi di mana fungsi itu tidak akan memanggil diri sendiri adalah kasus dasar dari fungsi. Pada dasarnya, hal itu biasanya adalah satu jika statemen memeriksa beberapa variabel untuk suatu kondisi (yang kurang dari nol, atau lebih besar) dan jika kondisi itu adalah benar, maka tidak akan diizinkan fungsi untuk memanggil diri sendiri lagi.
Contoh sederhana fungsi rekursif yang dibatasi oleh kondisi tertentu
void count_to_ten ( int count )
{
if ( count < 10 )
{
count_to_ten( count + 1 );
}
}
Tujuan program ini menghentikan hitungan ketika hitungan sudah tidak lagi kurang dari sepuluh. Ini adalah suatu hal yang baik karena ini berarti bahwa jika kita mempunyai satu masukan lebih besar dari sepuluh, kita akan berhenti dengan segera. Jika kita memilih untuk berhenti ketika hitungan sama dengan sepuluh, lalu jika fungsi itu memanggil masukan ke-11, hal itu akan sebagai isyarat ke memori sebelum berhenti.
Bagaimana Satu fungsi yang bisa mencetak angka-angka 123456789987654321 menggunakan pengulangan untuk menulis suatu fungsi untuk lakukan hal ini? Solusi sederhana adalah dengan menjaga kenaikan suatu variabel yang dilewatkan, kemudian menjadi variabel keluaran yang berikutnya: yakni satu kali sebelum fungsi rekursif, dan ketika setelah fungsi rekursif.
void printnum ( int begin )
{
printf( "%d", begin );
if ( begin < 9 )
{
printnum ( begin + 1 );
}
printf( "%d", begin );
}
Fungsi ini bekerja karena fungsi akan mengalami dan mencetak angka-angka mulai 1 sampai 9, kemudian setiap fungsi printnum berakhir akan dilanjutkan pencetakan nilai dari mulai 9 sampai 1.
Contoh berikut yakni membuat kombinasi huruf a, b, c, d dengan sebuah fungsi rekursif
void f(int x, int num)
{
int i;
char a[4] = {'a', 'b', 'c', 'd'};
char temp[16];
if(num == 0)
return;
else for(i = 0; i < 4; i++)
{
temp[x] = a[i];
f(x + 1, num - 1);
temp[x + 1] = '\0';
printf("%s\n", temp);
}
}
Menara Hanoi
Menara Hanoi merupakan persoalan untuk memindahkan tumpukan piring dari satu tonggak ke tonggak lain dengan bantuan sebuah tonggak perantara. Penyelesaian secara rekursif untuk persoalan ini dengan n buah piring menggunakan algoritma:
- Pindahkan piring n-1 teratas pada tonggak A ke tonggak B dengan menggunakan tonggak C sebagai perantara
- Pindahkan 1 piring tersisa pada tonggak A ke tonggak C
- Pindahkan n-1 piring teratas tonggak B ke tonggak C, dengan menggunakan tonggak A sebagai perantara
Dengan algoritma tersebut maka dapat dibuat suatu fungsi rekursif sebagai berikut:
Void tonggak(int n, char a, char b, char c)
{
if(n == 1)
Printf(“Pindahkan piring %c ke %c \n”, a, c);
Else
{
tonggak(n-1, a, c, b);
tonggak(1, a, b, c);
tonggak(n-1, b, a, c);
}
}
Contoh Algoritma Rekursif
#include <cstdlib>
#include <iostream>
using namespace std;
long faktorial(int n){
if((n==0)||(n==1)){
return 1;
}
else {
return n*faktorial(n-1);
}
}
int main(int argc, char *argv[])
{
int n;
cout<<"Masukkan angka yang akan difaktorialkan:";
cin>>n;
cout<<"Hasil:"<<faktorial(n);
system("PAUSE");
return EXIT_SUCCESS;
}
Refrensi :
http://mahfuzm.blogspot.com/2011/04/program-rekursif-c.html
http://errickrachman.blogspot.com/2010/11/recursive-rekursif.html
