Do recursive sequences leak memory?

Question

I like to define sequences recursively as follows:

let rec startFrom x =
    seq {
        yield x;
        yield! startFrom (x + 1)
    }

I'm not sure if recursive sequences like this should be used in practice. The yield! appears to be tail recursive, but I'm not 100% sure since its being called from inside another IEnumerable. From my point of view, the code creates an instance of IEnumerable on each call without closing it, which would actually make this function leak memory as well.

Will this function leak memory? For that matter is it even "tail recursive"?

[Edit to add]: I'm fumbling around with NProf for an answer, but I think it would be helpful to get a technical explanation regarding the implementation of recursive sequences on SO.

Answer 1

.NET applications don't "leak" memory in this way. Even if you are creating many objects a garbage collection will free any objects that have no roots to the application itself.

Memory leaks in .NET usually come in the form of unmanaged resources that you are using in your application (database connections, memory streams, etc.). Instances like this in which you create multiple objects and then abandon them are not considered a memory leak since the garbage collector is able to free the memory.

Answer 2

It won't leak any memory, it'll just generate an infinite sequence, but since sequences are IEnumerables you can enumerate them without memory concerns. The fact that the recursion happens inside the sequence generation function doesn't impact the safety of the recursion. Just mind that in debug mode tail call optimization may be disabled in order to allow full debugging, but in release there'll be no issue whatsoever.

Answer 3

I'm at work now so I'm looking at slightly newer bits than Beta1, but on my box in Release mode and then looking at the compiled code with .Net Reflector, it appears that these two

let rec startFromA x =    
    seq {        
        yield x     
        yield! startFromA (x + 1)    
    }

let startFromB x =    
    let z = ref x
    seq {        
        while true do
            yield !z
            incr z
    }

generate almost identical MSIL code when compiled in 'Release' mode. And they run at about the same speed as this C# code:

public class CSharpExample
{
    public static IEnumerable<int> StartFrom(int x)
    {
        while (true)
        {
            yield return x;
            x++;
        }
    }
}

(e.g. I ran all three versions on my box and printed the millionth result, and each version took about 1.3s, +/- 1s). (I did not do any memory profiling; it's possible I'm missing something important.)

In short, I would not sweat too much thinking about issues like this unless you measure and see a problem.

EDIT

I realize I didn't really answer the question... I think the short answer is "no, it does not leak". (There is a special sense in which all 'infinite' IEnumerables (with a cached backing store) 'leak' (depending on how you define 'leak'), see

http://stackoverflow.com/questions/898988/avoiding-stack-overflow-with-f-infinite-sequences-of-sequences

for an interesting discussion of IEnumerable (aka 'seq') versus LazyList and how the consumer can eagerly consume LazyLists to 'forget' old results to prevent a certain kind of 'leak'.)