I'm currently working on an exercise that requires me to swap recursively at random two integers within a given array.
Specifically, the program swaps two values, calculates in a given way the sum of this permutation, and keeps them, if the sum is the new lowest. If not, the program goes back to the previous sequence (i.e. swaps back the numbers), and repeats the process.
The output should display the sum and sequence that produces the lowest sum after 5M iterations.
My code works for 100,000 iterations (give or take), and then "segmentation fault" occurs.
Output for 10 ITERATIONS
*As mentioned, works up to 100,000 iterations.
Here, I output all permutations created after a swap, regardless of whether it is the new lowest sum. I then print the lowest sum (total) and the sequence.*
1 2 3 7 5 6 4 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 7 5 6 4 8 9 10 11 12 13 14 15 18 17 16 19 20
1 2 3 7 5 6 4 8 9 10 11 12 13 18 15 14 17 16 19 20
1 2 3 7 5 6 13 8 9 10 11 12 4 18 15 14 17 16 19 20
1 10 3 7 5 6 13 8 9 2 11 12 4 18 15 14 17 16 19 20
1 10 8 7 5 6 13 3 9 2 11 12 4 18 15 14 17 16 19 20
1 10 8 7 5 6 13 3 9 2 20 12 4 18 15 14 17 16 19 11
1 10 8 13 5 6 7 3 9 2 20 12 4 18 15 14 17 16 19 11
13 10 8 7 5 6 1 3 9 2 20 12 4 18 15 14 17 16 19 11
1 10 8 7 5 6 13 3 9 2 20 12 17 18 15 14 4 16 19 11
Total = 22328 1 10 8 7 5 6 13 3 9 2 20 12 4 18 15 14 17 16 19 11
Output for 100,000 plus ITERATIONS
Segmentation fault (core dumped)
Using Valgrind
==4395== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==4395==
==4395== Process terminating with default action of signal 11 (SIGSEGV)
==4395== Access not within mapped region at address 0x1FFE801FF8
==4395== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==4395== at 0x4A3A7AD: _IO_new_file_xsputn (fileops.c:1236)
==4395== by 0x4A3A7AD: _IO_file_xsputn@@GLIBC_2.2.5 (fileops.c:1197)
==4395== If you believe this happened as a result of a stack
==4395== overflow in your program's main thread (unlikely but
==4395== possible), you can try to increase the size of the
==4395== main thread stack using the --main-stacksize= flag.
==4395== The main thread stack size used in this run was 8388608.
==4395== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==4395==
==4395== Process terminating with default action of signal 11 (SIGSEGV)
==4395== Access not within mapped region at address 0x1FFE801FF0
==4395== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==4395== at 0x4831134: _vgnU_freeres (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_core-amd64-linux.so)
==4395== If you believe this happened as a result of a stack
==4395== overflow in your program's main thread (unlikely but
==4395== possible), you can try to increase the size of the
==4395== main thread stack using the --main-stacksize= flag.
==4395== The main thread stack size used in this run was 8388608.
==4395==
==4395== HEAP SUMMARY:
==4395== in use at exit: 1,024 bytes in 1 blocks
==4395== total heap usage: 1 allocs, 0 frees, 1,024 bytes allocated
==4395==
==4395== LEAK SUMMARY:
==4395== definitely lost: 0 bytes in 0 blocks
==4395== indirectly lost: 0 bytes in 0 blocks
==4395== possibly lost: 0 bytes in 0 blocks
==4395== still reachable: 1,024 bytes in 1 blocks
==4395== suppressed: 0 bytes in 0 blocks
==4395== Rerun with --leak-check=full to see details of leaked memory
==4395==
==4395== For lists of detected and suppressed errors, rerun with: -s
==4395== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Code
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <assert.h>
#include <string.h>
#define SZ 20
#define ITERATIONS 100000 //segmentation fault (core dumped) around 100,000 plus
void print_array(int arr[SZ]);
int score(int arr[SZ]);
void swap(int arr[SZ], int* num1, int* num2);
void dartboard(size_t count, int* min, int arr[SZ]);
int main() {
int arr[SZ] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
size_t count = 0;
int min = score(arr);
assert(min == 24350);
dartboard(count, &min, arr);
printf("Total = %d ", min);
print_array(arr);
return 0;
}
void dartboard(size_t count, int* min, int arr[SZ]) {
if(count<ITERATIONS) {
int num1 = rand()%SZ;
int num2 = rand()%SZ;
swap(arr, &num1, &num2);
int sum = score(arr);
print_array(arr); //print to check output (comment out once working)
count++;
if (sum > *min){
swap(arr, &num1, &num2); //swapping back
dartboard(count, min, arr); //repeating
}
else{
*min = sum; //new min
dartboard(count, min, arr); //repeat
}
}
return;
}
void swap(int arr[SZ], int* num1, int* num2) {
int temp;
temp = arr[*num1];
arr[*num1] = arr[*num2];
arr[*num2] = temp;
}
int score(int arr[SZ]) {
int sum = 0;
for(int i = 0; i < SZ; i++) {
sum = sum + pow((arr[i] + arr[(i+1)%SZ] + arr[(i+2)%SZ]), 2.0);
}
return sum;
}
void print_array(int arr[SZ]){
for(int i=0; i<20; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
My understanding is that this program is causing all my function calls to slowly stack up until overflow. I'm not sure however how exactly to manage memory and overcome these types of issues when it comes to recursion.