C# Language Yield Keyword Lazy Evaluation Example: Fibonacci Numbers
Example
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics; // also add reference to System.Numberics
namespace ConsoleApplication33
{
class Program
{
private static IEnumerable<BigInteger> Fibonacci()
{
BigInteger prev = 0;
BigInteger current = 1;
while (true)
{
yield return current;
var next = prev + current;
prev = current;
current = next;
}
}
static void Main()
{
// print Fibonacci numbers from 10001 to 10010
var numbers = Fibonacci().Skip(10000).Take(10).ToArray();
Console.WriteLine(string.Join(Environment.NewLine, numbers));
}
}
}
How it works under the hood (I recommend to decompile resulting .exe file in IL Disaambler tool):
- C# compiler generates a class implementing
IEnumerable<BigInteger>andIEnumerator<BigInteger>(<Fibonacci>d__0in ildasm). - This class implements a state machine. State consists of current position in method and values of local variables.
- The most interesting code are in
bool IEnumerator.MoveNext()method. Basically, whatMoveNext()do:- Restores current state. Variables like
prevandcurrentbecome fields in our class (<current>5__2and<prev>5__1in ildasm). In our method we have two positions (<>1__state): first at the opening curly brace, second atyield return. - Executes code until next
yield returnoryield break/}. - For
yield returnresulting value is saved, soCurrentproperty can return it.trueis returned. At this point current state is saved again for the nextMoveNextinvocation. - For
yield break/}method just returnsfalsemeaning iteration is done.
- Restores current state. Variables like
Also note, that 10001th number is 468 bytes long. State machine only saves current and prev variables as fields. While if we would like to save all numbers in the sequence from the first to the 10000th, the consumed memory size will be over 4 megabytes. So lazy evaluation, if properly used, can reduce memory footprint in some cases.
