## DEV Community is a community of 753,038 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Huy Tr.

Posted on

# Recursive type problem in Rust

Original posted on my blog

After spending much time reading about Rust, I decided to give it a
try
. It was a very simple implementation of Binary Tree Traversal algorithm.
Surprisingly, by doing it, I learned a lot of Rust’s basic concepts!

## Rust tell us what’s wrong in our code

One of the first things that the smartass Rust compiler threw to my face was the lovely error message:

``````\$ rustc binary_tree.rs -o binary_tree
error[E0072]: recursive type `Node` has infinite size
--> binary_tree.rs:1:1
|
|
= help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Node` representable
error: aborting due to previous error
``````

So yes, this is the code:

``````struct Node {
value: i32,
left: Option<Node>,
right: Option<Node>
}
``````

This code is a very obvious way to implement a binary tree node in other
programming languages like C/C++ or Java. However, Rust compiler just doesn’t agree with us. Also, this is the interesting part.

Take a closer look. The error message said that our Node struct is a
recursive type and it has infinite size. What does it mean?

In Rust, all values are allocated in stack by default. So the compiler needs to
know the size of each. The size of a struct is the sum of all its fields size.

For example, with this struct:

``````struct Point {
x: i32,
y: u8
}
``````

So the size of Point struct is:

``````size_of::<Point>() == size_of::<i32>() + size_of::<u8>()
``````

Back to our implementation, how do we calculate our Node’s size?

``````size_of::<i32>() + 2 * size_of::<Option>() + 2 * size_of::<Node>()
``````

Let’s expand this equation: Hey hey! Hey! Stop it! You can do this for all day long. There’s no way to stop the expanding process.

So, the size of Node would be infinite and become impossible for Rust
compiler to calculate.

## And Rust also tell us how to fix it

Let’s take a look at the error message again. You can see the kindness of Rust when it tries to teach us how to repair the broken:

``````\$ rustc binary_tree.rs -o binary_tree

error[E0072]: recursive type `Node` has infinite size
--> binary_tree.rs:1:1
|
1 | struct Node {
| ^ recursive type has infinite size
|

error: aborting due to previous error
``````

If we follow the hint and add Box to our implementation, the problem will be solved:

``````struct Node {
value: i32,
left: Option<Box<Node>>,
right: Option<Box<Node>>
}
``````

However, what is Box? How does it solve our recursive reference problem?

Box is a **pointer **that pointed to a heap allocated memory space.

So when we declare a reference to Node using Box, the size of this reference is the size of a pointer, not the size of the Node type, and it is defined, so Rust compiler now aware how much memory needed to allocate for a Node. And the recursive type problem now solved!

I hope you enjoy the post and now understand the problem of recursive type, how to fix it.

Please feel free to leave a comment if you want to discuss or subscribe to my blog to keep updated about my next posts in Rust (and other technical stuff, of course).