> clone() makes an immutable, deep copy/recursive copy of the original data structure.

No. clone() calls std::clone::Clone::clone. For many std collections that means deep/recursive copy.

For custom data structures, it can mean anything. It depends entirely on your implementation of the Clone trait.