Kotlin Tidbit: Loops and Recursion
Showcasing iterating using an imperative approach and a functional approach.
Given a LinkedList
data structure that is defined as:
data class LinkedList<T>(val value: T, val next: LinkedList<T>? = null)
Each LinkedList
entry is a node of the current value
and a reference to next
which points to another LinkedList
with the rest of the elements in the collection. The end of the list is denoted by next
being null
.
Here are example instances of LinkedList with Int nodes.
// 1 -> 4 -> 3 -> 1
val linkedListOne = LinkedList(1, LinkedList(4, LinkedList(3, LinkedList(1))))
// 6 -> 8 -> 3 -> 1
val linkedListTwo = LinkedList(6, LinkedList(8, LinkedList(3, LinkedList(1))))
To illustrate ways of iterating through these elements, let's write a function that returns the number of elements in the LinkedList.
Using while
Loop.
Using this imperative approach, we keep track of the number of elements in the collection via a variable count
; as long as there is a next
node we keep counting the elements.
Here we are making use of statements, and relying on side-effects to achieve our end goal by specifying step by step what needs to be done.
fun LinkedList<*>?.size(): Int {
var count = 0
var current: LinkedList<*>? = this
while (current != null) {
count++
current = current.next
}
return count
}
Using Recursion.
Using this functional approach, we keep track of the total number of elements in the collection by repeatedly evaluating an expression to count the total number of elements in the collection until the last element.
Here we are making use of a recursive function, that repeatedly evaluates if the current node is null
and if it is it returns the total number of elements c
, otherwise, it calls itself again for evaluation passing the total number of elements increased by 1, and a reference to the next
node in the collection.
fun LinkedList<*>?.length(): Int {
tailrec fun count(c: Int, l: LinkedList<*>?): Int =
if (l == null) c
else count(c + 1, l.next)
return count(0, this)
}
Conclusion.
Both approaches yield the same result in terms of figuring out the total number of elements in a particular collection. This Kotlin Tidbit serves to illustrate how looping can be achieved using either an imperative or a functional approach.