Can every recursive process be transformed into an iterative process?

Question

I was reading the book, Structure and Interpretation of Computer Programs, where in it tells about the distinction between a recursive procedure and recursive process, and similarly between iterative procedure and iterative process. So, a recursive procedure could still generate an iterative process.

My question is: given a procedure which generates a recursive process, can you always write another procedure that achieves the same result but generates an iterative process?

The specific problem that I was trying to solve was to write a procedure which does an in-order traversal of a binary search tree but generates an iterative process. I know how you can use a stack to get an iterative procedure for this problem. However, that still generates a recursive process (correct me if I am wrong here).

Thanks,
Abhinav.

Answer 1

Some tasks are truly impossible to solve with linear iterative processes (e.g. tree recursion, which is impossible to convert to tail recursion). You either have to use the stack built into your platform, or re-create it yourself within the language (usually a much less efficient and uglier solution). So if you define 'recursion' as 'using a stack to store different invocations of the same code', then yes, recursion sometimes is absolutely required.

If you define 'recursion' as 'a function in my language (eventually) calling itself', then you can get by without explicit recursion by re-implementing recursiveness yourself, as describes above. This is only useful if your language doesn't provide recursive procedures, or not enough stack space, or has similar limitations. (For instance, early Fortran's didn't have recursive procedures. Of course, they also didn't have the dynamic data structures that you would need to simulate them! Personally, I have never come across an actual example where implementing pseudo-recursion was the right solution.)

Answer 2

Read this former SO post:

Design patterns for converting recursive algorithms to iterative ones

there are a lot of good answers there which may help you further.

Answer 3

Any tail recursive process can be transformed into an iterative one.

But not all recursive processes can be transformed into an iterative one.