1. Overview
The Fibonacci series is a series of numbers where each number is the sum of the two preceding ones. In Kotlin, we can use various techniques to generate these numbers. In this tutorial, we’ll see a few of the techniques.
2. Generate Fibonacci Series With Recursion
Above all, the Fibonacci series formula is defined by F(0) = 0, F(1) = 1, …, F(n) = F(n-1) + F(n-2). So the first eight numbers are: 1,1,2,3,5,8,13,21.
One of the simplest ways to generate a Fibonacci series is through recursion. Let’s create a recursive function:
fun fibonacciUsingRecursion(num: Int): Int {
return if (num <= 1) {
num
} else {
fibonacciUsingRecursion(num - 1) + fibonacciUsingRecursion(num - 2)
}
}
This function uses recursive calls to calculate the Fibonacci number. The argument defines which Fibonacci number we want to return. Moreover, if the argument equals 1, the function returns it without calculation. On the other hand, when the argument is higher than 1, we start calling the function for values deducted by 1 and 2.
Let’s create a test for it:
@Test
fun `test checkIfFibonacciUsingRecursion return correct value`() {
Assertions.assertThat(fibonacciUsingRecursion(8)).isEqualTo(21)
}
As expected, the correct value is 21. The recursion is straightforward from the code perspective, but it’s expensive from a complexity point of view.
3. Iterative Approach
Now, let’s have a look at the iterative approach:
fun fibonacciUsingIteration(num: Int): Int {
var a = 0
var b = 1
var tmp: Int
for (i in 2..num) {
tmp = a + b
a = b
b = tmp
}
return b
}
In this approach, we are using a loop instead of the recursion. Thanks to that, it’s more efficient for larger values.
Let’s do the same test as in the first approach:
@Test
fun `test checkIfFibonacciUsingIteration return correct value`() {
Assertions.assertThat(fibonacciUsingIteration(8)).isEqualTo(21)
}
4. Use Tail Recursion
Now, let’s have a look at the tail recursion method. It’s a specialized form of recursion where the recursive call is the last operation in the function. Kotlin supports tail recursion optimization for efficiency.
Here’s how we can use tail recursion to generate the Fibonacci series:
tailrec fun fibonacciUsingTailRecursion(num: Int, a: Int = 0, b: Int = 1): Int {
return if (num == 0) a else fibonacciUsingTailRecursion(num - 1, b, a + b)
}
Firstly, we instruct the compiler to consider it for tail recursion with the tailrec keyword. The keyword tells the compiler that the recursion may be replaced with a loop. Additionally, the second and third arguments have default values. Thanks to that, we didn’t provide it in the initial call. Those arguments are used to hold the Fibonacci value.
Let’s test it:
@Test
fun `test checkIfFibonacciUsingTailRecursion return correct value`() {
Assertions.assertThat(fibonacciUsingTailRecursion(8)).isEqualTo(21)
}
5. Functional Approach for Fibonacci Generation
Now, we’ll see the calculation using a functional approach. It allows us to generate the Fibonacci sequence in a straightforward and expressive manner.
We’ll use the generateSequence() function. The function provides an easy way to create any sequence of elements. Moreover, it executes lazy.
Let’s see the implementation:
fun fibonacciUsingSequence(num: Int): Int {
val fibonacciSequence = generateSequence(Pair(1, 1), { Pair(it.second, it.first + it.second) }).map { it.first }
return fibonacciSequence.take(num).last()
}
Firstly, we create the function finobacciSequence(). After that, we call the take() method to generate first num elements. Finally, we return the last element from the sequence. The map function is an intermediate operation. On the other hand, the take() function is a terminal operation.
Let’s confirm that it works:
@Test
fun `test checkIfFibonacciSequence return correct value`() {
Assertions.assertThat(fibonacciUsingSequence(8)).isEqualTo(21)
}
6. Conclusion
In this article, we’ve explored different methods to generate Fibonacci sequences in Kotlin. We’ve discussed classic recursive and iterative approaches. After that, we saw the optimized for the efficiency tail recursion version.
Finally, we looked at the functional approach using Kotlin’s capabilities. The choice of method depends on our specific use case and performance requirements.
As always, the source code of the examples is available over on GitHub.