4

Is every recursive function convertible to iteration? What characteristic should a recursive function have in order for it to be implemented using iteration?

I've been trying to define the following function using iteration but seems like a no-go! It is supposed to explore all the paths (nodes) in a maze. Can anyone rewrite this using iterations? If it is not possible, why not?

typedef int[0,99] id_t;
bool visited[id_t];
int path[id_t];
int pathCounter = 0;

struct { 
    id_t id;
    bool free;
    int neighborNode[4];
} nodeMap[id_t];

void findPath(int current){
    visited[current] = true;
    for (i : int[0, 3]){
        if(nodeMap[nodeMap[current].neighborNode[i]].free == true && visited[nodeMap[current].neighborNode[i]] == false && nodeMap[current].neighborNode[i] != -1){
        path[pathCounter] = nodeMap[nodeMap[current].neighborNode[i]].id;
        pathCounter++;
        findPath(nodeMap[current].neighborNode[i]);
        path[pathCounter] = nodeMap[current].id;
        pathCounter++;      
        }
    }
    path[0] = current;
}

Extension: Is it possible to convert the mentioned recursive function to iteration without implementing my own stack? One of the answers suggested that every tail recursive function can be converted to iteration without using a stack structure...if that's so, is every recursive function convertible to tail recursion? How?

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Saba Ahang
  • 578
  • 9
  • 24
  • See also Wikipedia on [Recursion vs Iteration](http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursion_versus_iteration). – Jonathan Leffler Jan 20 '17 at 00:30
  • Possible duplicate of [Can every recursion be converted into iteration?](https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration) – thepurpleowl Sep 25 '19 at 12:37

5 Answers5

7

Yes, every recursive function can be converted to an iterative one by following a rather mechanical process.

Recall that compilers implement recursion by using a stack, which is typically implemented in the CPU's hardware. You can build a software stack of your own, make it suitable for keeping the state of your function (i.e. its local variables), push the initial state onto that stack, and write a while loop that pushes new state onto the stack instead of making a recursive call, popping the stack instead of returning, and continuing the process while the stack is not empty.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • I kinda prefer not to implement my own stack, is it still possible to convert my function to an iteration? – Saba Ahang Jul 29 '12 at 12:47
  • @SabaAhang It is possible to rewrite recursion without a stack if it is a *tail call* (modern compilers do this as an optimization). In case of your specific issue, the stack is simply an array of `int`s and a scalar `int` representing the "stack pointer", so implementing your stack is very easy. – Sergey Kalinichenko Jul 29 '12 at 12:52
  • There are actually 2 numbers that need to be stored: current and i. – nhahtdh Jul 29 '12 at 18:29
5

It is generally possible to convert any recursive algorithm into loop. The method is simple: we can imitate how the compiler generate code for function call: entering function, returning from function, and continue execution.

To turn a recursive function into an iterative loop, you can:

  • Define a record, which stores the arguments to the function and the local variables. This is equivalent to stack frame.
  • Define a stack, to which records a pushed. This is analogy to the program stack.
  • When a function is called, create a record of the current value of the arguments and local variables and push to stack.
  • When you return from the function, pop out from stack and overwrite the current value with that from the record.

The whole process above is done in a while loop, which will exit when the stack is empty,

nhahtdh
  • 55,989
  • 15
  • 126
  • 162
3

Like the other answers already stated, it's technically possible to do that with simulating the stack. But I guess you don't want to do that. You probably want an iterative solution without using a stack. If that's the case you need to have a tail recursive function. AFAIR that's the only possible way. You can rewrite every tail recursive function to an imperative one without simulating a stack.

duedl0r
  • 9,289
  • 3
  • 30
  • 45
  • Exactly! Can you tell me more about how to convert my function to a tail recursion so later I can rewrite it using iteration? Is it possible to convert any recursion to tail recursion? – Saba Ahang Jul 29 '12 at 12:38
  • You can't convert every recursive function to a tail recursive function. Maybe it's possible with your function, I'm not sure yet ;) – duedl0r Jul 29 '12 at 12:45
  • 1
    The function is tree recursive, so I think that pretty much rules out being able to transform it to use tail recursion without using an auxiliary data structure. – jamesdlin Jul 29 '12 at 12:58
0

If you have a simple "tail" recursion, then you can use a loop instead (e.g. factorial function). In more complex functions, you have to use a stack structure and a while (!stack.empty()) loop. However, if you have quite complex recursion, such as Towers of Hanoi, Merge Sort, and printing truth table, you will have to use a stack with while loop, as previous, but with a switch statement to determine the current status of call.

Recursive:

void mergeSort(int start, int end)
{
    if (start < end)
    {
         mergeSort(start, (start + end) / 2);
         mergeSort((start + end) / 2 + 1, end);
         Merge(start, end);
    }

}

Iterative:

void mergeSort()
{
  stack<int> st;
  st.push(1);
  int status;

  while (!st.empty())
  {
      status = st.pop();
      switch (status)
      {
        case 1:
             ....
            break;
        case 2:
             break;
      }
  }
}

I highly recommend this excellent pdf which explains the process in detail.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • How about the function in question? Is it a case of tail recursion? if not is it convertible to a tail recursion? How? – Saba Ahang Jul 29 '12 at 12:45
  • 1
    @SabaAhang It is not quite complex neither tail. It can be implemented using a stack. The `pdf` I provided is very good. You can learn from it how to implement it using stack –  Jul 29 '12 at 12:47
-3

According to http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursion_versus_iteration all recursively defined functions can be converted to iterative ones.

Colin 't Hart
  • 7,372
  • 3
  • 28
  • 51