Rekursif vs Iterasi

Jika kita mencoba membuat sebuah program yang membutuhkan looping seperti fibonacci generator, kita sering dihadapkan dengan iterasi maupun rekursif.

Berikut adalah 2 contoh program untuk mengetahui bilangan fibonacci ke-n dengan menggunakan iterasi dan rekursif

Iterasi:

def fibonacci(n)
  first = 0
  second = 1
  n.times do
    third = (first + second)
    first = second
    second = third
  end
  second
end
fibonacci(40)

Rekursif:

def fibonacci(n)
  if n < 2
    n
  else
    fibonacci(n - 1) + fibonacci(n - 2)
  end
end
fibonacci(40)

Bila kita mengeceknya menggunakan time ruby fibonacci.rb maka kita mendapatkan hasil

iteration:
real 0m0.060s
user 0m0.032s
sys 0m0.004s

recursion:
real 0m14.851s
user 0m14.836s
sys 0m0.004s

Di sini rekursif lebih lambat dibandingkan iterasi, karena harus membuat multiple stack sebelum melakukan kalkulasi. Selain itu dari segi kompleksitaspun memiliki kompleksitas berbeda. jika iterasi memiliki kompleksitas n, maka rekursif untuk fibonacci ini memiliki kompleksitas 2 ^ (n – 1) + 2 ^ (n – 2) + 1 = 2 ^ n.

Bandingkan dengan kode rekursif yang dioptimasi dengan cache ini:

@cache = { }
def fibonacci(n)
  if n < 2
    n
  else
    @cache[n] ||= fibonacci(n - 1) + fibonacci(n - 2)
  end
end
fibonacci(40)
optimized recursion
real 0m0.056s
user 0m0.024s
sys 0m0.008s

Performa yang ditunjukkan sedikit lebih baik dibandingkan dengan iterasi. Tentu saja rekursif ini bisa dioptimasi lagi dengan menggunakan tail recursion. Tetapi pada bahasa pemrograman ruby, tail-recursion ini tidak berlaku karena ruby tidak mampu mengoptimasi tail-recursion seperti pada bahasa pemrograman fungsional lainnya.

 

Jadi rekursif memiliki keunggulan:

  • Dapat dioptimasi dengan memoization dan tail recursive
  • Mudah dibaca karena kode relatif pendek (1 terminator dan 1 function call)

Tetapi rekursif juga memiliki kelemahan:

  • Bila dalam bahasa imperative, maka rekursif tidak dioptimasi sehingga terjadi stack overflow jika jumlah recursive call terlalu dalam
  • Memiliki kompleksitas yang lebih besar dibandingkan iterasi biasa

 

“To iterate is human, to recurse divine”

Rekursif vs Iterasi

2 pemikiran pada “Rekursif vs Iterasi

  1. Noobs berkata:

    Basically to improve this performance we can use Dynamic programming. Things that you write is part of dynamic programming and if you using loop you can cache the results too.

    Disukai oleh 1 orang

    1. Yes, you’re right about dynamic programming. I just want to show that recursive can be effective using memoization (and tail recursive which I will show in the next post using elixir). Thanks.

      Suka

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s