Fungsi rekursif C++

 Fungsi rekursif C++

pengertian fungsi rekursif

Fungsi rekursif adalah function yang memanggil dirinya sendiri secara
langsung maupun tidak langsung melalui function yang lain. Setiap function rekursif
mengandung 2 hal :
a. kasus yang paling sederhana atau kasus basis. Di dalamnya akan
mengembalikan suatu nilai
b. langkah rekursi (recursive call), di mana masalah yang kompleks dipecah
menjadi masalah yang lebih sederhana. Langkah rekursif ini harus
mengarah ke kasus basis.
Sebagai contoh adalah program untuk mencari nilai dari n! dengan n bilangan integer
non negatif. n! didefinisikan sebagai : (iteratif)
n! = n*(n-1)*(n-2)* ... * 1
dengan 1!=1 dan 0!=1. Persoalan ini dapat diselesaikan dengan cara iteratif
menggunakan pernyataan for. Misalkan akan dicari n!

faktorial = 1;
for (int i=1; i<= n; i++)
faktorial = faktorial * i;
Definisi faktorial bisa ditulis dengan relasi : (rekursif)
n! = n * (n-1)!
yang ditulis sebagai
faktorial := n * faktorial(n-1);
Perhatikan evaluasi rekursif dari 4! di bawah ini.

 

#include <iostream.h> int Factorial(int n) { int i, hasil = 1; for (i=1; i<=n; i++) hasil = hasil * i; return hasil; } void main(void) { cout << "5! = " << Factorial(5) << endl; }

Pada kasus perulangan iteratif di atas, kita dapat menggunakan pernyataan
perulangan while atau do .. while sebagai ganti for (5). Nilai kumulatif perkalian
dimulai dari 1 (4) dan pernyataan kumulatif nilai perkalian menggunakan (6) [
Silahkan merujuk diktat Algoritma dan Pemrograman ]. Nilai hasil dikembalikan
sebagai hasil dari fungsi Factorial (7).
Untuk kasus perulangan rekursif, nilai awal dapat kita pandang sebagai kasus
basis yang nantinya akan mengembalikan suatu nilai (4). Sementara sifat
pengulangannya menggunakan pemanggilan dirinya sendiri (5). Tentu saja rumus yang
digunakan disesuaikan dengan kasus yang dihadapi.

#include <iostream.h> int Factorial(int n) { if (n <= 1) return 1; // kasus basis else return n * Factorial(n - 1); // pemanggilan rekursif } void main(void) { cout << "5! = " << Factorial(5) << endl; }

Output dari program di atas untuk n = 5 adalah
Faktorial 5 = 1201. Fungsi Rekursif dua parameter : Perkalian Dua Buah IntegerDefinisi iteratif untuk kasus perkalian dua buah integer adalah sebagai berikut :
Definisi : (iteratif)
a x b = a + a + ... + a (b kali), untuk b > 0 (-a) + (-a) + ... + (-a) (b kali), untuk b < 0Dalam definisi di atas dapat dilihat bahwa perulangan selalu dipertahankan bernilai
positif, terutama untuk kasus b yang negatif, yaitu dengan cara mengalihkan nilai
negatif ke a. Implementasi definisi tersebut menggunakan fungsi sebagai berikut :

#include <iostream.h> #include <math.h> int kali_iteratif(int a,int b) { int i, hasil = 0; // nilai awal for (i=1; i<=abs(b); i++) hasil = hasil+a; if (b<0) return -hasil; else return hasil; } void main(void) { cout << "3x(-5) = " << kali_iteratif(3,-5) << endl; }

Fungsi absolut (abs) digunakan untuk perulangan yang selalu positif (7).
Fungsi abs prototipe fungsinya berada pada math.h (2). Sementara bila b bernilai
negatif, kita bisa menggunakan nilai negatif dari perhitungan semula untuk b positif
(9). Dalam implementasi menggunakan fungsi rekursif, nilai awal pada kasus iteratif
digunakan sebagai kasus basis (penyetop). Sementara dua kasus yang ada pada
definisi iteratif digunakan dan dimodifikasi untuk kasus rekursif. Definisi rekursif
dari kasus perkalian dua integer adalah sebagai berikut :
Definisi : (rekursif)
a x b = 0, untuk b = 0 a + (a x (b-1)), untuk b > 0 -a + (a x (b+1)), untuk b < 0Implementasi dari definisi rekursif di atas adalah sebagai berikut :

#include <iostream.h>

int kali_rekursif(int a,int b) { if (b==0) return 0; // kasus basis else if (b>0) return a + kali_rekursif(a,b-1); // pemanggilan rekursif else return (-a) + kali_rekursif(a,b+1); // pemanggilan rekursif } void main(void) { cout << "3x(-5) = " << kali_rekursif(3,-5) << endl; }

Pada kasus rekursif yang pertama, nilai b positif. Untuk mengarah pada kasus
basis (b = 0) maka nilai b selalu dikurangi dengan 1 (8). Sementara untuk kasus
rekursif yang kedua (b < 0), untuk mengarah pada kasus basis (b = 0) nilai b
ditambah dengan 1 (10).