Fungsi Rekursif

•Definisi fungsi rekursif.

•Contoh 1 : Faktorial

•Contoh 2 : Perkalian

•Contoh 3 : Fibonacci

Contoh 4 : Tower of Hanoi

--------------------------------------------------------------------------

 

•Fungsi biasa dipanggil oleh fungsi lain. Sedangkan fungsi rekursif dipanggil oleh dirinya sendiri.

 •Setara dengan proses looping/ iterasi à faktorial, perkalian

•Kadang rekursif lebih baik dari iterasi à tower of hanoi

•Terkadang sebaliknya à fibonacci

•Komponen :

–Way out à if – else + return() Recursive call dengan value baru

#include<stdio.h>

int main(void)

{

  printf("Never ends\n");

  main();

  return 0;

}

FAKTORIAL

ALGORITMA

n! = 1 if n == 0

n! = n * ( n – 1 )! if n > 0

4! = 4 x 3!

             3! = 3 x 2!

                          2! = 2 x 1!

                                       1! = 1 x 0!

                                                    0! = 1

SOURCE CODE

int factorial ( int n )

{

   int x, y;

   if ( n == 0 )  return ( 1 );

   x = n – 1;

   y = factorial ( x );

   return ( n * y );

}

 

 

PERKALIAN

ALGORITMA

a * b = a if b == 1

a * b = a * ( b – 1 ) + a if b > 1

6 x 3 = ( 6 x 2 ) + 6

         = ( 6 x 1 ) + 6 + 6

         = 6 + 6 + 6

         = 18

SOURCE CODE

int mult ( int a, int b )

{

   int c, d, sum;

   if ( b == 1 ) return ( a );

   c = b – 1;

   d = mult ( a, c );

   sum = d + a;

   return ( sum );

}