Return to Answer

NB3: The stack spool itself is apparently implemented as a non unique clustered index with key column of recursion level and uniqueifiers added as needed (source)

using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Program
{
    private static readonly Stack<Tuple<long, int>> StackSpool = new Stack<Tuple<long, int>>();

    private static void Main(string[] args)
    {
        //temp table #NUMS
        var nums = new[] { 3, 5, 7 };

        //Anchor member
        foreach (var number in nums)
            AddToStackSpoolAndEmit(number, 0);

        //Recursive part
        ProcessStackSpool();

        Console.WriteLine("Finished");
        Console.ReadLine();
    }

    private static void ProcessStackSpool()
    {
        //recursion base case
        if (StackSpool.Count == 0)
            return;

        var row = StackSpool.Pop();

        var thisLevel = row.Item2 + 1;
        var thisNum = row.Item1 * row.Item1;

        Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

        if (thisNum < 10000000)
            AddToStackSpoolAndEmit(thisNum, thisLevel);

        ProcessStackSpool();
    }

    private static void AddToStackSpoolAndEmit(long number, int recursionLevel)
    {
        StackSpool.Push(Tuple.Create(number, recursionLevel));
        Console.WriteLine(number);
    }
}

using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Program
{
    private static readonly Stack<dynamic> StackSpool = new Stack<dynamic>();

    private static void Main(string[] args)
    {
        //temp table #NUMS
        var nums = new[] { 3, 5, 7 };

        //Anchor member
        foreach (var number in nums)
            AddToStackSpoolAndEmit(number, 0);

        //Recursive part
        ProcessStackSpool();

        Console.WriteLine("Finished");
        Console.ReadLine();
    }

    private static void AddToStackSpoolAndEmit(long number, int recursionLevel)
    {
        StackSpool.Push(new { N = number, RecursionLevel = recursionLevel });
        Console.WriteLine(number);
    }

    private static void ProcessStackSpool()
    {
        //recursion base case
        if (StackSpool.Count == 0)
            return;

        var row = StackSpool.Pop();

        int thisLevel = row.RecursionLevel + 1;
        long thisN = row.N * row.N;

        Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

        if (thisN < 10000000)
            AddToStackSpoolAndEmit(thisN, thisLevel);

        ProcessStackSpool();
    }
}

The above is how it works logically. Physically recursive CTEs are currently always implemented with nested loops and a stack spool in SQL Server. This is described here and here.

The above is how it works logically. Physically recursive CTEs are currently always implemented with nested loops and a stack spool in SQL Server. This is described here and here and means that in practice each recursive element is just working with the parent row from the previous level, not the whole level. But the various restrictions on allowable syntax in recursive CTEs mean this approach works.

NB1: As above by the time the first child of anchor member 3 is being processed all information about its siblings, 5 and 7, and their descendants, has already been discarded from the spool and is no longer accessible.

NB2: The C# above has the same overall semantics as the execution plan but the flow in the execution plan is not identical, as there the operators work in a pipelined exection fashion. This is a simplified example to demonstrate the gist of the approach. See the earlier links for more details on the plan itself.