3

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.

abhinav
  • 221
  • 1
  • 3
  • 13

3 Answers3

4

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.)

Kilian Foth
  • 13,904
  • 5
  • 39
  • 57
  • 1
    Thanks for the explanation. I think what you meant to say was that not all tree recursions can be converted to tail recursions :) SICP demonstrates how to obtain an iterative process (using tail recursion) for computing Fibonacci numbers. – abhinav Aug 18 '11 at 12:01
  • 3
    Sure, but that's only possible because the left and right branches of the naive approach are self-similar. That allows you to use a linear recurrence - in fact, it allows an O(1) solution! In other words, the original definition isn't the right way to solve the problem in the first place. Unfortunately, almost every introductory text uses Fibonacci numbers as its example for tree recursion, although that concept really is a very, very bad example. – Kilian Foth Aug 18 '11 at 12:08
  • 1
    @KilianFoth why do you say tree recursion cannot be made into an iterative (tail-recursive) process? It's just a matter of sequencing the nodes in the correct order. Continuation-passing style makes light work of the problem – https://stackoverflow.com/q/19070577/633183 – Mulan Feb 03 '18 at 01:33
3

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.

Community
  • 1
  • 1
Doc Brown
  • 19,739
  • 7
  • 52
  • 88
3

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

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

leppie
  • 115,091
  • 17
  • 196
  • 297
  • Can you explain what a tail recursive process is and what are the other categories of recursive processes? Or give a pointer? TIA – Serge Wautier Aug 18 '11 at 11:57
  • Thanks for the clarification. Can you provide a reference as to where I can read on why all recursive processes cannot be transformed into an iterative one? – abhinav Aug 18 '11 at 12:03
  • @abhinav: A depth first tree traversal is an example that is hard or impossible to write iteratively. – leppie Aug 18 '11 at 12:06