Как получить каждую комбинацию букв, используя yield return и рекурсию?

Вам нужно перечислить итератор:

foreach(string s in ReturnString(...)) {
    Console.WriteLine(s);
}

Это также относится к каждой итерации:

foreach(string tail in ReturnString(nextList))
    yield return letter + tail;

Кроме того, я подозреваю, что вы можете что-то сделать с SelectMany здесь.

from x in l1
from y in l2
from z in l3
select x + y + + z

Обновление:

Вот схема для произвольной версии. Я заполню детали позже.

private bool m_beforeStart;
private IList<IEnumerable<char>> m_lists;
private Stack<IEnumerator<char>> m_enumerators;

public bool MoveNext() {
    while (CurrentEnumerator != null && !CurrentEnumerator.MoveNext()) {
        RemoveLastChar(m_stringBuilder);
        PopEnumerator();
     }
     if (CurrentEnumerator == null && ! m_beforeStart) {
         return false;
     }
     m_beforeStart = false;
     while (PushEnumerator()) {
          if (!CurrenEnumerator.MoveNext()) {
              ClearEnumerators();
              return false;
          }
          m_stringBuilder.Append(
              m_currentEnumerator.Current
          );
      }
      return true;
}

public string Current {
    get {
        return m_stringBuilder.ToString();
    }
}

private IEnumerator<char> CurrentEnumerator {
    get {
        return m_enumerators.Count != 0 ? m_enumerators.Peek() : null;
    }
}

private void PopEnumerator() {
    if (m_enumerators.Count != 0) {
        m_enumerators.Pop();
    }
}

private bool PushEnumerator() {
    if (m_enumerators.Count == m_lists.Count) {
        return false;
    }
    m_enumerators.Push(m_lists[m_enumerators.Count].GetEnumerator());
}

public static IEnumerable<string> ReturnString(IEnumerable<IEnumerable<string>> matrix)
{
    if (matrix.Count() == 1)
        return matrix.First();

    return from letter in matrix.First()    // foreach letter in first list
           let tail = matrix.Skip(1)        // get tail lists
           let tailStrings = ReturnString(tail)   // recursively build lists of endings for each tail
           from ending in tailStrings       // foreach string in these tail endings
           select letter + ending;          // append letter from the first list to ending
}

вызовите как ReturnString(lst.Where(l => l.Any()), чтобы пропустить пустые последовательности.