TypeScript Recursive Types

A recursive type is a type that references itself, and it is very useful for handling tree structures and nested data.

TypeScript supports recursive type definitions, allowing you to express data structures of infinite depth.

SVG Illustration: How Recursive Types Work

Why Do We Need Recursive Types?

In the real world, data structures are often nested.

For example, a file system has folders and subfolders, an organizational structure has departments and sub-departments, and JSON data can be nested infinitely.

Recursive types allow us to express this kind of infinitely nested structure, and they are the cornerstone of handling tree-shaped data.

Concept:A recursive type is a type that references itself in its own definition, and it can express nested structures of arbitrary depth.

Tree Structure

The most common application of recursive types is to represent tree structures.

Example

// Define tree node type, children references itself
interface TreeNode {
id: number; // Node ID
name: string; // Node name
children?: TreeNode[]; // Child node array, recursive reference
}

// Create a tree structure
const fileSystem: TreeNode = {
id: 1,
name: "Root",
children: [
{
id: 2,
name: "Folder 1",
children: [
{ id: 5, name: "File A.txt" },
{ id: 6, name: "File B.txt" }
]
},
{
id: 3,
name: "Folder 2",
children: [
{ id: 7, name: "File C.txt" }
]
},
{
id: 4,
name: "File.txt"
}
]
};

// Function to traverse the tree
function traverse(node: TreeNode, depth: number = 0): void {
const indent = " ".repeat(depth);
console.log(indent + "📁 " + node.name);

if (node.children) {
for (const child of node.children) {
traverse(child, depth + 1);
}
}
}

traverse(fileSystem);

Output:

&#x1f4c1; 根目录
  &#x1f4c1; 文件夹1
    &#x1f4c1; 文件A.txt
    &#x1f4c1; 文件B.txt
  &#x1f4c1; 文件夹2
    &#x1f4c1; 文件C.txt
  &#x1f4c1; 文件.txt

File system:Tree structure is a classic application of recursive types, and it can represent directory trees, organizational structures, and more.

Nested Lists

Recursive types can also represent nested list structures.

Example

// Define nested list type
type NestedList<T> = T | NestedList<T>[];

// Define task type
interface Task {
id: number;
title: string;
completed: boolean;
}

// Create a nested task list
const tasks: NestedList<Task> = [
{ id: 1, title: "Project A", completed: false },
[
{ id: 2, title: "Subtask 1", completed: true },
{ id: 3, title: "Subtask 2", completed: false }
],
{ id: 4, title: "Project B", completed: false }
];

// Calculate the depth of the nested list
function getDepth<T>(list: NestedList<T>, depth: number = 0): number {
if (Array.isArray(list)) {
let maxDepth = depth + 1;
for (const item of list) {
maxDepth = Math.max(maxDepth, getDepth(item, depth + 1));
}
return maxDepth;
}
return depth;
}

console.log("List depth: " + getDepth(tasks));

Union type:Using T | NestedList[] can handle both individual elements and arrays.

Deep Readonly Type

Use recursive types to implement deep readonly transformation.

Example

// Deep readonly type - recursive application
type DeepReadonly<T> = T extends Function
? T // Functions remain unchanged
: T extends object
? { readonly [P in keyof T]: DeepReadonly<T[P]> }
: T;

// User type
interface User {
name: string;
profile: {
email: string;
address: {
city: string;
zip: string;
};
};
friends: User[];
}

// Create a deeply readonly user
const user: DeepReadonly<User> = {
name: "Alice",
profile: {
email: "[email protected]",
address: {
city: "Beijing",
zip: "100000"
}
},
friends: []
};

// Attempting to modify will cause an error
// user.name = "Bob"; // Error: name is readonly
// user.profile.address.city = "Shanghai"; // Error: nested properties are also readonly

console.log("User: " + user.name);
console.log("City: " + user.profile.address.city);

Recursive transformation:DeepReadonly recursively converts all nested object properties to readonly.

