How does SQL recursion actually work?

The BOL description of recursive CTEs describes the semantics of recursive execution as being as follows:

1. Split the CTE expression into anchor and recursive members.
2. Run the anchor member(s) creating the first invocation or base result set (T0).
3. Run the recursive member(s) with Ti as an input and Ti+1 as an output.
4. Repeat step 3 until an empty set is returned.
5. Return the result set. This is a UNION ALL of T0 to Tn.

So each level only has as input the level above not the entire result set accumulated so far.

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.

If you remove the ORDER BY from your query the results are ordered as follows

+---------+
|    N    |
+---------+
|       3 |
|       5 |
|       7 |
|      49 |
|    2401 |
| 5764801 |
|      25 |
|     625 |
|  390625 |
|       9 |
|      81 |
|    6561 |
+---------+

This is because the execution plan operates very similarly to the following C#

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();
    }
}

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.

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)

This is just a (semi) educated guess, and is probably completely wrong. Interesting question, by the way.

T-SQL is a declarative language; perhaps a recursive CTE is translated into a cursor-style operation where the results from the left side of the UNION ALL is appended into a temporary table, then the right side of the UNION ALL is applied to the values in the left side.

So, first we insert the output of the left side of the UNION ALL into the result set, then we insert the results of the right side of the UNION ALL applied to the left side, and insert that into the result set. The left side is then replaced with the output from the right side, and the right side is applied again to the "new" left side. Something like this:

1. {3,5,7} -> result set
2. recursive statements applied to {3,5,7}, which is {9,25,49}. {9,25,49} is added to result set, and replaces the left side of the UNION ALL.
3. recursive statements applied to {9,25,49}, which is {81,625,2401}. {81,625,2401} is added to result set, and replaces the left side of the UNION ALL.
4. recursive statements applied to {81,625,2401}, which is {6561,390625,5764801}. {6561,390625,5764801} is added to result set.
5. Cursor is complete, since next iteration results in the WHERE clause returning false.

You can see this behavior in the execution plan for the recursive CTE:

This is step 1 above, where the left side of the UNION ALL is added to the output:

This is the right side of the UNION ALL where the output is concatenated to the result set:

The SQL Server documentation, which mentions T_i and T_i+1, is neither very understandable, nor an accurate description of the actual implementation.

The basic idea is that the recursive part of the query looks at all previous results, but only once.

It might be helpful to look how other databases implement this (to get the same result). The Postgres documentation says:

Recursive Query Evaluation

1. Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.
2. So long as the working table is not empty, repeat these steps:
   1. Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.
   2. Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.

Note
Strictly speaking, this process is iteration not recursion, but RECURSIVE is the terminology chosen by the SQL standards committee.

The SQLite documentation hints at a slightly different implementation, and this one-row-at-a-time algorithm might be the easiest to understand:

The basic algorithm for computing the content of the recursive table is as follows:

1. Run the initial-select and add the results to a queue.
2. While the queue is not empty:
   1. Extract a single row from the queue.
   2. Insert that single row into the recursive table
   3. Pretend that the single row just extracted is the only row in the recursive table and run the recursive-select, adding all results to the queue.

The basic procedure above may modified by the following additional rules:

• If a UNION operator connects the initial-select with the recursive-select, then only add rows to the queue if no identical row has been previously added to the queue. Repeated rows are discarded before being added to the queue even if the repeated rows have already been extracted from the queue by the recursion step. If the operator is UNION ALL, then all rows generated by both the initial-select and the recursive-select are always added to the queue even if they are repeats.
  […]