Pada kasus seperti apa fungsi rekursif digunakan apa keuntungannya?

Pertemuan 4 Fungsi Rekursif

Apa itu fungsi rekursif? Sebuah fungsi dapat memanggil fungsi lain Sebuah fungsi dapat memanggil dirinya sendiri. Fungsi seperti demikian disebut fungsi rekursif Sebuah fungsi f juga disebut rekursif jika memanggil fungsi lain g dan di dalam g terdapat pemanggilan terhadap f Meski kurang efisien dibandingkan dengan fungsi iteratif yang memakai perulangan, pada beberapa kasus fungsi rekursif menyediakan solusi yang lebih natural dan sederhana

Apa itu fungsi rekursif? Permasalahan yang diselesaikan melalui fungsi rekursif memiliki beberapa karakteristik: Kasus sederhana dari permasalahan tersebut memiliki jawaban langsung yang disebut base cases. Contoh 0! = 1. Kasus yang lebih kompleks dapat didefinisikan secara sama namun dalam ukuran yang lebih kecil yang disebut recursive cases. Contoh: n! = n * (n-1)! Dengan menerapkan karakteristik 2 secara berulang kasus rekursif akan mendekati dan sampai pada base case. Contoh: n! (n-1)! (n-2)!... 1!, 0!.

Apa itu fungsi rekursif? Strategi penyelesaian masalah pada kasus rekusif disebut decrease-and-conquer. Idenya ialah mengurangi ukuran permasalahan sampai menjadi kasus sederhana (dalam kasus ini decrease-andconquer)yang memiliki penyelesaian jelas.

Format fungsi rekursif Pada umumnya fungsi rekursif memiliki bentuk sebagai berikut if this is a simple case solve it else redefine the problem using recursion

Format fungsi rekursif Cabang if merupakan base case, sedangkan bagian else-nya merupakan recursive case Bagian recursive case menyediakan pengulangan yang dibutuhkan yang menyederhanakan permasalahan dan base case menyediakan penghentian Agar rekursi dapat berhenti recursive cases harus mendekati base case di setiap pemanggilan fungsi rekursif

