In Chapter 2, Getting Started with Functional Programming, in the section, Recursion, we cover recursion extensively (albeit there are recursion topics that are outside the scope of this book).
We used recursion to write classic algorithms such as Fibonacci (we're reusing tailrecFib from Chapter 2, Getting Started with Functional Programming):
fun tailrecFib(n: Long): Long {
tailrec fun go(n: Long, prev: Long, cur: Long): Long {
return if (n == 0L) {
prev
} else {
go(n - 1, cur, prev + cur)
}
}
return go(n, 0, 1)
}And Factorial (same here, reusing tailrecFactorial from Chapter 2, Getting Started with Functional Programming):
fun tailrecFactorial(n: Long): Long {
tailrec fun go(n: Long, acc: Long): Long {
return if (n <= 0) {
acc
} else {
go(n - 1, n * acc)
}
}
return go(n, 1)
}In both cases, we started with a number, and we reduced it to reach a base condition.
Another example...