递归函数中的分段错误

我正在实现Strassen's matrix multiplication algorithm作为赋值的一部分。我已经正确编码了，但我不知道它为什么给出分段错误。我叫strassen（）为strassen（0，n，0，n）;主要是。 n是由用户给出的数字，它是2的幂，它是矩阵（2D阵列）的最大尺寸。它没有给n = 4的段错误，但是对于n = 8,16,32，它给出段错误。代码如下所示。递归函数中的分段错误

void strassen(int p, int q, int r, int s) 
    { 
     int p1,p2,p3,p4,p5,p6,p7; 
     if(((q-p) == 2)&&((s-r) == 2)) 
     { 
      p1 = ((a[p][r] + a[p+1][r+1])*(b[p][r] + b[p+1][r+1])); 
      p2 = ((a[p+1][r] + a[p+1][r+1])*b[p][r]); 
      p3 = (a[p][r]*(b[p][r+1] - b[p+1][r+1])); 
      p4 = (a[p+1][r+1]*(b[p+1][r] - b[p][r])); 
      p5 = ((a[p][r] + a[p][r+1])*b[p+1][r+1]); 
      p6 = ((a[p+1][r] - a[p][r])*(b[p][r] +b[p][r+1])); 
      p7 = ((a[p][r+1] - a[p+1][r+1])*(b[p+1][r] + b[p+1][r+1])); 
      c[p][r] = p1 + p4 - p5 + p7; 
      c[p][r+1] = p3 + p5; 
      c[p+1][r] = p2 + p4; 
      c[p+1][r+1] = p1 + p3 - p2 + p6; 
     } 
     else 
     { 
      strassen(p, q/2, r, s/2); 
      strassen(p, q/2, s/2, s); 
      strassen(q/2, q, r, s/2); 
      strassen(q/2, q, s/2, s); 
     } 
    }

来源

2013-03-16 Shreyas Kale

最有可能的终止条件不正确，并且函数递归直到它溢出堆栈。您至少应该检查在调试器中运行时会发生什么。如果调试器停止在'c'数组的任何一个赋值处，请检查这些索引以使它们不超出范围。 – 2013-03-16 16:22:06

不要让我们猜测。段错误的原因是什么，堆栈溢出或溢出数组边界？在gdb中敲击它并提供更多信息。 – 2013-03-16 16:24:03

您也可以尝试将'int'声明放在第一个if中。虽然我觉得约阿希姆是正确的。你确定条件是'=='而不是'<='？说'p'和'q'是10和10.然后我们有（10,10）（10,5）（10,2）（10,1）（10,0）... – 2013-03-16 16:25:55

一些在你的else块的条件是无限递归（至少第二和第四，没有检查等）。这可以用笔和纸很容易地证明：例如：
strassen(p, q/2, s/2, s)为`0,8,0,8将产生在每个迭代：

1) 0, 4, 4, 8 

2) 0, 2, 4, 8 

3) 0, 1, 4, 8 

4) 0, 0, 4, 8 

5) 0, 0, 4, 8

...

，并因为没有这些结果的传递你

if(((q-p) == 2)&&((s-r) == 2))

测试中，函数将运行（我怀疑分支，因为第4个函数有同样的问题...），直到堆栈结束时，导致分段错误。

无论如何，如果你正在尝试在else块做的是递归平分矩阵，更好的企图都将是这样的：

strassen(p, (q+p)/2, r, (r+s)/2);            
strassen(p, (q+p)/2, (r+s)/2, s);            
strassen((q+p)/2,q, (r+s)/2, s);             
strassen((q+p)/2,q, r, (r+s)/2);

（记住，我没有检查这个代码，虽然）

来源

2013-03-16 16:39:37 Rick77

谢谢，我会再次尝试，并期待在它与笔ñ纸和gdb了。 – 2013-03-16 16:43:37

请问，如果我的回答满足您的问题，请不要忘记标记为解决方案;-) – Rick77 2013-03-17 10:36:54

void strassen(int p, int q, int r, int s) 
{ 
    int p1,p2,p3,p4,p5,p6,p7; 
    if(q-p == 2 && s-r == 2) 
    { 
     p1 = (a[p][r] + a[p+1][r+1]) * (b[p][r] + b[p+1][r+1]); 
     p2 = (a[p+1][r] + a[p+1][r+1]) * b[p][r]; 
     p3 = a[p][r]     * (b[p][r+1] - b[p+1][r+1]); 
     p4 = a[p+1][r+1]    * (b[p+1][r] - b[p][r]); 
     p5 = (a[p][r] + a[p][r+1])  * b[p+1][r+1]; 
     p6 = (a[p+1][r] - a[p][r])  * (b[p][r] +b[p][r+1]); 
     p7 = (a[p][r+1] - a[p+1][r+1]) * (b[p+1][r] + b[p+1][r+1]); 
     c[p][r] = p1 + p4 - p5 + p7; 
     c[p][r+1] = p3 + p5; 
     c[p+1][r] = p2 + p4; 
     c[p+1][r+1] = p1 + p3 - p2 + p6; 
    } 
    else 
    { 
     if (q/2-p >= 2 && s/2-r >= 2) strassen(p, q/2, r, s/2); 
     if (q/2-p >= 2 && s-s/2 >= 2) strassen(p, q/2, s/2, s); 
     if (q-q/2 >= 2 && s/2-r >= 2) strassen(q/2, q, r, s/2); 
     if (q-q/2 >= 2 && s-s/2 >= 2) strassen(q/2, q, s/2, s); 
    } 
}

但更简单的递归塞将在函数的开头，如：

{ 
    int p1,p2,p3,p4,p5,p6,p7; 
    if(q-p < 2 || s-r < 2) return; 
    if(q-p == 2 && s-r == 2) 
    { ...

来源

2013-03-16 16:48:45 wildplasser

递归函数中的分段错误

回答

相关问题