Contoh 1 : Recursive Factorial Contoh berikut menunjukkan fungsi iteratif dan rekursif dari fungsi faktorial Recursive version int factorial (int n) { if (n == 0) return 1; else return n * factorial (n-1); Iterative version int factorial (int n) { int i, product=1; for (i=n; i>1; --i) product=product * i; return product; Recursive Call

Contoh 1 : Recursive Factorial /* Computes the factorial of a number */ #include <stdio.h> int factorial(int n); /* shows how to call a user-define function */ int main(void) { int num, fact; printf("enter an integer between 0 and 7> "); scanf("%d", &num); if (num < 0) { printf("factorial not defined for negative numbers\n"); else if (num <= 7) { fact = factorial(num); printf("the factorial of %d is %d\n", num, fact); else { printf("number out of range: %d\n", num); /* Computes n! for n greater than or equal to zero */ int factorial (int n) { if (n == 0) //base case else return 1; return n * factorial (n-1); //recursive case system("pause"); return (0);

Trace Eksekusi fungsi rekursif berlangsung dalam dua tahap Expansion di mana pada setiap pemanggilan fungsi rekursif makin mendekati base case Substitution di mana solusi dihitung secara terbalik mulai dari base case factorial(4) = 4 * factorial (3) = 4 * (3 * factorial (2)) = 4 * (3 * (2 * factorial (1))) = 4 * (3 * (2 * (1 * factorial (0)))) Expansion phase = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24 Substitution phase

Contoh 2: Perkalian Misalnya kita ingin menulis fungsi rekursif untuk mengalikan integer m dan integer n menggunakan penjumlahan Salah satu cara menyelesaikan ini melalui rekursif adalah dengan mengidentifikasi base case dan recursive case. Base case adalah jika n bernilai 1, jawabannya m. Recursive case adalah: m*n = m + m (n-1). m*n m, n = 1 m + m (n-1), n>1

Contoh 2: Perkalian #include <stdio.h> int multiply(int m, int n); int main(void) { int num1, num2; printf("enter two integer numbers to multiply: "); scanf("%d%d", &num1, &num2); printf("%d x %d = %d\n", num1, num2, multiply(num1, num2)); system("pause"); return 0; int multiply(int m, int n) { if (n == 1) return m; /* simple case */ else return m + multiply(m, n - 1); /* recursive step */

Contoh 2: Perkalian multiply(5,4) = 5 + multiply(5, 3) = 5 + (5 + multiply(5, 2)) = 5 + (5 + (5 + multiply(5, 1))) Expansion phase = 5 + (5 + (5 + 5)) = 5 + (5 + 10) = 5 + 15 = 20 Substitution phase

Contoh 4: Bilangan Fibonacci Misalnya kita akan membuat fungsi untuk menghitung bilangan fibonacci ke n Bilangan Fibonacci dimulai dari 0 dan 1 serta memiliki sifat setiap bilangan ke n > 2 merupakan penjumlahan dua bilangan sebelumnya 0, 1, 1,2,3,5,8,13,21,34 Sequence bilangan fibonacci adalah n, n = 0, 1 fib(n) fib(n-1) + fib(n-2) n>1

Contoh 4: Fibonacci Function #include <stdio.h> int fib(int n); int main(void) { int n; printf("enter an integer n to find the nth fibonacci term: "); scanf("%d", &n); printf("fibonacci(%d) = %d\n", n, fib(n)); system("pause"); return 0; int fib(int n) { if (n == 0 n== 1) return n; /* simple case */ else return fib(n-1) + fib(n-2); /* recursive step */

Tracing menggunakan pohon rekursif Cara lain untuk melakukan trace pada fungsi rekursif adalah dengan menggambar pohon rekursif. Cara ini lebih sesuai jika pada recursive case terdapat lebih dari 1 pemanggilan fungsi rekursif Rrecursive tree of the Fibonacci function

Part Of Trace n=7, fib(7)=fib(6) + fib(5) fib (6)= fib(5) + fib(4)

ALGORITMA REKURSIF DAN ITERATIF TERKAIT DEFINISI, FUNGSI DAN CONTOHNYA

A. ALGORITMA REKURSIF

1. Pengertian Algoritma Rekursif

Rekursif dapat diartikan bahwa suatu proses yang  bisa memanggil dirinya sendiri. sedikit menyimpang dari pengertian ada sedikit pendapat tentang Rekursif salah satunya adalah Menurut definisi dalam Microsoft Bookshelf, Rekursif adalah kemampuan suatu rutin untuk memanggil dirinya sendiri. Dalam Rekursif sebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil lewat pemanggil prosedur dan fungsi. Rekursif merupakan teknik pemrograman yang penting dan beberapa bahasa pemrograman mendukung keberadaan proses rekursif ini. Dalam prosedur dan fungsi, pemanggilan ke dirinya sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir.

Algoritma rekursif

- Teknik Rekursif merupakan salah satu cara pembuatan algoritma dengan pemanggilan procedure atau function yang sama

- Ada variabel lokal baru

- Program menjadi lebih sederhana

- Menggunakan perulangan if else

Kelebihan perulangan rekursif: • Sangat mudah untuk melakukan perulangan dengan batasan yang luas dalam artian melakukan perulangan dalam skala yang besar.

• Dapat melakukan perulangan dengan batasan fungsi.

2.  Fungsi Algoritma Rekursif

Fungsi tersebut memanggil dirinya sendiri secara rekursif terhadap versi input yang lebih kecil (n-1) dan mengkalikan hasil dari pemanggilan rekursif dengan n, sampai pada kasus dasar, sama analoginya dengan definisi matematika dari faktorial.

Rekursi dalam pemrograman komputer dicontohkan saat sebuah fungsi didefinisikan dalam bentuk sederhana, bahkan versi terkecil dari dirinya. Solusi dari permasalahan kemudian dirancang dengan menggabungkan solusi-solusi yang didapat dari versi sederhana dari permasalahan. Salah satu contoh aplikasi rekursi yaitu dalam parsing untuk bahasa pemrograman. Keuntungan utama dari rekursi adalah suatu himpunan tak-terbatas dari kalimat yang memungkinkan, perancangan atau data lainnya dapat didefinisikan, diurai atau dihasilkan dengan suatu program komputer yang terbatas.

Relasi perulangan adalah persamaan-persamaan untuk menentukan satu atau lebih urutan-urutan secara rekursif. Beberapa relasi perulangan tertentu dapat “diselesaikan” untuk mendapatkan definisi bukan-rekursif.

Penggunaan rekursi dalam suatu algoritma memiliki kelebihan dan kekurangan. Kelebihan utamanya adalah biasanya kesederhanaan. Kekurangan utamanya adalah terkadang algoritma tersebut membutuhkan memori yang sangat banyak jika kedalaman rekursi sangat besar.

Contoh paling sederhana dari proses rekursi adalah menghitung nilai faktorial dari bilangan bulat. Nilai faktorial, secara rekursif dapat ditulis sebagai :

0! = 1

N! = N x (N-1)!, Untuk N > 0

yang secara notasi pemrograman bisa ditulis sebagai:

FAKTORIAL (0) = 1 1)

FAKTORIAL (N) = N * FAKTORIAL (N-1)
#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; }  2)

Persamaan 2) di atas merupakan contoh hubungan rekurens (recurrence relation), yang berarti bahwa nilai suatu fungsi dengan argumen tertentu bisa dihitung dari fungsi yang sama dengan argumen yang lebih kecil. Persamaan 1) yang tidak bersifat rekursif, disebut nilai awal. Setiap fungsi rekursi paling sedikit mempuyai 1 (satu) nilai awal; jika tidak, fungsi tersebut tidak bisa dihitung secara eksplisit.

B. ALGORITMA ITERATIF

         Perulangan iteratif merupakan perulangan yang melakukan proses perulangan terhadap sekelompok instruksi di mana perulangan tersebut akan berhenti jika batasan syarat sudah tidak terpenuhi.

Algoritma iteratif

- Teknik Iteratif merupakan suatu teknik pembuatan algoritma dengan pemanggilan procedure    beberapa kali atau hingga suatu kondisi tertentu terpenuhi.

- Tidak ada variabel lokal baru

- Program tidak sederhana

- Menggunakan perulangan for dan while

Perulangan iteratif merupakan perulangan yang melakukan proses perulangan terhadap sekelompok intruksi. Perulangan dilakukan dalam batasan syarat tertentu. Ketika syarat tersebut tidak terpenuhi lagi maka perulangan aka terhenti.  

Berikut beberapa fungsi dari Algoritma Iteratif

a. Fungsi rekursif dalam pemrograman merupakan fungsi yang memanggil dirinya sendiri. Fungsi rekursif sering saya bayangkan seperti perulangan. Karena tingkah lakunya yang mengulang-ulang setiap pemanggilan dirinya.

b. Fungi Iteratif merupakan perulangan yang melakukan proses perulangan terhadap sekelompok intruksi. Perulangan dilakukan dalam batasan syarat tertentu. Ketika syarat tersebut tidak terpenuhi lagi maka perulangan akan terhenti.

3. Contoh Algoritma Iteratif

/*Fungsi pencarian nilai maximum*/

Function maximum(A,n){

 m <- A[1]

 i <- 2

 While (i <= n) do

  if (A[i] > m) then

    m <- A[i]

  i <- i+1

 endwhile

 return m

}