A la respuesta de por qué pasa eso, ya te ha respondido Candid Moe en los comentarios. En cuanto a hacer más rápida la función recursiva, puedes hacerlo así:
def fibonacci(n, a=0, b=1):
while n!=0:
return fibonacci(n-1, b, a + b)
return a