Untuk memahami pengertian rekursi, perhatikan contoh sederhana singkatan berikut: GNU. GNU merupakan singkatan dari GNU Not Unix . Mengapa kepanjangannya masih terdapat singkatan GNU lagi? Karena GNU merupakan singkatan rekursif (bersifat rekursi).
Rekursi adalah subroutine yang memanggil dirinya sendiri, baik secara langsungmaupun tidak langsung. Bentuk rekursi merupakan alternatif iterasi atau perulangan. Ada beberapa masalah yang cocok dipecahkan menggunakan teknik rekursi. Akan tetapi,secara umum teknik rekursi biasanya kurang efisien dibandingkan teknik iterasi karenarekursi memanggil dirinya sendiri sehingga menyebabkan waktu pemrosesan lebih lamadisbanding iterasi biasa. Proses reskursi akan menggunakan memori stack. Semakin lama proses rekursi dikerjakan, maka memori stack akan terus berkurang dan akibatnyamemori stack akan habis. Dalam rekursi sebenarnya terkandung pengertian fungsi, perbedaannya adalah rekursi bisa memanggil dirinya sendiri sedangkan fungsi harus dipanggil lewat pemanggil fungsi. Suatu fungsi tidak hanya bisa memanggil fungsi lain, melainkan juga bisa memanggil dirinya sendiri. Pemanggilan dirinya sendiri bisa berarti proses berulang yangtidak bisa diketahui kapan berakhir sehingga dalam rekursi harus ada syarat-syarat berikut:
1. Ada titik pemberhentian sebagai pengendali rekursi.
2. Adanya langkah induksi yang menuju pada titik pemberhentian.
Berikut ini adalah contoh program yang menerapkan teknik rekursi, program ini digunakan untuk menghitung bilangan factorial.
#include <stdio.h>int
fact();
main(){
int n, m;
printf(“Masukkan angka: ”);
scanf(“%d”, &n);
m = fact(n);
printf(“Nilai faktorial %d adalah %d. \n”, n, m);
}
int fact(x)
int x;
{
Penghenti rekursi
Proses dalam rekursi harus ada titik akhir. Titik akhir disini merupakan batas dari fungsi untuk tidak lagi memanggil dirinya sendiri sekaligus awal dari proses pemberian nilai pada fungsi tersebut. Dari contoh diatas, fungsi faktorial tidak lagi memanggil dirinya sendiri saat n=0.
Penggunaan memori
Komputer mempunyai ruang memori yang terbatas. Setiap kali fungsi memanggil dirinya sendiri, ia memerlukan tambahan sejumlah memori. Jika proses ini terus menerus, pada akhirnya menyebabkan error
Efisiensi
Kita hampir selalu dapat menggantikan rekursi dengan loop. Loop tidak memiliki overhead dari pelewatan argumen, inisialisasi penyimpanan tambahan, dan pengembalian nilai. Kinerja program dapat lebih baik tanpa pemanggilan fungsi yang rekursif.
Tidak ada komentar:
Posting Komentar