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.

  • 2
    $\begingroup$ You seem to be mixing syntactic and semantic notions. Maybe use "inductive" for "semantic recursion" and let "recursion" be a syntactic term? $\endgroup$ – Raphael Sep 14 '17 at 6:20
  • 1
    $\begingroup$ I don't think there is a really sharp definition for these. One can remove any recursion using an explicitly programmed "call stack", as you say, but it's hardly iterative and non-recursive now. Apart from the extreme cases (explicit recursion vs plain loops with no "call stack" around) there can be a grey area in the middle (some queue/stack is used and the algorithm loops until it's emptied). $\endgroup$ – chi Sep 14 '17 at 8:09
  • $\begingroup$ This question is unanswerable since it is opinion based. $\endgroup$ – fade2black Sep 14 '17 at 13:42
  • 1
    $\begingroup$ I'm pretty sure these terms have well defined meanings in theoretical CS. I'm tending to see it as @chi does, but I'm interested in a little more formal info on the subject. $\endgroup$ – John Doe the Righteous Sep 14 '17 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.