I assume total time for both recursive and non recursive is less.
Then problem is not in database. Ask them is it also connecting to some other server except this D/B?

BTW u traced for how long? if it's for a small time increase trace time and see what u got.