Teachers/writers don't like being rushed since they are overloaded with other letters and work related stuff. I gave my professors over 5 months to write them and I gave them a deadline and year I was applying (they turned it in within a month or two). I asked them right after the semester ended so they'd have a fresh perspective of me as a student and that also helps them not forget who you were. So the earlier the better in my opinion.