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”

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.