第三章 栈和队列-递归输出n个数的全排列2019-02-27

         摘抄的递归漫谈中的两个段落，对于递归，自己真真的没有亲手做过，然后每次看稍微复杂一点的例子，都是二脸懵逼，这贼尴尬，不得已，还是继续查资料，做实验，争取递归这儿以后不拖自己的后腿。

         对于递归，最好的理解方式便是从函数的功能意义的层面来理解。了解一个问题如何被分解为它的子问题，这样对于递归函数代码也就理解了。这里有一个误区（我也曾深陷其中），就是通过分析堆栈，分析一个一个函数的调用过程、输出结果来分析递归的算法。这是十分要不得的，这样只会把自己弄晕，其实递归本质上也是函数的调用，调用的函数是自己或者不是自己其实没什么区别。在函数调用时总会把一些临时信息保存到堆栈，堆栈只是为了函数能正确的返回，仅此而已。我们只要知道递归会导致大量的函数调用，大量的堆栈操作就可以了。

        递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。

关于输出n个数的全排序的代码，总算是看懂想通了，下面是对例子的注释，明白了之后发现这玩意挺简单

// n是要全排序的数组 k表示n[]中的当前的最大的数组下标，n表示的是数组的长度

void CoutNum(int nData[],int k,int nNum)

{

if (k == 0)//这时候表示递归到这儿只剩下最后一个数了，这时候不需要再组合，作为输出，和某次递归的结束

{

for (int i=0; i<nNum; i++)

{

cout<<nData[i];

}

cout<<endl;

return;

}

int temp;

for (int i=0; i<=k; i++)

{

temp = nData[k]; // 数组中的最后一个数可以在任何一个位置，如123，在全排列中3可以在12中间的任意位置，共三种组合

nData[k] = nData[i];

nData[i]=temp;

CoutNum(nData,k-1,nNum);

temp = nData[k]; //一次递归完成后，交换回来，才能下一个位置与最后一个数进行交换

nData[k] = nData[i];

nData[i]=temp;

}

}