Recursive type problem in Rust
Tags: rust
Published: 2017-10-02 20:36:48

---
title: Recursive type problem in Rust
published: true
description: Rust and recursive data types
tags: rust
---

_Original posted on [my blog](https://thefullsnack.com/en/recursive-rust.html)_

---

After spending much time reading about Rust, I decided to [give it a
try](https://github.com/huytd/thingsinrust/blob/master/binary_tree/binary_tree.rs).

![](https://cdn-images-1.medium.com/max/2000/1*UNsRZHTPh1rO1eF_VH71gw.png)

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:

![](https://cdn-images-1.medium.com/max/1600/1*rV3hH3Yq-KkS7d5sVYYCog.png)

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<T>** to our implementation, the problem will be solved:

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

However, what is **Box<T>**? How does it solve our recursive reference problem?

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

So when we declare a reference to **Node** using **Box<Node>**, *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).