递归导致的分段错误

9!（362880） 和 （3628800） 是巨大的数字，当您执行尽可能多的递归调用时，它们会溢出调用堆栈。因为所有的局部变量和形式参数都必须存储。您要么必须增加堆栈大小，要么将递归转换为迭代。10!

在 linux 上，您可以执行以下操作：

ulimit -s unlimited

将堆栈大小设置为无限制。默认值通常为 8MB。

我会让你的函数迭代 - 添加，并删除递归调用：rearangedo while

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 <stdio.h>

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);
}

计算排列可以迭代完成，但即使你以递归方式进行计算，也不需要有一个巨大的堆栈（比如建议增加系统堆栈的答案）。事实上，你只需要一小部分的堆栈。考虑一下：

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 个元素。

编辑：我冒昧地在您的 rerange-function 中添加了一个递归计数器，它现在打印如下：

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<elems;++j){
            printf("%i ", temp[j]);
        }
        printf("   (at recursion depth %u)\n", depth);
    } else {
        int i=0;for(;i<elems;++i){
            temp[depth] = i;
            betterRecursion(depth+1, elems, temp);
        }
    }
}
int main() {
    int temp[100];
    betterRecursion(0, 11, temp); // arrange the 11 elements 0...10
    return 0;
}

您的程序不必要地使用了过多的递归。它使用递归，而实际上就足够了。n!n

若要仅使用递归，请考虑递归函数的以下逻辑：n

• 它接收要排列的唯一数字数组nums[]n
• 这些排列可以有不同的第一个数字，因为数组中有不同的数字nn
• （关键步骤）遍历 的元素，并在每次迭代中创建一个新数组，但删除了当前元素，并递归到相同的函数中，将这个较短的数组作为参数传递nums[]
• 随着递归的深入，参数数组会越来越小
• 当只剩下一个元素时，递归就结束了

使用此算法，您的递归不会比更深，并且您不会得到分段错误。关键在关键步骤中，您可以在其中构建一个新的数字数组，该数组始终比输入数组短 1 个项目。n

顺便说一句，请确保在提交之前检查程序的输出，例如运行它以确保您获得正确数量的组合，并检查没有重复项（如果没有重复项，则输出应为空）。| sort | uniq | wc -l| sort | uniq -d

剧透警告：这是我使用上述算法的变体的实现：https://gist.github.com/janosgyerik/5063197C++