通过数组全排列思考递归

数组全排列算法思考——递归

递归原理思考

递归原理就是：

要解决该问题 等价于 解决一个简单操作+一个规模比本问题小的同样类型的问题。这里解决规模比自己小的问题的解决方法就是通过调用自己，传递一个该小规模尺寸的参数，来解决 。

这样不断把该类问题的规模减小，直到能够一步解决为止，此时问题解决

即 结构：

fun(N)
{
    if(N==0) // 问题规模小，能够一步解决
    {
        简单操作A;
        return;
    }
    
    附加操作a;// 这里的附加操作可以是循环调用func(N)，比如func(N i)  i=1....m
    fun(N-1);
    return;
}

结果输出操作：

​ 结果输出可能会在三个地方输出

1. 一个是在问题规模最小，简单操作A之后输出，此时表示 该结果（就像全排列一样，会有很多个结果） 已经解决完毕，开始输出
2. 在调用过程中即，func(N-1) 附近进行输出，eg. 二叉树的递归遍历 此时等价于解决问题的过程中打点（遍历就是每走到一个地方之后打点，标记按照这个流程，走到这里了）
3. 还有就是调用func(N)后，通过返回值，或者引用形参，获得结果之后的输出（这时只有一个结果）

数组全排列算法：

我这里简单提一下思路

目的： 全排列一个长度为N的数组 等价于 将N个元素轮流放到第一个位置上，每放定一个元素之后全排列后面的长度为N-1的数组。

输出：每组全排列完毕之后输出，在最小规模的数组全排列完毕之后代表每组全排列完毕

代码实现：https://blog.csdn.net/MsStrbig/article/details/79823555