Skip to content

Instantly share code, notes, and snippets.

@gunhansancar
Last active March 12, 2022 09:04
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gunhansancar/d01e572e297444217a3ae5ae6a3c9a4c to your computer and use it in GitHub Desktop.
Save gunhansancar/d01e572e297444217a3ae5ae6a3c9a4c to your computer and use it in GitHub Desktop.
Recursive vs Iterative with #Kotlin and #Fibonacci sequence
import java.time.Duration
import java.time.Instant
object Fibonacci {
fun recursive(n: Long): Long = if (n < 2) n else recursive(n - 1) + recursive(n - 2)
tailrec fun recursiveTail(n: Long, a: Long, b: Long): Long
= if (n < 1) a else recursiveTail(n - 1, b, a + b)
fun iterative(n: Long): Long {
if (n < 2) return n
var minusOne: Long = 1
var minusTwo: Long = 0
var result = minusOne
for (i in 2..n) {
result = minusOne + minusTwo
minusTwo = minusOne
minusOne = result
}
return result
}
}
fun main(args: Array<String>) {
println("Fibonacci recursive vs iterative")
measure(Fibonacci::recursive, 50)
measure(Fibonacci::recursiveTail, 5000, 0, 1)
measure(Fibonacci::iterative, 5000)
}
fun measure(method: (n: Long, a: Long, b: Long) -> Long, n: Long, a: Long, b: Long) {
val start = Instant.now()
val result = method(n, a, b)
val finish = Instant.now()
val timeElapsed = Duration.between(start, finish).toMillis()
print("\nFibonacci($n) = $result Time elapsed: $timeElapsed ms")
}
fun measure(method: (n: Long) -> Long, n: Long) {
val start = Instant.now()
val result = method(n)
val finish = Instant.now()
val timeElapsed = Duration.between(start, finish).toMillis()
print("\nFibonacci($n) = $result Time elapsed: $timeElapsed ms")
}
@gunhansancar
Copy link
Author

gunhansancar commented Mar 4, 2019

Output:
Fibonacci recursive vs iterative

Fibonacci(50) = 12586269025 Time elapsed: 46094 ms
Fibonacci(5000) = 535601498209671957 Time elapsed: 1 ms
Fibonacci(5000) = 535601498209671957 Time elapsed: 0 ms

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment