I think the prevalence of recursion might be attributable to mathematics. A lot of mathematical analysis of algorithms is more natural to express in terms of re

I think the prevalence of recursion might be attributable to mathematics. A lot of mathematical analysis of algorithms is more natural to express in terms of recursion (partially because of proof by induction), so you often see algorithms stated that way. It's also worth noting that there are plenty of instances where (IMO), recursion is much more natural. For example, traversing trees recursively. I agree, though, there should definitely be more time spent teaching how to convert between the two.