Kotlin Tidbit: Loops and Recursion

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.