Search⌘ K
AI Features
Home
Courses
The Ultimate Guide to Kotlin Programming

The Power and Perils of Recursion

Understand how recursion works in Kotlin by exploring divide and conquer strategies, comparing recursive and iterative approaches, and recognizing recursion's limitations such as stack overflow. Learn why recursion is expressive but can be risky for large inputs and prepare to explore optimizations like tail call optimization.

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:

Kotlin
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 for recursive functions—no type inference available for ...