Last active
March 12, 2022 09:04
-
-
Save gunhansancar/d01e572e297444217a3ae5ae6a3c9a4c to your computer and use it in GitHub Desktop.
Recursive vs Iterative with #Kotlin and #Fibonacci sequence
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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") | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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