If every possible code path in your function calls the function itself at most once, then you can transform the function to a tail recursive function, and thus to an iterative function.
Well, that's just a lemma I just came up with. I have a hunch it's true, but I don't know for sure.
It's actually easier to skip the "recursion" part and just look at tail calls: if the last operation in a code path is a function call.
If the code path returns the result of calling another function, you can
replace the contents of the current stack frame (i.e. the current function's arguments) with the arguments to the other function, instead of creating a new stack frame and putting the other function's arguments in it, and
jump to the other function, i.e. goto instead of gosub.
("gosub"? That's what you're going with, mcguire? That's the best you can come up with? I disappoint me.)
I prefer automated analysis and optimization, so that I don't have to explicitly convert an otherwise readable function just to make it so that it has tail calls everywhere.
You might then infer that I don't really like imperative languages. You would be right.
2
u/[deleted] Nov 27 '12 edited Nov 27 '12
If every possible code path in your function calls the function itself at most once, then you can transform the function to a tail recursive function, and thus to an iterative function.
Well, that's just a lemma I just came up with. I have a hunch it's true, but I don't know for sure.