1

好吧，递归对我来说总是很麻烦。

谁能解释一下递归在计算给定字符串排列的函数中是如何工作的。

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
}

当有 2 个递归调用后跟一个语句时，递归如何工作？我希望我很清楚。

谢谢。

4

1 回答 1

1

尝试用英文读出代码；

该函数生成从第 i 个元素开始到第 n 个元素结束的字符串 a 的排列。

如果 i 和 n 相等，我们就完成了，只有一个元素和一个排列。

否则;

对于 i 和 n 之间的每个 j，包括两端。： -交换第 i 个元素和第 j 个元素的位置。- 生成所有不会更改为前 i 个元素的顺序的排列。- 再次交换第 i 个和第 j 个元素。

递归调用在循环中的事实意味着它将被执行多次。- 字符串的每个潜在第一个字符一次。

以上在具体示例中的含义是该算法将对字符串“1234”执行；

首先生成以“1”开头的字符串，然后是“234”的所有排列，即“1234”的所有排列恰好以“1”开头。

然后生成以“2”开头的所有排列。

然后一切以“3”开头。

最后是所有以“4”开头的排列。

由于“1234”的所有排列都以“1”、“2”、“3”或“4”开头，这将生成字符串“1234”的所有排列。

证明这项工作可以通过归纳来完成，并且“留给读者作为练习”。

于 2013-08-29T11:15:37.640 回答