recursion

递归

在 Rust 中，递归类型指的是一个类型的定义中直接或间接地引用了自身。这样的定义在许多数据结构，如树和链表中是很常见的。

但在 Rust 中，由于所有权和生命周期的规则，直接定义递归类型需要一些额外的注意。

链表

链表是一个常见的递归数据结构。考虑以下简单的单向链表定义：

enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

这是一个泛型枚举 List<T>，它有两个变体：Cons 和 Nil。

Cons 变体：

Cons(T, Box<List<T>>)

这个变体代表链表中的一个节点。它有两部分：

T: 这是链表节点存储的实际数据的类型。
Box<List<T>>: 这是一个指向链表中的下一个节点的指针。

在这里，使用 Box 是为了使递归数据结构在 Rust 中工作。由于 Rust 的所有数据类型都必须有一个已知的固定大小，我们不能直接在 Cons 变体中嵌套 List<T>，因为这会导致其大小无限制。使用 Box 解决了这个问题，因为 Box 是一个固定大小的堆分配指针。

Nil 变体：

Nil

这个变体代表链表的结束。当你到达链表的最后一个节点时，该节点的指针会指向 Nil。

总体分析：

这个 List 的定义表示一个单向链表，其中：

每个节点包含一个值和一个指向下一个节点的指针。
链表的结束由 Nil 表示。

例如，一个包含整数 1、2 和 3 的链表可以表示为：

Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil))))))

这种表示方法非常简洁，并完全利用了 Rust 的类型系统和所有权模型来创建一个安全、高效的链表实现。

单向链表

单向链表中的每个节点都有一个值和一个指向下一个节点的指针。这里是一个简单的单向链表实现：

enum Node<T> {
    Cons(T, Box<Node<T>>),
    Nil,
}

struct LinkedList<T> {
    head: Node<T>,
}

在这个定义中：

Node 是一个枚举，有两个变体：Cons 和 Nil。 Cons 变体包含一个值和一个指向下一个节点的 Box<Node< T>>。使用 Box 是因为 Rust 的类型需要一个固定的大小，而 Box 提供了一个固定大小的指针，实际数据存储在堆上。

一般来说，这个代码在上面那一部分结束之后就算是链表结束了，但是为什么我们还要写后面的那一堆东西呢？那一堆东西是干什么的？

通常我们还会添加一个 struct（如 LinkedList<T>）来表示整个链表，主要有以下几个原因：

更清晰的语义有了 LinkedList 这样的结构体，我们可以更清晰地表示这是一个链表的开始（或头部）。这样，当我们看到 LinkedList 类型时，就能立刻知道这是整个链表，而不仅仅是其中的一个节点。
扩展性使用 struct 表示整个链表可以让我们在未来更容易地添加更多的字段或方法。例如，我们可能希望在 LinkedList 结构体中添加一个 tail 字段来快速访问链表的尾部，或者添加一个 length 字段来存储链表的长度。
方法的实现在 Rust 中，我们可以为 struct 实现方法。通过这种方式，我们可以为 LinkedList 实现一些常见的链表操作，如 append, pop, push 等。

例如：

impl<T> LinkedList<T> {
    fn new() -> Self {
        LinkedList { head: Nil }
    }  
// 其他方法...
}

尽管 enum Node<T> { Cons(T, Box<Node<T>>), Nil } 本身就是一个链表的定义，但使用额外的 struct 来表示整个链表可以为我们提供更多的灵活性、清晰性和扩展性。

双向链表

双向链表与单向链表类似，但每个节点还有一个指向前一个节点的指针。这使得从链表的任何位置开始向前遍历成为可能。

struct DoubleNode<T> {
    value: T,
    next: Option<Box<DoubleNode<T>>>,
    prev: Option<*mut DoubleNode<T>>,  // 使用裸指针，因为 Rust 不允许双向所有权
}

struct DoublyLinkedList<T> {
    head: Option<Box<DoubleNode<T>>>,
    tail: Option<*mut DoubleNode<T>>,
}

使用链表

链表是动态数据结构，它在插入和删除时很有用，因为这些操作通常是 O(1) 的。但在查找和随机访问时，它们比数组和向量慢，因为这些操作是 O(n) 的。

Rust 标准库的 LinkedList Rust 的标准库提供了一个现成的 LinkedList 实现，它是一个双向链表。你可以使用 std::collections::LinkedList 而不是自己实现。

Box介绍

在 Rust 中，Box<T> 是一个非常重要的类型，它代表一个在堆上分配的值。以下是有关 Box<T> 的详细介绍：

基本概念

堆分配：Rust 中的默认行为是在栈上分配数据。栈上的数据有固定的大小，生命周期短，且在其作用域结束时自动清理。然而，有时我们需要在堆上分配数据，这样的数据可以在运行时动态地改变大小，并且其生命周期不受作用域的限制。
Box：Box<T> 是一个智能指针，它指向堆上分配的 T 类型的数据。当 Box 离开作用域时，它的析构函数会被调用，从而释放堆上的数据，确保没有内存泄漏。

