Question

c语言全排列递归问题

#include<stdio.h>
int A[100];
// 输出1～n的全排列的递归函数
void print_permutation(int n, int* A, int cur) {
int i, j;
if(cur == n) { // 递归边界
for(i = 0; i < n; i++) printf("%d ", A[i]);
printf("\n");
}
else for(i = 1; i <= n; i++) { // 尝试在A[cur]中填各种整数i
int ok = 1;
for(j = 0; j < cur; j++)
if(A[j] == i) ok = 0; // 如果i已经在A[0]～A[cur-1]出现过，则不能再选
if(ok) {
A[cur] = i;
print_permutation(n, A, cur+1); // 递归调用
}
}
}

int main() {
print_permutation(4, A, 0);
return 0;
}
这道题递归是怎么实现的？我尝试自己手算了好多遍，都是只能输出1,2,3,4啊。。。我理解的是每递归一次cur就+1，到等于4时就结束了，然后每次递归得出一个数，到最后不就是1,2,3,4吗？那些2，3，4开头的排列是怎么递归出的啊？求解！最好能说下每次递归得出什么，感激不尽！！！

Answer 1

你这个程序是对的啊。
你每次到4结束之后要返回到上一级调用，然后他们可能会执行下一个循环的。

追问

结束后返回上级调用是什么意思？cur重新变回0？执行下一个循环什么都不变那不是也是输出1234吗，怎么会变成2开头的排列啊，对递归不熟，求解，谢谢

追答

main 调用

print_permutation(4, A, 0)
接下来 print_permutation(4, A, 0) 有一个循环 调用
a[0] = 1 调用 print_permutation(4, A, 1) ==> 。。。。。。。。。。这里有很多
a[0] = 2 调用 print_permutation(4, A, 1) ==> 。。。。。。。。。。这里有很多
a[0] = 3 调用 print_permutation(4, A, 1) ==> 。。。。。。。。。。这里有很多
a[0] = 4 调用 print_permutation(4, A, 1) ==> 。。。。。。。。。。这里有很多

追问

emmm，我有点笨，看的不是很懂
那个cur怎么都是1？
你的意思是当cur等于4的时候所有结果都能输出吗？
可是不是只是输出四个数吗，输出后cur不会变为0，它是怎么又输出的啊？
还有，i不是从1开始吗，为什么会a[0]＝2或者3，4啊。
我现在头脑很乱，不好意思啊

追答

print_permutation(4, A, 0)    
接下来    print_permutation(4, A, 0)    有一个循环    调用    

a[0] = 1    调用    print_permutation(4, A, 1)
    a[1] = 1    不符合条件
    a[2] = 2    调用    print_permutation(4, A, 2)
        a[3] = 1    不符合条件
        a[3] = 2    不符合条件
        a[3] = 3    调用    print_permutation(4, A, 3)
            a[4] = 1, 2, 3    都不符合条件
            a[4] = 4    调用    print_permutation(4, A, 3)
                输出    a[1...4]    也就是    1,2,3,4
                退回到    print_permutation(4, A, 3)    继续
        a[3]    =4    继续调用    print_permutation(4, A, 3)
            a[4] = 1, 2, 不符合
            a[4] = 3    调用    print_permutation(4, A, 3)
                输出    a[1...4]    也就是    1,2,4, 3
            a[4] = 4    不符合    
            退回到    print_permutation(4, A, 3)    继续
        退回到    print_permutation(4, A, 2)    继续        
    a[2] = 4    调用    print_permutation(4, A, 2)    
        。很多很多，    
    a[2] = 4    调用    print_permutation(4, A, 2)    
        。很多很多，    
a[0] = 2    调用    print_permutation(4, A, 1)    
。。。

a[0] = 3    调用    print_permutation(4, A, 1)    
。。。
a[0] = 4    调用    print_permutation(4, A, 1)    
。。。