コンスセルや再帰を使わずに直積

結論：スタックを使え。
ただし、Stack<T>はミュータブルコレクションなので、状況によっては使いにくい。
下のコードだと、IEnumerable<T>にPushしている拡張メソッド。
これはPushの結果が別インスタンスになることが重要なので、本当はコンスセルのほうが都合がいい。

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var upperOrLower = "ABCD"
            .Select(x => new[] { char.ToUpper(x), char.ToLower(x) }.AsEnumerable())
            .DirectProduct(x => new string(x.ToArray()));

        foreach (var s in upperOrLower)
        {
            Console.WriteLine(s);
        }
    }
}

public static class EnumerableEx
{
    public static IEnumerable<TResult> DirectProduct<T, TResult>(
        this IEnumerable<IEnumerable<T>> source,
        Func<IEnumerable<T>, TResult> collector)
    {
        return source
            .FoldRight(
                Enumerable.Repeat(Enumerable.Empty<T>(), 1),
                (p, q) => p.SelectMany(x => q.Select(y => y.Push(x))))
            .Select(x => collector(x));
    }

    public static TAccumulate FoldRight<T, TAccumulate>(
        this IEnumerable<T> source,
        TAccumulate seed,
        Func<T, TAccumulate, TAccumulate> func)
    {
        Stack<T> stack = new Stack<T>();
        foreach (T item in source) stack.Push(item);
        while (stack.Count > 0) seed = func(stack.Pop(), seed);
        return seed;
    }

    public static IEnumerable<T> Push<T>(this IEnumerable<T> source, T head)
    {
        yield return head;
        foreach (T item in source) yield return item;
    }
}