Box and recursion
- Rust course
- Intermediate
- Lesson 33/115
- 4 min
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.
Practice 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.
Starter code
fn main() {
// buraya yaz
}Sample 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));
}Expected output
6 3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Which type best fits the children of a recursive tree node?
- &Node always
- [Node; 2]
- Vec<Node> or Option<Box<Node>> Correct answer
- Node (directly)
Explanation: Vec and Box both store on the heap and have a fixed size; Option expresses that leaf nodes have no children.
2 Indirect field
enum Liste {
Dugum(i32, ____),
Bos,
}enum Liste {
Dugum(i32, Box<Liste>),
Bos,
}Explanation: The Box pointer fixes the size of the recursive type.
3 Definition and result
| Term | Meaning |
|---|---|
Dugum(i32, Liste) |
E0072 |
Dugum(i32, Box<Liste>) |
Valid |
toplam(1→2→3) |
6 |
uzunluk(1→2→3) |
3 |