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
Iterative version
int factorial (int n)
int factorial (int n)
{
{ if (n == 0)
int i, product=1;
return 1;
for (i=n; i>1; --i)
else
product=product * i;
return n * factorial (n-1); }
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); } system("pause"); return (0); }
/* Computes n! for n greater than or equal to zero */ int factorial (int n) { if (n == 0) //base case return 1; else return n * factorial (n-1); //recursive case }
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)))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) =4*6 = 24
Expansion phase
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 = 1 m*n
m + m (n-1), n>1
Contoh 2:
#include <stdio.h>
Perkalian
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: multiply(5,4)
Perkalian = 5 + multiply(5, 3) = 5 + (5 + multiply(5, 2)) = 5 + (5 + (5 + multiply(5, 1)))
= 5 + (5 + (5 + 5)) = 5 + (5 + 10) = 5 + 15 = 20
Expansion phase
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)
