时间戳

首页 > 解决方案 > 无法推断为什么我的递归函数中会出现分段错误

c - 无法推断为什么我的递归函数中会出现分段错误

问题描述

通过注释掉代码的特定部分，我对我的代码进行了一些试验。我发现当我用变量 j（如代码所示）注释掉 for 循环时，不会发生分段错误。此外，当我注释掉函数中的递归部分（函数调用自身的行）时，即使存在 for 循环也不会发生段错误。很明显，for循环在函数的第二次或更高次迭代中引起了问题，但我不知道为什么。我能想到的一个可能原因是发生了无限递归，但据我所知，这里没有发生无限递归。我一直在尝试解决以下问题：https ://www.codechef.com/problems/H1

#include<stdio.h>
 int prime1[]={3,5,7,11,13,17};
 int min=1000000000;   //just some large number
 void check(int *, int);
 void swap(int*, int, int);
 int prime(int);
 int main()
 {
  int T;
  scanf("%d", &T);
  for(int i=0; i<T; i++)
  {
   printf("\n");
   int arr[9];
   for(int j=0; j<9; j++)
   scanf("%d", &arr[j]);
   check(arr, 0);
   if(min==1000000000)
    min=-1;
   printf("%d\n", min);
  } 
 }

 void check(int arr[],int  step)       //step indicates the level of     
                                       //iteration
 {
  int k,  a[9];
  for(k=0; k<9; k++)
  {
   if(arr[k]!=k+1)
    break;
  }
  if(k==9)
  {
   if(step<min)
    min=step;
  }
  else
  {
   for(int i=0; i<8; i++)
   {
    if(i%3!=2)
    {
     if(prime(arr[i]+arr[i+1]))
     {
      for(int j=0; j<9; j++)          // segmentation fault 
       a[j]=arr[j];
      swap(a, i, i+1);
      check(a, step+1);
     }
    }
    if(i<=5)
    {
     if(prime(arr[i]+arr[i+3]))
     {
      for(int j=0; j<9; j++)          // segmentation fault
       a[j]=arr[j];
      swap(a, i, i+3);
      check(a, step+1);
     }
    }
   }  
  }  
 }
 int prime(int a)
 {
  for(int i=0; i<6; i++)
  {
   if(a==prime1[i])
    return 1;
  }
  return 0;
 }

 void swap( int a[], int b, int c)
 {
  int temp;
  temp=a[b];
  a[b]=a[c];
  a[c]=temp; 
 }

标签： crecursion

解决方案

您的算法永远运行切换前两个瓷砖。
我删除了一些循环，i=0我们剩下k=0：arr[] = {4,3,}

void check(int arr[], int step)
{
    int k, a[9];
    // arr[0] != 1, so k != 9, we fall in else { ... }
//  for (k = 0; k < 9; k++) {
//      if (arr[k] != k+1)
//          break;
//  }
//  printf("\n");
//  if (k == 9) {
//      if (step < min)
//          min = step;
//  } else {
        int i = 0;
//      for (int i = 0; i < 8; i++) {
//          if (i%3 != 2) {
//              if (prime(arr[i] + arr[i+1])) {
                    // i = 0, so i%3 != 2, so we fall in the first if
                    for (int j = 0; j < 9; j++)
                        a[j] = arr[j];
                    // you swap arr[0] with arr[1]
                    swap(a, i, i+1);
                    // and then you check again
                    check(a, step+1);
                    // and it runs so forever, never reaching this point
//              }
//          }
//          if (i <= 5) {
//              if (prime(arr[i] + arr[i+3])) {
//                  for (int j = 0; j < 9; j++)
//                      a[j] = arr[j];
//                  swap(a, i, i+3);
//                  check(a, step+1);
//              }
//          }
        }
    }
}

这个算法需要重新思考。当使用不同的步数运行时，您需要区分算法。最简单的方法是在每次检查时随机切换一个标题，更好的是构建一个适当的决策树，您可以记住哪些标题被切换了。
你可能会对一些适当的缩进感兴趣，

推荐阅读