REKURSI (HOURS 11)

Rekursi adalah teknik pemrograman dimana sebuah fungsi atau anggota yang dapat memanggil dirinya sendiri untuk menyelesaikan sebuah permasalahan.
 

Contoh rekursi dalam penggunaan penambahan segitiga phytagoras dimana didapatkan hasil berupa deret 1, 3, 6, 10, 15, 21, …dst

Digunakan loop atau perulangan untuk mendapatkan nilai jumlah dari setiap segitiga

int triangle(int n) {

int total = 0;

while(n > 0) // until n is 1

{

total = total + n; // add n (column height) to total

--n; // decrement column height

}

return total;

}

Dengan menggunakan rekursi rumusnya dapat disederhanakan menjadi

int triangle(int n) {

if(n==1)

return 1;

else

return( n + triangle(n-1) );

}

Secara matematis dapat dihitung nilai dari hasil return fungsi triangle yaitu dengan rumus (n²+n)/2

Cara kerja fungsi triangle

Listing

int triangle(int n){

cout << "Entering: n=" << n << endl;

if(n==1){

cout << "Returning 1" << endl;

return 1;

}

Else {

int temp = n + triangle(n-1);

cout << "Returning " << temp << endl;

return temp;

}

}

Output

Enter a number: 5

Entering: n=5

Entering: n=4

Entering: n=3

Entering: n=2

Entering: n=1

Returning 1

Returning 3

Returning 6

Returning 10

Returning 15

Triangle = 15

Analisa

Terlihat jelas urutan saat fungsi triangle memproses input dan memulai rekursi dengan memanggil dirinya sendiri hingga nilai yang dikembalikan(return) terus berubah hingga didapat nilai akhir yaitu nilai yang sebenarnya

Karakteristik dari fungsi rekursif

- memanggil dirinya sendiri

- ketika memanggil dirinya sendiri maka akan menyelesaikan masalah yang lebih kecil/sederhana terlebih dahulu

- ada beberapa versi dari rekursi dimana proses yang dilakukan terlalu mudah sehingga tidak perlu melakukan pemanggilan fungsi diri sendiri dan langsung memberikan nilai return

Rekursi dipakai bukan karena efisien
tapi karena kemudahan dalam listing serta sederhana. Rekursi memakan banyak memori dan dapat mengakibatkan overflow jika permasalahan yang diberikan terlalu banyak

Pembuatan program anagram/kombinasi dengan rekursi

Konsepnya adalah menyimpan 1 karakter dan menukar-nukar posisi karakter yang lain sehingga didapat kombinasi yang berbeda-beda

Listing anagram

//anagram.cpp

//creates anagrams

#include <iostream>

#include <string>

using namespace std;

////////////////////////////////////////////////////////////////

class word {

private:

int size; //length of input word

int count; //numbers in display

string workStr; //workspace

void rotate(int); //rotate part of workStr

void displayWord(); //display workStr

public:

word(string); //constructor

void anagram(int); //anagram ourselves

};

//--------------------------------------------------------------

//constructor

word::word(string inpStr) : workStr(inpStr), count(0) { //initialize workStr

size = inpStr.length(); //number of characters

}

//--------------------------------------------------------------

void word::anagram(int newSize) {

if(newSize == 1) //if too small,

return; //go no further

for(int j=0; j<newSize; j++) //for each position,

{

anagram(newSize-1); //anagram remaining

if(newSize==2) //if innermost,

displayWord(); // display it

rotate(newSize); //rotate word

}

}

//--------------------------------------------------------------

//rotate left all chars from position to end

void word::rotate(int newSize) {

int j;

int position = size - newSize;

char temp = workStr[position]; //save first letter

for(j=position+1; j<size; j++) //shift others left

workStr[j-1] = workStr[j];

workStr[j-1] = temp; //put first on right

}

//--------------------------------------------------------------

void word::displayWord() {

if(count < 99) //spaces before onecout

<< " "; //or two-digit numbers

if(count < 9)

cout << " ";

cout << ++count << " "; //number

cout << workStr << " ";

if(count%6 == 0)

cout << endl;

}

////////////////////////////////////////////////////////////////

int main() {

string input;

int length;

cout << "Enter a word: "; //get word

cin >> input;

length = input.length(); //get its length

word theWord(input); //make a word object

theWord.anagram(length); //anagram it

return 0;

} //end main()

Output

Enter a word: cats

1 cats     2 cast     3 ctsa     4 ctas     5 csat     6 csta

7 atsc     8 atcs     9 asct     10 astc     11 acts     12 acst

13 tsca     14 tsac     15 tcas     16 tcsa     17 tasc     18 tacs

19 scat     20 scta     21 satc     22 sact     23 stca     24 stac

Pembuatan fungsi rekursif

1. Menentukan nilai henti(terminate)
2. Melakukan penyederhanaan pada langkah rekursi

Contoh

Program faktorial dengan fungsi fak(n)

1. Nilai henti 1!=1 fak(1)=1
2. Penyederhanaan n! = n*(n-1)!

Program fibonacci dengan fungsi fib(n)

1. Nilai henti fib(1) = 1
   
   
       fib(2) = 1
2. Penyederhanaan fib(n) = fib(n-1) + fib(n-2)

Program pangkat aⁿ dengan fungsi pangkat(a,n)

1. Nilai henti pangkat(a,n) n=0;a=1
2. Penyederhanaan return(a*pangkat(a,n-1))

Program tes 1

Int tes(int n) {

If (n>0) {

Cout <<n<<" ";

Tes(n-1);

}

}

Int main(){

Tes(5);

Cout<<endl;

Return 0;

}

Output 54321

Program tes 2

Int tes(int n) {

If (n>0) {

Tes(n-1);

Cout <<n<<" ";

}

}

Int main(){

Tes(5)

Cout<<endl;

Return 0;

}

Output 12345

sumber : kuliah logika dan pemrograman sistem II