Most of us know the typical answer to this question: if a function calls itself, it's recursion, if it's a loop, it's iteration. We also know that recursion can be simulated using iteration (by manually unrolling the call stack) and iteration can be turned into recursion.
Yet there's something about this that keeps bugging me. Suppose we have a recursive algorithm that we unroll, so it does not use our favourite language's function call operator on itself anymore. Has this really become an iterative algorithm though? Would this mean in a language that has no concept of functions (most assembly languages go here) we cannot have a recursive algorithm? Graph travelsals and some numerical algorithms are often recursive in nature: we start a computation for some input, discover we can't finish it without doing the same computation on some other input, so we put it aside, start working on something else and then later come back and finish the job. To me, "iterativizing" these algorithms still leave the algorithms themselves recursive, just making the implementation iterative.
Just like if we're trying to compute some numerical sequence that has a nice iterative algorithm (think sum of first $n$ numbers and similar), putting tailcalls where the loop would restart doesn't really feel like we've made the algorithm itself recursive.
To me recursive/iterative has more to do with whether we start at the root or the leaves of a computational dependency graph (in which a problem instance has an edge leading to another if the former is dependent on the result of the latter).
Could anyone shed some light on the theoretic background of this matter please? What do these terms really mean? It would be greatly appreciated.
