递归排列，Ellis Horowitz算法和数据结构混淆

Question

我是大学一年级的初级程序员。我的导师让我们做一些递归算法的研究，并使其无递归。不管我怎么努力，似乎都不可能。问题是

A是一个字符串(例如A = "hello")和交换，即一个抽象，用A的第i个字符交换第k个字符，例如，CALL交换("hello"， 2,3)将把"hello"更改为"hlelo")。

这个想法是打印出所有可能的排列c++中的版本为

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

我的导师更喜欢使用一种叫做ADL的语言，这种语言似乎只出现在Horowitz的书"算法和数据结构"中。他在ADL中提出了这个问题，所以我也会添加那个代码，它很容易理解。

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

感谢任何可以帮助我的人。Martyn

Answer 1

递归算法就是使用堆栈的算法。

递归允许您使用调用堆栈作为数据堆栈。

任何采用这种形式的递归函数

void perm(char*a, const int k, const int n)
{
   // check if your code should return
   // make a recursive call with new data
}

可以改成:

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

这里有一个提示，没有为你做功课。当你遍历字符串，看第i个字符时，你处于三种可能的状态之一:

• i == k
• i == n
其他

你在这三种情况下分别打印什么?