Seriously, Fibonacci and factorials where exactly what I was referring to when I was saying that "Most of the basic examples of recursion tend to be things which work better iteratively".

That recursive fibonacci implementation is horrible, too. It runs in, what, exponential time? It's exactly that kind of shit that nobody should teach, ever.