The sender must have an SPF record specifying all the sending services that they use. The receiver does not need to have an SPF record as such in order for it work. The receiver must be doing SPF validation on the emails coming in so that they can check if the email coming from you is authorized or not.
You can see this article, where I have explained all you need to know about SPF, DKIM and DMARC.All you need to know about SPF, DKIM and DMARC
OnDMARC can help you with implementing SPF, DKIM and DMARC. DMARC - OnDMARC - Actively block phishing
You can also see the below article for more information on why SPF alone is not enough.
You can sign up for a 14 day free trial using the button below.