[throwaway2245]

>if I listen to songs on Spotify, are they supposed to somehow not store it, but still give me recommendations?

This is perfectly possible.

In your example, Spotify could store the data they needed for their recommendation algorithm in aggregate form so that any link to a person was destroyed and not reversible.

And then make recommendations by running that algorithm on your locally/privately stored data, with no loss of functionality.

As such, a recommendation algorithm does not technically benefit from storing your personal data, at all.