Is there a pattern for removing recursion?

I have an algorithm that works perfectly, but it uses recursion. I know there are patterns for just about everything, but I c开发者_如何学Could not find one for this case.

I just need some simple examples that show how to modify an algorithm, specifically the part where a method or function calls itself. I've seen iteration algorithms that do it with a while loop. So there must be a simple checklist to follow in order to convert an recursive algorithm into an iterational one.

You can definitely model recursion with iteration and a custom call stack. Since recursion is nothing but execution of same instructions in a new environment, you can model your own environment using a simple stack structure, and just wrap your algorithm in a loop, pushing your current mini-environment at the start of an iteration and popping it whenever you finish a loop iteration, or exit it prematurely via break or continue.

Tail-call recursion where the recursion happens as the end of a function is pretty trivial to make non-recursive with a loop. Some compilers even do that for you automatically.

Converting any recursive function into an iterative one in a systematic way isn't so simple and in all likelihood you'd end up creating your own call stack, which most likely defeats the purpose of having a non-recursive algorithm anyway.

Also see: Can every recursion be converted into iteration?

BTW, if you are using GCC or llvm, then your non-debug code with -O2 or -O3 turned on will perform tail recursion elimination for you. (In case you don't know, tail recursion is when the recursion call comes last thing in the function and is simply returned, i.e. not part of an expression. See http://en.wikipedia.org/wiki/Tail_call.)

So, if the recursive write up is clearer to read, it's probably better to stick with that.