Kotlin Recursion
Understanding functions that call themselves
🔄 What is Recursion?
Recursion in Kotlin is when a function calls itself to solve smaller parts of a problem. It's like breaking a big task into smaller, similar tasks until you reach a simple base case.
// Simple recursive function to count down
fun countdown(n: Int) {
if (n <= 0) {
println("Done!")
} else {
println(n)
countdown(n - 1) // Function calls itself
}
}
Output:
3
2
1
Done!
Key Recursion Concepts
Base Case
The stopping condition
if (n <= 0) return 1Recursive Call
Function calling itself
return n * factorial(n - 1)Problem Reduction
Making the problem smaller
fibonacci(n - 1) + fibonacci(n - 2)Stack Memory
Each call uses memory
// Be careful with deep recursion🔹 Factorial Example
Calculate factorial using recursion (5! = 5 × 4 × 3 × 2 × 1):
fun factorial(n: Int): Int {
// Base case: factorial of 0 or 1 is 1
if (n <= 1) {
return 1
}
// Recursive case: n * factorial of (n-1)
return n * factorial(n - 1)
}
fun main() {
val result = factorial(5)
println("5! = $result")
}Output:
5! = 120
🔹 Fibonacci Sequence
Generate Fibonacci numbers where each number is the sum of the two preceding ones:
fun fibonacci(n: Int): Int {
// Base cases
if (n <= 1) {
return n
}
// Recursive case: sum of previous two numbers
return fibonacci(n - 1) + fibonacci(n - 2)
}
fun main() {
for (i in 0..6) {
print("${fibonacci(i)} ")
}
}Output:
0 1 1 2 3 5 8
🔹 Sum of Array Elements
Calculate the sum of array elements recursively:
fun sumArray(arr: IntArray, index: Int = 0): Int {
// Base case: reached end of array
if (index >= arr.size) {
return 0
}
// Recursive case: current element + sum of rest
return arr[index] + sumArray(arr, index + 1)
}
fun main() {
val numbers = intArrayOf(1, 2, 3, 4, 5)
val total = sumArray(numbers)
println("Sum: $total")
}Output:
Sum: 15