[Rust] 재귀 타입 (Recursive Type)

타입 내에 스스로의 타입을 또 넣는 것은 흔한 구현 패턴 중 하나다.
특히 자료구조 같은 기반구조를 구현할 때는 상습적으로 사용된다.

Rust도 재귀 타입 표현을 지원하긴 하나, 아주 약간의 제한사항이 존재한다.

재귀 타입의 기본 원칙 중 하나는, 값 타입을 무작정 쑤셔넣는 형태로는 넣을 수가 없다는 것이다.

그냥 이렇게 넣어버리면 오류가 난다.
당연하다. 그냥 저렇게 넣으면 타입시스템은 저 구조체 타입의 크기를 알아낼 수가 없기 때문이다.
Node 안에 또 Node가 있고, 또 있고를 반복하니, 구조체 크기 파악하는데서 무한 재귀가 발생한다.

그래서 재귀 타입을 표현하기 위해서는, Box 같은 포인터 타입으로 래핑해서 제한을 해줘야 한다.

이러면 Box 자체는 어차피 고정된 포인터 크기로 평가되기 때문에 문제가 발생하지 않는다.

재귀 타입은 struct에만 사용할 수 있는 것은 아니다. union과 enum에도 사용할 수 있다.
recursive enum의 경우에는 다음과 같이 계층적인 순환구조를 사용할 때 응용할 수 있다. 대표적인 사용사례로는 JSON 구조 정의를 들 수 있겠다.

이 경우에는 Vec과 HashMap이 방금 Box의 역할을 대체한다.
저 컬렉션 구조체들의 타입 자체는 고정 크기이기 때문에 Box와 마찬가지로 유효하다.

참조
https://doc.rust-lang.org/reference/types.html#r-type.recursive