Aladdin
There is a Bollywood version Aladdin and Sinbad. In it, both characters meet and participate in the adventures of each other. The djinn is female. In the end Aladdin marries her (rather than the princess).