recursion ?

> You can translate recursive method into loop then it will be easy to calcuate Complexity .

> But some recursive method are really hard to translate to loop...

And some recursive methods (when 'translated to a loop') require an explicit stack when transmogified

into an iterative method. Most of the times the 'recursion vs iteration' dilemma can be solved after

analyzing the original recursive method --

- If the stack size is O(n), where n is the size of the problem, you're way better off implementing this

method iteratively. The factorial function and the fibonacci numbers come to mind. Those functions

don't even require an explicit stack when transformed to their iterative version.

- If the stack size is O(log(n)), where n is the size of the problem, you'd better leave the recursive method

alone as it is. Your iterative method requires an explicit stack; a simple recursive function call is often way

faster than clumsy push/pop/test-what-to-do operations. Tree searching functions come to mind. Partial

tail recursion can often be removed and changed into some 'while' form construct.

- If the stack size is O(2^n) (or worse) you're in deep trouble, no matter what you do. These are the

hard functions. The Ackermann function comes to mind -- int Ack(int x, int y) {

if (x == 0) return y+1;

if (y == 0) return Ack(x-1, 1);

return Ack(x-1, Ack(x, y-1));

}

Creatures like this don't deserve to be calculated by computers, recursively or not; you're simply

out of luck when you bump into one of these.

kind regards,

Jos

JosHorsmeiera at 2007-7-16 1:39:10 >