I am new to this site and this question is certainly not research level - but oh well. I have a little background in software engineering and almost none in CSTheory, but I find it attractive. To make a long story short, I would like a more detailed answer to the following if this question is acceptable on this site.So, I know that every recursive program has an iterative analog and I kind of understand the popular explanation that is offered for it by maintaining something similar to the system stack and pushing environment settings like return address etc. I find this kind of handwavy. Being a little more concrete, I would like to (formally) see how does one prove this statement in cases where you have a function invoking chain $F_0 \rightarrow F_1 \ldots F_i \rightarrow F_{i+1} \ldots F_n \rightarrow F_0$. Further, what if there are some conditional statements which might lead an $F_i$ make a call to some $F_j$? That is, the potential function call graph has some strongly connected components.I would like to know how can these situations be handled by let us say some recursive to iterative converter. And is the handwavy description I referred to earlier, really enough for this problem? I mean then why is it that I find removing recursion in some cases easy. In particular removing recursion from pre-order traversal of a Binary tree is really easy - its a standard interview question but removing recursion in case of post order has always been a nightmare for me. What I am really asking is $2$ questions(1) Is there really a more formal (convincing?) proof that recursion can be converted to iteration?(2) If this theory is really out there, then why is it that I find, for eg, iteratizing preorder easier and postorder so hard? (other than my limited intelligence)
Removing recursion - a look into theory behind the scenes
pl.programming languages;recursion;recursive
If I understand correctly, you are clear about converting functions that contain no other function calls but to themselves.So assume we have a call chain $F \to F_1 \to \dots \to F_n \to F$. If we furthermore assume that $F_1, \dots, F_n$ are not recursive themselves (because we have converted them already), we can inline all those calls into the definition of $F$ which thusly becomes a directly recursive function we can already deal with.This fails if some $F_j$ has itself a recursive call chain in which $F$ occurs, i.e. $F_j \to \dots \to F \to \dots \to F_j$. In this case, we have mutual recursion which requires another trick to get rid off. The idea is to compute both functions simultaneously. For example, in the trivial case:f(0) = af(n) = f'(g(n-1))g(0) = bg(n) = g'(f(n-1))with f' and g' non-recursive functions (or at least independent of f and g) becomesh(0) = (a,b)h(n) = let (f,g) = h(n-1) in (f'(g), g'(f)) endf(n) = let (f, _) = h(n) in f endg(n) = let (_, g) = h(n) in g endThis naturally extends to more functions involved and more complicated functions.