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