Segmentation fault due to recursion

Question

I'm writing a program that is to take a number between 1-10 and display all possible ways of arranging the numbers.

Ex input: 3 output:

   1 2 3
   1 3 2
   2 1 3
   2 3 1
   3 1 2
   3 2 1

Whenever I input 9 or 10, the program gives a segmentation fault and dumps the core. I believe the issue is my recursive algorithm is being called too many times. Could someone help point out how I could limit the amount of recursive calls necessary? Here is my current code:

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 <= 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

  if (fact > 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;
}

Answer 1

9! (362880) and 10! (3628800) are huge numbers that overflow the call stack when you do as many recursive calls. Because all the local variables and formal parameters have to be stored. You either you have to increase the stack size or convert the recursion into iteration.

On linux, you can do:

ulimit -s unlimited

to set the stack size to unlimited. The default is usually 8MB.

Answer 2

Calculating permutations can be done iteratively, but even if you do it recursively there is no need to have a gigantic stack (like answers suggesting to increase your system stack say). In fact you only need a tiny amount of your stack. Consider this:

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

Permuting 9 elements takes 9 stackframes and a for-loop through 9 elements in each stackframe.

EDIT: I have taken the liberty to add a recursion-counter to your rearrange-function, it now prints like this:

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

The recursion-leafs should be the only ones which output so the depth should be constant and small (equal to the number you enter).

EDIT 2:

Ok, wrote the code. Try it out:

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

Answer 3

I'd make your rearange function iterative - do while added, and recursive call removed:

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

Answer 4

This is not a task for a deep recursion. Try to invent some more stack-friendly algorithm. Following code has rather troubles with speed than with stack size... It's a bit slow e.g. for n=1000 but it works.

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

Answer 5

Your program is using too many recursions unnecessarily. It is using n! recursions when actually n would be enough.

To use only n recursions, consider this logic for the recursive function:

• It receives an array nums[] of n unique numbers to arrange
• The arrangements can have n different first number in them, as there are n different numbers in the array
• (key step) Loop over the elements of nums[], and in each iteration create a new array but with the current element removed, and recurse into the same function passing this shorter array as parameter
• As you recurse deeper, the parameter array will be smaller and smaller
• When there is only one element left, that's the end of the recursion

Using this algorithm, your recursion will not be deeper than n and you will not get segmentation fault. The key is in the key step, where you build a new array of numbers that is always 1 item shorter than the input array.

As a side note, make sure to check the output of your program before you submit, for example run it through | sort | uniq | wc -l to make sure you are getting the correct number of combinations, and check that there are no duplicates with | sort | uniq -d (the output should be empty if no dups).

Spoiler alert: here's my implementation in C++ using a variation of the above algorithm: https://gist.github.com/janosgyerik/5063197