Why does '+' operator for sequences hang?

Question

The following is a minimal reproducible example of an application with two attempts at an unbounded Eratosthenes Sieve:

interface SieveImplementation {
    fun sieve(seq: Sequence<Int>): Sequence<Int>
}

object Attempt1 : SieveImplementation {
    override fun sieve(seq: Sequence<Int>): Sequence<Int> = sequence {
        yield(seq.first())
        yieldAll(sieve(seq.drop(1).filter { it % seq.first() != 0 }))
    }
}

object Attempt2 : SieveImplementation {
    override fun sieve(seq: Sequence<Int>): Sequence<Int> =
        sequenceOf(seq.first()) + sieve(seq.drop(1).filter { it % seq.first() != 0 })
}

fun primes(attempt: SieveImplementation): Sequence<Int> {
    return attempt.sieve(generateSequence(2) { it + 1})
}

fun main() {
    primes(Attempt1).take(5).forEach(::println)  // Works OK
    primes(Attempt2).take(5).forEach(::println)  // Hangs
}

Why does Attempt1 work just fine, but Attempt2 hangs forever?

Answer 1

In Attempt2, sieve calls itself before returning, which calls itself before returning, which calls itself before returning, and so on in an infinite loop. Thus, it can never return and will eventually crash with a StackOverflowError.

The reason why Attempt1 (seemingly) works is because it's implemented as a coroutine, i.e. the code pauses execution at each yield until the next value is requested. That too will eventually crash with a StackOverflowError if you iterate it for too long; it's just less obvious due to the incremental evaluation.