Recursion is a powerful programming technique where a function calls itself to solve a problem. Recursive solutions are often elegant and concise, especially for problems that can be divided into similar subproblems.
This guide covers the following aspects of recursion in Kotlin:
- Basics of Recursion
- Tail Recursion Optimization
- Major Recursive Algorithms
- Real-world Examples
1. Basics of Recursion
In a recursive function, the function calls itself to solve smaller instances of the same problem. To prevent infinite recursion, there must be a base case that stops the recursion.
Here’s a simple example of a recursive function to calculate the factorial of a number:
fun factorial(n: Int): Int {
return if (n == 0) 1 else n * factorial(n - 1)
}
fun main() {
println(factorial(5)) // Output: 120
}
2. Tail Recursion Optimization
Kotlin supports tail recursion optimization, which allows the compiler to optimize recursive calls and prevent stack overflow errors by reusing the current function’s stack frame.
A function is tail-recursive if the last operation of the function is the recursive call. To make a function tail-recursive, use the tailrec modifier:
tailrec fun factorial(n: Int, accumulator: Int = 1): Int {
return if (n == 0) accumulator else factorial(n - 1, n * accumulator)
}
fun main() {
println(factorial(5)) // Output: 120
}
3. Major Recursive Algorithms
Here are some common recursive algorithms implemented in Kotlin:
3.1. Fibonacci Sequence
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones.
fun fibonacci(n: Int): Int {
return if (n <= 1) n else fibonacci(n - 1) + fibonacci(n - 2)
}
fun main() {
println(fibonacci(10)) // Output: 55
}
3.2. Binary Search
Binary search is an efficient algorithm for finding an item from a sorted list.
fun binarySearch(arr: IntArray, key: Int, low: Int = 0, high: Int = arr.size - 1): Int {
if (low > high) return -1
val mid = (low + high) / 2
return when {
arr[mid] == key -> mid
arr[mid] > key -> binarySearch(arr, key, low, mid - 1)
else -> binarySearch(arr, key, mid + 1, high)
}
}
fun main() {
val arr = intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9)
println(binarySearch(arr, 5)) // Output: 4
}
3.3. Merge Sort
Merge sort is a divide-and-conquer algorithm for sorting an array.
fun mergeSort(arr: IntArray): IntArray {
if (arr.size <= 1) return arr
val middle = arr.size / 2
val left = mergeSort(arr.sliceArray(0 until middle))
val right = mergeSort(arr.sliceArray(middle until arr.size))
return merge(left, right)
}
fun merge(left: IntArray, right: IntArray): IntArray {
var i = 0
var j = 0
val result = mutableListOf<Int>()
while (i < left.size && j < right.size) {
if (left[i] <= right[j]) {
result.add(left[i])
i++
} else {
result.add(right[j])
j++
}
}
result.addAll(left.slice(i until left.size))
result.addAll(right.slice(j until right.size))
return result.toIntArray()
}
fun main() {
val arr = intArrayOf(5, 3, 8, 4, 2, 7, 1, 10)
println(mergeSort(arr).joinToString(", ")) // Output: 1, 2, 3, 4, 5, 7, 8, 10
}
4. Real-world Examples
4.1. Directory Traversal
Recursively traverse a directory to list all files.
import java.io.File
fun listFiles(directory: File): List<File> {
val files = mutableListOf<File>()
directory.listFiles()?.forEach {
if (it.isDirectory) {
files.addAll(listFiles(it))
} else {
files.add(it)
}
}
return files
}
fun main() {
val directory = File("path/to/directory")
val files = listFiles(directory)
files.forEach { println(it) }
}
4.2. HTML Parsing
Recursively parse an HTML document to extract all links.
import org.jsoup.Jsoup
import org.jsoup.nodes.Element
import org.jsoup.select.Elements
fun extractLinks(element: Element, links: MutableList<String>) {
if (element.tagName() == "a") {
element.attr("href")?.let { links.add(it) }
}
val children: Elements = element.children()
for (child in children) {
extractLinks(child, links)
}
}
fun main() {
val html = """
<html>
<body>
<a href="https://example.com">Example</a>
<div>
<a href="https://kotlinlang.org">Kotlin</a>
</div>
</body>
</html>
""".trimIndent()
val document = Jsoup.parse(html)
val links = mutableListOf<String>()
extractLinks(document, links)
links.forEach { println(it) } // Output: https://example.com, https://kotlinlang.org
}
Recursion is a fundamental concept that can simplify solving complex problems by breaking them down into smaller, more manageable subproblems. Kotlin provides robust support for recursion, including tail recursion optimization. This guide has covered basic recursion, tail recursion, major recursive algorithms, and real-world examples, illustrating the power and versatility of recursion in Kotlin.