Box and recursion

Define recursive types with Box.

Box and recursion

A type containing itself can't be written directly, because its size would be infinite. Box fixes the size by putting a pointer in between:

enum Liste {
    Dugum(i32, Box<Liste>),
    Bos,
}

// enum Liste { Dugum(i32, Liste), Bos }   // error E0072: infinite size

use Liste::{Bos, Dugum};
let l = Dugum(1, Box::new(Dugum(2, Box::new(Dugum(3, Box::new(Bos))))));

The compiler suggests exactly this in its error message: "insert some indirection (e.g., a `Box`, `Rc`, or `&`)".

Recursive functions

Recursive types are naturally processed with recursive functions; match separates each variant:

fn toplam(l: &Liste) -> i32 {
    match l {
        Dugum(v, sonraki) => v + toplam(sonraki),
        Bos => 0,
    }
}

sonraki is a &Box<Liste> and is auto-dereferenced when passed to the function expecting &Liste.

Exercise Linked list

Write the Liste enum above and the toplam function; also add an uzunluk function returning the number of nodes. Print both for the list 1 → 2 → 3, separated by a space.

Show example solution

enum Liste {
    Dugum(i32, Box<Liste>),
    Bos,
}

use Liste::{Bos, Dugum};

fn toplam(l: &Liste) -> i32 {
    match l {
        Dugum(v, sonraki) => v + toplam(sonraki),
        Bos => 0,
    }
}

fn uzunluk(l: &Liste) -> usize {
    match l {
        Dugum(_, sonraki) => 1 + uzunluk(sonraki),
        Bos => 0,
    }
}

fn main() {
    let l = Dugum(1, Box::new(Dugum(2, Box::new(Dugum(3, Box::new(Bos))))));
    println!("{} {}", toplam(&l), uzunluk(&l));
}

Test yourself

Which type best fits the children of a recursive tree node?
- &Node always
- [Node; 2]
- Vec<Node> or Option<Box<Node>>
- Node (directly)
Show answer

Vec<Node> or Option<Box<Node>> — Vec and Box both store on the heap and have a fixed size; Option expresses that leaf nodes have no children.

Indirect field

enum Liste {
    Dugum(i32, ____),
    Bos,
}

Show answer

enum Liste {
    Dugum(i32, Box<Liste>),
    Bos,
}

Definition and result

Dugum(i32, Liste)

E0072
Dugum(i32, Box<Liste>)

Valid
toplam(1→2→3)

6
uzunluk(1→2→3)

3

Next lesson: Deref

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies