Recursive Permutation, Ellis Horowitz Algorithms and data structure Confusion.

Question

I am a beginner programmer in my first year of university. My tutor has asked us to do some research on a recursive algorithm and make it none recursive. No natter how much I try it seems impossible. The question reads

A is a character string (e.g. A = "hello") and interchange, which is an abstraction, exchanges the k-th with the i-th character of A, e.g. CALL interchange("hello", 2, 3) would change "hello" to "hlelo").

The idea is to print out all the possible permutations The version in c++ reads

void perm(char*a, const int k, const int n)
{
  if(k==n)
  {
    cout << a;
  }
  else
  {
    for (i=k;i<=n;i++)
    {
      interchange(a, k, i);
      perm(a, k+1, n)
    }
  }
 }

My tutor much prefers to use a language called ADL that seems only to appear in the Horowitz book "algorithms and data structures". He has posed the question in ADL so I will add that code in too, its very easy to understand.

proc perm(IN a, IN k, IN n)
  if k=n then
    print(a)
  else
    {
     for i <- k to n do
       call interchange(a,k,i)
       call perm( a, k+1, n)
     end
    }
end

thanks for anyone who can help. Martyn

Answer 1

A recursive algorithm is simply an algorithm that uses a stack.

The recursion allows you to use the call stack as your data stack.

Any recursive function taking this form:

void perm(char*a, const int k, const int n)
{
   // check if your code should return

   // make a recursive call with new data
}

Can be changed to this:

void perm(char*a, const int k, const int n)
{
   // Create a stack, push (a,k,n)

   while ( /* stack isn't empty */ )
   {
       // check if stack should be *popped* (instead of returning)

       // Put new data on the stack (instead of recursing)
   }
}

Answer 2

Here's a hint, without doing your homework for you. As you walk down the string, looking at the ith character, you're in one of three possible states:

• i == k
• i == n
• else

What do you print in each of those three cases?