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:

[code language=”ruby”]
def fibonacci(n)
first = 0
second = 1
n.times do
third = (first + second)
first = second
second = third
end
second
end
fibonacci(40)
[/code]

Rekursif:

[code language=”ruby”]
def fibonacci(n)
if n < 2
n
else
fibonacci(n — 1) + fibonacci(n — 2)
end
end
fibonacci(40)
[/code]

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

[code lang=text]
iteration:
real 0m0.060s
user 0m0.032s
sys 0m0.004s

recursion:
real 0m14.851s
user 0m14.836s
sys 0m0.004s
[/code]

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:

[code language=”ruby”]
@cache = { }
def fibonacci(n)
if n < 2
n
else
@cache[n] ||= fibonacci(n — 1) + fibonacci(n — 2)
end
end
fibonacci(40)
[/code]

[code lang=text]
optimized recursion
real 0m0.056s
user 0m0.024s
sys 0m0.008s

[/code]

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”

Related Posts

Streaming Festival Disrupto Exploration and Experimentation 2020

Streaming Festival Disrupto Exploration and Experimentation 2020

Resiko Berbahaya menggunakan VPN gratisan di Laptopmu!

Resiko Berbahaya menggunakan VPN gratisan di Laptopmu!

Part II — Understanding about RuleChain

Mengenal dasar RxSwift

No Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

Tags