问快速概括(可能是建模/提取/总结)思维模式的递归部分

EN

用于生成长度为N的字符串的所有排列的井

• 你需要N个嵌套的

循环，它将通过字母表生成所有的可能性。你可以把它看作是一个数字的增量，但是你有

• ，而不是数字，所以3个字符的小写字母不带标点符号，看起来像这样：

const int N=3；//目标单词大小字符wN+1；//生成的单词int i；wN=0；//单词结束i=0；for (wi='a';wi<='z';wi++){ i++；for (wi='a';wi<='z';wi++){ i++；for (wi='a';wi<='z';wi++){ //此处w[]包含生成的单词，因此请使用它执行一些操作}i--；}i--；}正如你所看到的，

• 很简单，它是硬编码的，以匹配N=3，并且不能在runtime

• unless期间改变。你使用的是自变代码...

从迭代到递归的移植

循环递归参数就像for循环中的索引，它必须降低其函数大小，所以它会在有限时间内停止，并且递归必须包含某种停止condition

• the N个字符的单词生成可以重写as

• genere_word(N)=genere_word(N-1)+generate_char();

• so您可以编写生成所有1个字符的函数，然后使用递归可以实现N个字符的单词

• <

>H135递归尾部(操作数)可以是实际生成的单词w

• 和递归层(实际生成的字符位置i)

• of code i character generation不会更改i-1字符或任何以前的

• ，因此我们不需要在堆栈上抛出w，并且可以将其保留为指针或全局变量

• ，因此我们实际上只需要将<

• >d49w>作为如下代码：

char w1024={0}；//足够大的buffer void _generate(int i) //递归调用{ // stop conditions if (i==0) for (wi='a';wi<='z';wi++) //如果第一个字符是完整的，则单词是完整的，因此没有递归{ //此处w[]包含生成的单词，因此使用它做一些事情} else for (wi='a';wi<='z'；wi++) //否则{ //并非所有字符都是genered，因此递归地生成下一个_generate(i-1)；}} void generate(int N) // main call { //这里可以动态创建wN+1，如果(N< 0) N= 0；//避免无效N if (N>=1024) N=1023上的访问冲突；//避免无效N wN=0上的访问冲突；// end of word if (N) _generate(N-1)；//仅当至少有一个字符时才生成... }

备注

C++

• iteration中的所有代码通常会更快，因为如果编码得当，没有堆垃圾

• 例如，N=3上的这两个示例迭代花费了2.2秒和递归2.3秒在我的设置

• 上花费了如此长的时间，因为我将每个单词逐个添加到VCL TMemo。

• 如果我自己在内存中创建列表并复制整个代码，则速度会快得多(68ms )

<代码>H165我可以从头到尾生成字符，但为此您还需要知道<代码>D66

• ，因此您将需要i,N作为尾部，这将是尽可能小的递归尾部...

• 一些语言/解释器/编译器针对递归进行了优化，在这种情况下，递归比迭代更快。

• 在这种情况下，上面的说明不会应用

• btw如果足够聪明，那么您甚至可以在tail中删除D78i,N>，并将其用作全局变量，如w

• 在这种情况下，您必须确保在从_generate返回之前设置i对于入口点的值，

• 如下所示：

//--------------------------------------------------------------------------- int i；char w1024={0}；//--------------------------------------------------------------------------- _generate() { if (i==0) for (wi='a';wi<='z'；wi++) { //此处w[]包含生成的单词，因此请对其执行操作} else for (wi='a';wi<='z';wi++) { i--；_generate()；i++；}} void generate(int N) { if (N< 0) N= 0；if (N>=1024) N=1023；wN=0；i=N-1；if (N) _generate()；} //---------------------------------------------------------------------------

• beware这是O(26^N)的复杂性，这是巨大的

• ，所以如果N>4和糟糕的编码，你可以等待很长一段时间，直到结束...