Entendendo Tipos Recursivos em TypeScript
Um tipo recursivo é aquele que faz referência a si mesmo em sua definição. Em TypeScript, isso é extremamente útil quando trabalhamos com estruturas de dados que possuem natureza hierárquica ou aninhada, como árvores, grafos e documentos JSON complexos. A razão pela qual isso funciona em TypeScript é que o compilador permite que tipos façam auto-referência, desde que a recursão seja resolvida em tempo de compilação.
A importância de dominar tipos recursivos vai além de um exercício acadêmico: aplicações reais frequentemente precisam lidar com dados aninhados arbitrariamente. Quando você trabalha com APIs REST que retornam estruturas profundas, sistemas de arquivos hierárquicos ou até mesmo parsers de expressões matemáticas, tipos recursivos são a ferramenta correta para garantir segurança de tipos sem perder flexibilidade.
Tipos Recursivos Básicos e Padrões Comuns
O Padrão Fundamental
O padrão mais simples de um tipo recursivo é aquele que define um nó contendo dados e uma referência a si mesmo. Vamos começar com um exemplo clássico: uma lista ligada.
interface Node<T> {
value: T;
next: Node<T> | null;
}
const linkedList: Node<number> = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: null
}
}
};
Aqui, Node faz referência a si mesmo através de next: Node<T> | null. O | null é crucial: ele fornece a condição de parada da recursão, impedindo uma cadeia infinita de tipos.
Árvores Binárias
Um caso de uso muito comum é representar árvores binárias. Cada nó pode ter zero, um ou dois filhos:
interface TreeNode<T> {
value: T;
left: TreeNode<T> | null;
right: TreeNode<T> | null;
}
const binaryTree: TreeNode<string> = {
value: "A",
left: {
value: "B",
left: {
value: "D",
left: null,
right: null
},
right: {
value: "E",
left: null,
right: null
}
},
right: {
value: "C",
left: null,
right: null
}
};
Note que TypeScript verifica que cada left e right é exatamente do tipo TreeNode<T> | null. Isso garante que estruturas malformadas serão detectadas durante o desenvolvimento.
O Padrão com Array (Árvores N-árias)
Quando uma estrutura pode ter um número arbitrário de filhos, usamos arrays:
interface TreeNodeNary<T> {
value: T;
children: TreeNodeNary<T>[];
}
const naryTree: TreeNodeNary<number> = {
value: 1,
children: [
{
value: 2,
children: [
{ value: 5, children: [] },
{ value: 6, children: [] }
]
},
{
value: 3,
children: []
},
{
value: 4,
children: [
{ value: 7, children: [] }
]
}
]
};
Trabalhando com JSON Tipado e Estruturas Profundas
JSON como Tipo Recursivo
JSON é naturalmente recursivo: um objeto pode conter outros objetos, arrays podem conter qualquer coisa. TypeScript oferece formas poderosas de tipificar JSON mantendo flexibilidade:
type JSONValue =
| string
| number
| boolean
| null
| JSONObject
| JSONArray;
interface JSONObject {
[key: string]: JSONValue;
}
interface JSONArray extends Array<JSONValue> {}
const complexJSON: JSONValue = {
user: {
name: "Alice",
age: 30,
posts: [
{
id: 1,
title: "First Post",
comments: [
{ author: "Bob", text: "Great!" },
{ author: "Carol", text: "Thanks!" }
]
},
{
id: 2,
title: "Second Post",
comments: []
}
]
},
count: 42,
active: true
};
Este tipo permite que TypeScript entenda que complexJSON pode ter profundidade arbitrária, mas mantém segurança de tipos em cada nível.
Filtrando e Transformando Estruturas Profundas
Um desafio comum é manipular estruturas recursivas. Vamos criar uma função que extrai todos os valores primitivos de um JSON:
function extractPrimitives(value: JSONValue): (string | number | boolean | null)[] {
if (value === null || typeof value === 'string' || typeof value === 'number' || typeof value === 'boolean') {
return [value];
}
if (Array.isArray(value)) {
return value.flatMap(item => extractPrimitives(item));
}
// É um objeto
return Object.values(value).flatMap(item => extractPrimitives(item));
}
const primitives = extractPrimitives(complexJSON);
// Resultado: [Alice, 30, 1, "First Post", "Bob", "Great!", "Carol", "Thanks!", 2, "Second Post", 42, true]
Validação em Tempo de Compilação
TypeScript verifica recursivamente que seus dados correspondem ao tipo esperado. Se tentarmos atribuir um valor inválido:
// Isto causará erro de compilação
const invalido: JSONValue = {
data: undefined // undefined não é parte de JSONValue
};
// Isto também causa erro
const invalido2: TreeNode<string> = {
value: "A",
left: "B", // erro: string não é TreeNode<string> | null
right: null
};
Operações Úteis com Tipos Recursivos
Mapeamento de Tipos Recursivos
Às vezes você precisa transformar um tipo recursivo em outro. Por exemplo, converter uma árvore em um tipo que rastreia a profundidade:
interface TreeNodeWithDepth<T> {
value: T;
depth: number;
left: TreeNodeWithDepth<T> | null;
right: TreeNodeWithDepth<T> | null;
}
function addDepth<T>(
node: TreeNode<T> | null,
depth: number = 0
): TreeNodeWithDepth<T> | null {
if (node === null) return null;
return {
value: node.value,
depth,
left: addDepth(node.left, depth + 1),
right: addDepth(node.right, depth + 1)
};
}
const treeWithDepth = addDepth(binaryTree);
// treeWithDepth.depth === 0
// treeWithDepth.left?.depth === 1
// treeWithDepth.left?.left?.depth === 2
Busca e Navegação
Percorrer estruturas recursivas é fundamental. Aqui está uma função genérica que busca um valor em uma árvore:
function findInTree<T>(
node: TreeNode<T> | null,
predicate: (value: T) => boolean
): T | null {
if (node === null) return null;
if (predicate(node.value)) {
return node.value;
}
const foundLeft = findInTree(node.left, predicate);
if (foundLeft !== null) return foundLeft;
return findInTree(node.right, predicate);
}
const found = findInTree(binaryTree, value => value === "E");
console.log(found); // "E"
Serialização Segura
Ao serializar estruturas recursivas para JSON, TypeScript garante que você não esqueça de nenhum campo:
function serializeTree<T>(node: TreeNode<T> | null): string {
if (node === null) return "null";
return JSON.stringify({
value: node.value,
left: JSON.parse(serializeTree(node.left)),
right: JSON.parse(serializeTree(node.right))
});
}
const serialized = serializeTree(binaryTree);
console.log(serialized);
Padrões Avançados e Limitações
Tipos Recursivos Mutuamente Dependentes
Às vezes dois tipos precisam referenciar um ao outro. TypeScript permite isso através de interfaces:
interface Expression {
evaluate(): number;
}
interface BinaryOp extends Expression {
type: 'add' | 'subtract' | 'multiply' | 'divide';
left: Expression;
right: Expression;
evaluate(): number;
}
interface Literal extends Expression {
type: 'literal';
value: number;
evaluate(): number;
}
type Expr = BinaryOp | Literal;
const expr: Expr = {
type: 'add',
left: { type: 'literal', value: 5, evaluate: () => 5 },
right: {
type: 'multiply',
left: { type: 'literal', value: 3, evaluate: () => 3 },
right: { type: 'literal', value: 2, evaluate: () => 2 },
evaluate: function() { return 6; }
},
evaluate: function() { return 11; }
};
Cuidado com Circularidade
TypeScript previne tipos circulares que não podem ser resolvidos. Isto não é permitido:
// ERRO: Type alias 'Circular' circularly references itself
// type Circular = {
// self: Circular
// };
Mas isto é:
interface Circular {
self: Circular | null; // null fornece a saída
}
Profundidade Máxima em Tipos Condicionais
Quando você usa tipos recursivos com tipos condicionais, TypeScript tem um limite de profundidade para evitar loops infinitos na verificação de tipos. Este é um detalhe avançado, mas importante estar ciente:
type Flatten<T> = T extends Array<infer U> ? Flatten<U> : T;
// Isto funciona para profundidades razoáveis
type Test1 = Flatten<[[[1]]]>; // 1
type Test2 = Flatten<[[[[[[[[[1]]]]]]]]]>; // Pode exceder limite
// TypeScript pode emitir erro se recursão for muito profunda
Conclusão
Três aprendizados principais saem deste estudo: Primeiro, tipos recursivos são a ferramenta correta para estruturas hierárquicas, e TypeScript torna seguro trabalhar com árvores, JSON aninhado e grafos através de auto-referência controlada. Segundo, a necessidade de uma condição de parada (como | null ou []) é fundamental — sem ela, não há como o compilador resolver a recursão. Terceiro, padrões práticos como busca, mapeamento e serialização se tornam simples e type-safe quando você domina estes conceitos, eliminando categorias inteiras de bugs em tempo de execução.