The Ultimate Guide to Kotlin Programming/

...

/

The Power and Perils of Recursion

The Power and Perils of Recursion

We'll cover the following...

Recursion with divide and conquer

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:

Press + to interact
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, and, finally, merges the two solutions to create the overall solution. Kotlin readily supports general recursion, but it requires the return type ...