当 Box<T> 离开其作用域时，以下操作会发生：

Box<T> 的 drop 方法被调用。 该方法会释放 Box 指向的堆内存。 如果 T 也实现了 Drop trait，那么 T 的 drop 方法也会被调用，确保任何需要的清理操作都已完成。

用途

递归类型：由于 Rust 需要知道每种类型的确切大小，因此直接定义递归类型（例如链表和树）是不可能的。使用 Box 可以解决这个问题，因为 Box 的大小是固定的，不管它指向的数据有多大。
```
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}
```
大型数据：如果数据非常大，而你不希望它占用栈空间，你可以使用 Box 将它移动到堆上。
所有权转移：Box 可以用来表示一个数据的唯一所有权，并将这个所有权转移到其他函数或线程。

使用

创建一个 Box：

let b = Box::new(5);  // b 的类型是 Box<i32>

解引用：

解引用是一个操作，它允许你访问指针或引用所指向的真实数据。在编程中，当我们使用指针或引用来指向某个数据时，有时我们需要直接操作或访问这个数据，而不是操作指针或引用本身。这就需要用到解引用。

由于 Box<T> 实现了 Deref trait，你可以使用 * 运算符来访问其内部的数据：

let b = Box::new(5);
assert_eq!(*b, 5);

性能

运行时成本：虽然 Box 本身的开销很小，但在堆上分配和释放数据会有一些运行时成本。因此，对于小型数据或短暂存在的数据，通常更倾向于在栈上分配。
空间开销：Box 本身只是一个指针的大小，但它指向的数据是在堆上分配的，所以实际的空间使用量取决于数据的大小。

总结

Box<T> 在 Rust 中是一个非常有用的工具，允许开发者在堆上分配数据，并为其提供自动的内存管理。它在处理大型数据、递归数据结构或需要转移所有权的情况下特别有用。

方法

在 Rust 中，方法是定义在某种数据结构上的函数，通常这些数据结构是结构体 (struct)、枚举 (enum) 或特性 (trait)。方法与普通函数的区别在于，方法始终与某个数据类型相关联，并且在其签名中有一个额外的第一个参数，通常是 self，代表其调用者。

定义和调用方法：方法定义在 impl 块中，这个块为一个特定的数据类型提供方法实现。

例如，定义一个 Rectangle 结构体和一个方法来计算其面积：

struct Rectangle {
    width: u32,
    height: u32,
}

impl Rectangle {
    fn area(&self) -> u32 {
        self.width * self.height
    }
}

// 使用方法
let rect = Rectangle { width: 30, height: 50 };
println!("The area of the rectangle is {} square pixels.", rect.area());

在上述示例中：

area 方法定义在 Rectangle 结构体的 impl 块中。该方法接受一个名为 self 的参数，它是一个 &Rectangle 类型的引用，表示方法的调用者。调用方法时，使用 . 符号，如 rect.area()。

方法和所有权

self 参数的几种形式：

引用 (&self): 这是只读方法，不会修改调用者。可变引用 (&mut self): 这允许方法修改其调用者。所有权 (self): 这允许方法消费或转移调用者的所有权。关联函数：除了方法，impl 块还可以包含不取 self 为参数的函数，这些函数被称为关联函数。最常见的关联函数是 new，用于创建结构体的新实例。

impl Rectangle {
    fn square(size: u32) -> Rectangle {
        Rectangle { width: size, height: size }
    }
}
let sq = Rectangle::square(20);

在这个例子中，square 是一个关联函数，用于创建一个正方形 Rectangle。

关联函数

关联函数是定义在结构体、枚举或特性的 impl 块中的函数，但它们不接受 self 作为参数。

因为它们不作用于一个实例，所以它们也被称为“静态方法”或“类方法”。

关联函数通常用于：

创建和返回一个新的实例，例如构造函数。
提供不需要访问特定实例的功能。

示例：

考虑一个 Rectangle 结构体，我们可以有一个关联函数来创建一个正方形，因为正方形是一个特殊的矩形，其中宽度和高度是相等的。

struct Rectangle {
    width: u32,
    height: u32,
}

impl Rectangle {
    // 关联函数
    fn square(size: u32) -> Rectangle {
        Rectangle { width: size, height: size }
    }
}

// 使用关联函数
let sq = Rectangle::square(10);

在这个例子中，square 是一个关联函数，它接受一个 u32 参数并返回一个 Rectangle 实例。注意我们是如何使用 :: 而不是 . 来调用关联函数的。这是因为它不是在一个 Rectangle 实例上调用的，而是直接在 Rectangle 类型上调用的。

recursion ​

recursion