C语言递归排列算法错误求助：新手求递归解题思路与代码修正提示

你的代码里的关键问题 #

1. Permutation函数语法+逻辑全错：
   • 开头if(i>=N) return;里的i未定义，属于语法错误
   • 递归调用Permutation(i+1, N-i, num)完全偏离全排列核心逻辑，N-i这个参数没有意义，全排列递归要关注的是当前处理的位置，而非剩余长度
   • 打印逻辑混乱，没有跟踪已选入排列的元素，直接遍历数组打印，无法生成正确的排列组合
2. main函数调用逻辑错误：循环打印每个元素再调用Permutation的方式完全错误，全排列只需要从第0位启动一次递归即可

递归全排列（字典序）的正确思路 #

全排列的递归本质是分治+回溯：

• 固定数组的第start个位置，对剩下的元素做全排列
• 终止条件：当start等于数组长度时，说明已生成一个完整排列，直接输出
• 因为你已将输入数组升序排序，按顺序交换start与后面的元素，递归生成的排列天然符合字典序
• 递归完成后必须回溯（把交换的元素换回来），避免影响后续递归分支的状态

递归类编程题的实用技巧 #

• 先明确终止条件：比如全排列中，处理到数组末尾就是终止点，此时要执行输出操作
• 拆解子问题：把大问题拆成相同逻辑的小问题，比如“生成n个数的排列”可拆为“固定第1个元素，生成剩下n-1个数的排列”
• 回溯要到位：递归前修改了状态（比如交换元素），递归后一定要恢复状态，否则后续分支会出错
• 手动模拟小例子：比如拿n=2的情况，手动走一遍递归流程，理清每一步的调用顺序和数组变化，比单纯看代码更易理解

修正后的完整代码 #

#include <stdio.h>

// 辅助交换函数
void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 递归生成全排列：start是当前要固定的位置
void Permutation(int start, int N, int num[]) {
    // 终止：已经处理完所有元素，输出当前排列
    if (start == N) {
        for (int i = 0; i < N; i++) {
            printf("%d%s", num[i], i == N-1 ? "\n" : " ");
        }
        return;
    }
    // 依次把start位置和后面的每个元素交换，递归处理子数组
    for (int i = start; i < N; i++) {
        swap(&num[start], &num[i]);
        Permutation(start + 1, N, num);
        swap(&num[start], &num[i]); // 回溯，恢复原数组状态
    }
}

// 排序函数，做了小优化（j从i+1开始，避免自我比较）
void sort(int N, int *num) {
    int tmp;
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            if (*(num + i) > *(num + j)) {
                tmp = *(num + i);
                *(num + i) = *(num + j);
                *(num + j) = tmp;
            }
        }
    }
}

int main() {
    int N;
    scanf("%d", &N);
    int num[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &num[i]);
    }
    sort(N, num); // 先排序保证字典序
    Permutation(0, N, num); // 从第0位启动递归
    return 0;
}

代码说明 #

• swap函数用于快速交换元素，方便回溯操作
• Permutation函数中，start标记当前要固定的位置：每次交换start与后面的元素，递归处理后续子数组，递归完成后交换回来，确保每个分支的数组状态正确
• 排序函数的小优化不影响结果，但减少了无用的自我比较
• main函数只需调用一次Permutation即可生成所有排列，无需额外循环

内容的提问来源于stack exchange，提问作者NatsumiStar