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 secondendfibonacci(40)[/code]
Rekursif:
[code language=”ruby”]def fibonacci(n) if n < 2 n else fibonacci(n — 1) + fibonacci(n — 2) endendfibonacci(40)[/code]
Bila kita mengeceknya menggunakan time ruby fibonacci.rb maka kita mendapatkan hasil
[code lang=text]iteration:real 0m0.060suser 0m0.032ssys 0m0.004s
recursion:real 0m14.851suser 0m14.836ssys 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) endendfibonacci(40)[/code]
[code lang=text]optimized recursionreal 0m0.056suser 0m0.024ssys 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”
