F# Seq.initInfinite giving StackOverflowException

Question

I'm learning F#, and I am having trouble understanding why this crashes. It's an attempt to solve Project Euler problem 2.

let rec fibonacci n =
    if n = 1 then
        1
    elif n = 2 then
        2
    else
        fibonacci (n - 1) + fibonacci (n - 2)

let debugfibonacci n =
    printfn "CALC: %d" n
    fibonacci n

let isEven n =
    n % 2 = 0

let isUnderLimit n =
    n < 55

let getSequence =
    //[1..30]
    Seq.initInfinite (fun n -> n)
    |> Seq.map debugfibonacci
    |> Seq.filter isEven
    |> Seq.takeWhile isUnderLimit

Seq.iter (fun x -> printfn "%d" x) getSequence

The final version would call a sum function (and would have a higher limit than 55), but this is learning code.

As is, this gives a StackOverflowException. However, if I comment in the [1..30] and comment out the Seq.initInfinite, I get:

CALC: 1
CALC: 2
2
CALC: 3
CALC: 4
CALC: 5
8
CALC: 6
CALC: 7
CALC: 8
34
CALC: 9
CALC: 10
CALC: 11

It appears to be generating items on demand, as I would expect in LINQ. So why does it blow up when used with initInfinite?

Answer 1

Seq.initInfinite returns a sequence that starts at 0.

Your fibonacci function results in a stack overflow when called with zero, because it never hits the terminating cases.

You can solve this by starting from Seq.initInfinite (fun n -> n + 1)

Answer 2

You're starting with 0 with initInfinite, which then recurses -1, -2, ...

(By the way, if you're using the Visual Studio debugger, this is easy to diagnose, by checking the call stack and locals window.)