Fold and recursion

Learn functional patterns with fold and recursion.

Accumulating with fold

fold turns a collection into an accumulator with an initial value. A lambda is called for each element; the lambda updates the accumulator.

Example: val sum = listOf(1, 2, 3, 4).fold(0) { acc, n -> acc + n }. This gives 0 + 1 + 2 + 3 + 4 = 10. fold reduces a list to a single value; unlike reduce, it takes an initial value. For an empty list, reduce throws, while fold returns the initial value.

Recursion for factorial

Recursion is a function calling itself. It is common in functional programming instead of loops. Each recursive call must approach a base case.

Example: fun fact(n: Int): Long { if (n <= 1) return 1; return n * fact(n - 1) }. n <= 1 is the base case. fact(5) returns 5 * 4 * 3 * 2 * 1 = 120. Deep recursion can cause stack overflow; this is why tailrec is used.

Exercise Sum a list with fold

In main assign the result of listOf(1, 2, 3, 4, 5).fold(0) { acc, n -> acc + n } to a variable and print it with println.

Show example solution

fun main() {
    val sum = listOf(1, 2, 3, 4, 5).fold(0) { acc, n ->
        acc + n
    }
    println(sum)
}

Test yourself

What is the key difference between fold and reduce?
- fold only works with Int
- reduce is faster
- fold takes an initial value
- fold has no side effects
Show answer

fold takes an initial value — answer: fold takes an initial value. It is safe for empty lists.
Match the fold and recursion parts

fold(0) { acc, n -> }

Accumulator
{ acc, n -> acc + n }

Lambda
if (n <= 1) return 1

Base case
fact(n - 1)

Recursive call

Complete the fold call

val sum = listOf(1, 2, 3).____(0) { acc, n -> acc + n }

Show answer

val sum = listOf(1, 2, 3).fold(0) { acc, n -> acc + n }

Next lesson: Monad

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies