Programming Kotlin

The Power and Perils of Recursion

Using recursion we can apply the divide and conquer technique: solve a problem by implementing solutions to its subproblems. For example, here’s a piece of Kotlin code to perform one implementation of the quick sort algorithm:

recursion/quicksort.kts

fun sort(numbers: List<Int>): List<Int> =
  if (numbers.isEmpty())
    numbers

  else {
    val pivot = numbers.first()
    val tail = numbers.drop(1)
    val lessOrEqual = tail.filter { e -> e <= pivot }
    val larger = tail.filter { e -> e > pivot }

    sort(lessOrEqual) + pivot + sort(larger)
  }

println(sort(listOf(12, 5, 15, 12, 8, 19))) //[5, 8, 12, 12, 15, 19]

The sort() function splits the given input into two parts, sorts the two parts separately, ...