Deep Partial Type

Use recursive types to implement deep optional transformation.

Example

// Deep partial type - recursive application
type DeepPartial<T> = T extends object
? { [P in keyof T]?: DeepPartial<T[P]> }
: T;

// Configuration type
interface AppConfig {
database: {
host: string;
port: number;
credentials: {
username: string;
password: string;
};
};
server: {
port: number;
ssl: boolean;
};
}

// Using deep partial, you can provide only part of the configuration
const partialConfig: DeepPartial<AppConfig> = {
database: {
host: "localhost"
// port and credentials are optional
}
// server is optional
};

console.log("Database host: " + partialConfig.database?.host);

Optional nesting:DeepPartial recursively makes all properties optional, making it easier to handle partial configurations.

Linked Data Structures

Recursive types can represent linked data structures such as linked lists.

Example

// Linked list node type
interface ListNode<T> {
value: T; // Value of the current node
next?: ListNode<T>; // Next node, recursive reference
}

// Create a linked list
const linkedList: ListNode<number> = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: undefined
}
}
}
};

// Traverse the linked list
function traverseList<T>(node: ListNode<T>): void {
let current: ListNode<T> | undefined = node;
const values: T[] = [];

while (current) {
values.push(current.value);
current = current.next;
}

console.log("Linked list values: " + values.join(" -> "));
}

traverseList(linkedList);

// Calculate the length of the linked list
function getLength<T>(node: ListNode<T>): number {
let length = 0;
let current: ListNode<T> | undefined = node;

while (current) {
length++;
current = current.next;
}

return length;
}

console.log("Linked list length: " + getLength(linkedList));

Linked list:ListNodeBy referencing itself through next, it forms a chained structure, which is a classic application of recursive types.

Recursive Union Types

Use recursive types to handle union types in JSON data.

JSON type:Recursive types can precisely express all possible types of JSON.

Example

// Recursive type definition for JSON values
type JSONValue = string | number | boolean | null | JSONValue[] | { [key: string]: JSONValue };

// Define a configuration object
const config: JSONValue = {
"name": "my-app",
"version": "1.0.0",
"enabled": true,
"settings": {
"debug": false,
"ports": [3000, 8080],
"metadata": {
"author": "Alice",
"tags": ["web", "typescript"]
}
}
};

// Function to get a JSON value
function getValue(obj: JSONValue, path: string): JSONValue | undefined {
const keys = path.split(".");
let current: JSONValue | undefined = obj;

for (const key of keys) {
if (current && typeof current === "object" && !Array.isArray(current)) {
current = (current as { [key: string]: JSONValue })[key];
} else {
return undefined;
}
}

return current;
}

console.log("Version: " + getValue(config, "version"));
console.log("Port: " + getValue(config, "settings.ports"));
console.log("Author: " + getValue(config, "settings.metadata.author"));

Notes

Recursive base case:Ensure recursive types have a termination condition to avoid infinite recursion.
Conditional types:Recursion is often used in combination with conditional types.
Depth limit:The TypeScript compiler has a limit on recursion depth.
Performance considerations:Deep recursion may affect type-checking performance.

Best practices:Recursive types are a powerful tool for handling tree-shaped and nested data. Mastering them can solve many complex type problems.

Summary

Recursive types are an advanced feature of the TypeScript type system.

Self-reference:Referencing itself in the type definition.
Tree structure:Expressing infinitely nested data.
Deep transformation:Implementing utility types such as DeepReadonly and DeepPartial.
Chained structures:Representing linear recursive structures such as linked lists.

Suggestion:When dealing with nested data, prioritize using recursive types to ensure type safety.

Other Extensions

Type System Basics

Advanced

TypeScript Recursive Types

Why Do We Need Recursive Types?

Tree Structure

Example

Nested Lists

Example

Deep Readonly Type

Example

Deep Partial Type

Example

Linked Data Structures

Example

Recursive Union Types

Example

Notes

Summary