from typing import List


def gray_code(n: int) -> List[List[int]]:
    """
    Recursively generate the Gray code of order n.
    :param n: the length of the Gray code
    :return: a list of 2^n binary strings of length n, who pairwise differ from each other (cyclically) by distance 1.

    >>> gray_code(0)
    [[]]
    >>> gray_code(1)
    [[0], [1]]
    >>> gray_code(2)
    [[0, 0], [0, 1], [1, 1], [1, 0]]
    >>> gray_code(3)
    [[0, 0, 0], [0, 0, 1], [0, 1, 1], [0, 1, 0], [1, 1, 0], [1, 1, 1], [1, 0, 1], [1, 0, 0]]
    """
    if n < 0:
        raise ValueError(f"gray_code({n}) does not exist")

    if n == 0:
        return [[]]
    prev = gray_code(n - 1)
    return [[0] + c for c in prev] + [[1] + c for c in reversed(prev)]