So this is a part computer science, part math question, but as I am more curious about this from a mathematical perspective. I know from Comp. Sci. classes the following theorem (roughly);
Theorem: Any algorithm that can written recursively can also be written iteratively, possibly needing the assistance of a supplementary data structure.
While this makes sense, I was wondering how a mathematician might prove this? How do we state this as a problem in pure math, and how would one go about proving the statement?