递归引起的分段错误
我正在编写一个程序，要取1-10之间的数字，并显示所有可能的方法来安排数字。
防爆输入：3输出：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 每当我输入9或10时，程序会产生分段错误并转储核心。 我相信问题是我的递归算法被调用了太多次。 有人可以帮助指出我如何限制所需的递归调用量吗？ 这是我目前的代码：
void rearange(int numbers[11], int index, int num, int fact) { int temp = numbers[index]; numbers[index] = numbers[index-1]; numbers[index-1] = temp; int i; for (i = 1; i 0) // If we have more sequences remaining rearange(numbers, index, num, fact); // Do it all again! :D } int main() { int num, i; // our number and a counter printf("Enter a number less than 10: "); scanf("%d", &num); // get the number from the user int numbers[11]; // create an array of appropriate size // fill array for (i = 1; i <= num; i++) { // fill the array from 1 to num numbers[i] = i; } int fact = 1; // calculate the factorial to determine for (i = 1; i <= num; ++i) // how many possible sequences { fact = fact * i; } rearange(numbers, num, num, fact); // begin rearranging by recursion return 0; }
9! （362880）和10! （3628800）是在执行尽可能多的递归调用时溢出调用堆栈的巨大数字。 因为必须存储所有局部变量和forms参数。 您要么必须增加堆栈大小，要么将递归转换为迭代。
在linux上，你可以这样做：
ulimit -s unlimited
将堆栈大小设置为无限制。 默认值通常为8MB。
计算排列可以迭代完成，但即使你递归地执行它也不需要有一个巨大的堆栈（比如建议增加系统堆栈的答案）。 事实上，你只需要少量的筹码。 考虑一下：
0 1 <- this needs **2** stackframes 1 0 and an for-loop of size 2 in each stackframe 0 1 2 <- this needs **3** stackframes 0 2 1 and an for-loop of size 3 in each stackframe 1 0 2 1 2 0 2 1 0 2 0 1
在每个堆栈帧中排列9个元素需要9个堆栈帧和一个for循环通过9个元素。
编辑：我已经冒昧地为你的重新排列函数添加一个递归计数器，它现在打印如下：
Enter a number less than 10: 4 depth 1 1 2 4 3 depth 2 1 4 2 3 depth 3 4 1 2 3 depth 4 4 1 3 2 depth 5 4 3 1 2 depth 6 3 4 1 2 depth 7 3 4 2 1 depth 8 3 2 4 1 depth 9 2 3 4 1 depth 10 2 3 1 4 depth 11 2 1 3 4 depth 12 1 2 3 4 depth 13 1 2 4 3 depth 14 1 4 2 3 depth 15 4 1 2 3 depth 16 4 1 3 2 which is obviously wrong even if you do it recursively. depth 17 4 3 1 2 depth 18 3 4 1 2 depth 19 3 4 2 1 depth 20 3 2 4 1 depth 21 2 3 4 1 depth 22 2 3 1 4 depth 23 2 1 3 4 depth 24 1 2 3 4 ....
递归叶子应该是唯一输出的叶子，因此深度应该是恒定的和小的（等于你输入的数字）。
编辑2：
好的，写了代码。 试试看：
#include "stdio.h" void betterRecursion(int depth, int elems, int* temp) { if(depth==elems) { int j=0;for(;j
我会重复你的rearange函数 – 添加时，删除递归调用：
void rearange(int numbers[11], int index, int num, int fact) { int temp; do { temp = numbers[index]; numbers[index] = numbers[index-1]; numbers[index-1] = temp; int i; for (i = 1; i <= num; ++i) // print the current sequence { printf("%d ", numbers[i]); } printf("\n"); fact--; // decrement how many sequences remain index--; // decrement our index in the array if (index == 1) // if we're at the beginning of the array index = num; // reset index to end of the array } while (fact > 0); }
这不是深度递归的任务。 尝试发明一些更友好的堆栈算法。 以下代码在速度方面比使用堆栈大小有相当麻烦…它有点慢，例如对于n = 1000但是它有效。
#include void print_arrangement(int n, int* x) { int i; for(i = 0; i < n; i++) { printf("%s%d", i ? " " : "", x[i]); } printf("\n"); } void generate_arrangements(int n, int k, int* x) { int i; int j; int found; if (n == k) { print_arrangement(n, x); } else { for(i = 1; i <= n; i++) { found = 0; for(j = 0; j < k; j++) { if (x[j] == i) { found = 1; } } if (!found) { x[k] = i; generate_arrangements(n, k + 1, x); } } } } int main(int argc, char **argv) { int x[50]; generate_arrangements(50, 0, x); }
您的程序不必要地使用了太多的递归。 它正在使用n! 实际上n就足够的递归。
要仅使用n递归，请考虑递归函数的此逻辑：
- 它接收一个
n唯一数字的数组nums[]来安排 - 这些排列可以在其中具有
n不同的第一个数字，因为arrays中有n不同的数字 - （关键步骤）循环遍历
nums[]的元素，并在每次迭代中创建一个新数组但删除当前元素，并递归到同一函数中，将此较短的数组作为参数传递 - 随着深度递归，参数数组将越来越小
- 当只剩下一个元素时，那就是递归的结束
使用此算法，您的递归不会比n更深，您不会得到分段错误。 关键是在关键步骤中，您将构建一个新的数字数组，该数组总是比输入数组短1项。
作为旁注，请务必在提交之前检查程序的输出，例如运行| sort | uniq | wc -l | sort | uniq | wc -l | sort | uniq | wc -l以确保您获得正确数量的组合，并检查没有与| sort | uniq -d重复 | sort | uniq -d | sort | uniq -d （如果没有重复，则输出应为空）。
剧透警报：这是我使用上述算法的变体在C++中的实现： https ： //gist.github.com/janosgyerik/5063197