Recursive types: tipos que referenciam a si mesmos

1. Introdução aos Recursive Types

Tipos recursivos são tipos que fazem referência a si mesmos em sua definição. Diferentemente da recursão em funções, que resolve valores em tempo de execução, a recursão em tipos opera exclusivamente em tempo de compilação, permitindo modelar estruturas de dados naturalmente recursivas.

A motivação principal é capturar a estrutura de dados que contém outros elementos do mesmo tipo. Por exemplo, uma árvore onde cada nó contém subárvores:

type TreeNode<T> = {
  value: T;
  children: TreeNode<T>[];
};

const tree: TreeNode<number> = {
  value: 1,
  children: [
    { value: 2, children: [] },
    { value: 3, children: [{ value: 4, children: [] }] }
  ]
};

2. Estruturas de Dados Recursivas com Tipos

Listas encadeadas são o exemplo clássico de recursão em tipos:

type LinkedList<T> = {
  value: T;
  next: LinkedList<T> | null;
};

const list: LinkedList<number> = {
  value: 1,
  next: { value: 2, next: { value: 3, next: null } }
};

Árvores binárias demonstram recursão com múltiplas referências:

type BinaryTree<T> = {
  value: T;
  left?: BinaryTree<T>;
  right?: BinaryTree<T>;
};

const tree: BinaryTree<number> = {
  value: 10,
  left: { value: 5 },
  right: { value: 15, left: { value: 12 }, right: { value: 20 } }
};

JSON é um caso real de estrutura infinitamente aninhada:

type JSONValue =
  | string
  | number
  | boolean
  | null
  | JSONValue[]
  | { [key: string]: JSONValue };

const data: JSONValue = {
  name: "produto",
  price: 29.90,
  tags: ["eletrônico", "promoção"],
  specs: { weight: 1.5, dimensions: { width: 10, height: 20 } }
};

3. Tipos Recursivos com Genéricos e Condicionais

Recursão em tipos condicionais permite transformar estruturas complexas:

type Flatten<T> = T extends any[] ? Flatten<T[number]> : T;

type NestedArray = [[1, 2], [3, [4, 5]]];
type FlatResult = Flatten<NestedArray>; // number

DeepReadonly com infer e recursão:

type DeepReadonly<T> = {
  readonly [K in keyof T]: T[K] extends object
    ? DeepReadonly<T[K]>
    : T[K];
};

interface User {
  name: string;
  address: { city: string; zip: number };
}

type ReadonlyUser = DeepReadonly<User>;
// { readonly name: string; readonly address: { readonly city: string; readonly zip: number } }

Template literal types recursivos para caminhos de objetos:

type Paths<T, Prefix extends string = ""> = {
  [K in keyof T & string]: T[K] extends object
    ? `${Prefix}${K}` | Paths<T[K], `${Prefix}${K}.`>
    : `${Prefix}${K}`;
}[keyof T & string];

type UserPaths = Paths<{ a: { b: number; c: string }; d: boolean }>;
// "a" | "a.b" | "a.c" | "d"

4. Limitações e Armadilhas Comuns

O TypeScript impõe um limite de profundidade de recursão (tipicamente 50 níveis). Excedê-lo gera o erro:

// Erro: Type instantiation is excessively deep and possibly infinite
type DeepArray<T> = [DeepArray<T>];

Para evitar recursão infinita, sempre inclua um caso base:

type SafeDeepArray<T> = T | SafeDeepArray<T>[]; // Perigoso: sem caso base
type SafeDeepArray<T> = T[] | T[][]; // Seguro: profundidade limitada

Recursão muito profunda impacta performance da compilação. Prefira soluções com profundidade controlada.

5. Casos de Uso Avançados

Expressões matemáticas com operadores binários:

type Expression =
  | number
  | { op: "+" | "-" | "*" | "/"; left: Expression; right: Expression };

const expr: Expression = {
  op: "+",
  left: { op: "*", left: 3, right: 4 },
  right: 5
};

State machines com transições recursivas:

type StateMachine<S extends string> = {
  current: S;
  transitions: Record<string, StateMachine<S>>;
};

type LightState = "red" | "yellow" | "green";
const trafficLight: StateMachine<LightState> = {
  current: "red",
  transitions: {
    next: { current: "yellow", transitions: {} }
  }
};

Validadores recursivos para dados aninhados:

type Validator<T> = (value: unknown) => value is T;

const isNumber: Validator<number> = (v): v is number => typeof v === "number";
const isString: Validator<string> = (v): v is string => typeof v === "string";

function isArrayOf<T>(itemValidator: Validator<T>): Validator<T[]> {
  return (v): v is T[] =>
    Array.isArray(v) && v.every(itemValidator);
}

const isNumberArray = isArrayOf(isNumber);

6. Recursive Types com Mapped Types e Indexed Access

DeepPartial aplica recursão em todas as propriedades:

type DeepPartial<T> = {
  [K in keyof T]?: T[K] extends object ? DeepPartial<T[K]> : T[K];
};

interface Config {
  server: { host: string; port: number };
  debug: boolean;
}

type PartialConfig = DeepPartial<Config>;
// { server?: { host?: string; port?: number }; debug?: boolean }

Acesso indexado para extrair tipos folha:

type LeafType<T> = T extends { children: infer C } ? LeafType<C> : T;

type Tree = { value: string; children: { value: number } };
type Leaf = LeafType<Tree>; // number

OmitDeep para remover propriedades em qualquer profundidade:

type OmitDeep<T, K extends string> = T extends object
  ? { [P in keyof T as P extends K ? never : P]: OmitDeep<T[P], K> }
  : T;

type Data = { a: { b: { c: string; secret: number } }; secret: boolean };
type CleanData = OmitDeep<Data, "secret">;
// { a: { b: { c: string } } }

7. Padrões e Melhores Práticas

Type aliases vs interfaces: para tipos recursivos, prefira type quando precisar de condicionais ou uniões, e interface para objetos simples:

// Bom com interface
interface TreeNode<T> {
  value: T;
  children: TreeNode<T>[];
}

// Necessário type para condicionais
type DeepPartial<T> = { [K in keyof T]?: T[K] extends object ? DeepPartial<T[K]> : T[K] };

Estratégias para limitar profundidade:

type DeepPick<T, Path extends string, Depth extends number = 5> =
  Depth extends 0
    ? never
    : Path extends `${infer Key}.${infer Rest}`
      ? Key extends keyof T
        ? DeepPick<T[Key], Rest, Subtract<Depth, 1>>
        : never
      : Path extends keyof T
        ? T[Path]
        : never;

Prefira tipos utilitários prontos (DeepPartial, DeepReadonly) em vez de reimplementar. Use recursão explícita apenas quando necessário.

8. Conclusão e Próximos Passos

Tipos recursivos são fundamentais para modelar estruturas de dados complexas em TypeScript com segurança de tipos. Desde listas encadeadas até transformações profundas de objetos, eles permitem expressar padrões que seriam impossíveis com tipos planos.

Para aprofundar, explore:
- Phantom types: tipos que existem apenas em tempo de compilação
- Variadic tuple types: manipulação de tuplas de tamanho variável
- Template literal types: para validação de strings em tempo de compilação

Exercícios sugeridos:
1. Implemente DeepNonNullable<T> que remove null e undefined recursivamente
2. Crie Paths<T> que retorna todas as chaves aninhadas como strings separadas por ponto
3. Implemente DeepMerge<T, U> que mescla objetos recursivamente

Referências