Ошибка сегментации в рекурсивной функции

Question

Я реализую Strassen's matrix multiplication algorithm как часть задания. Я правильно закодировал его, но я не знаю, почему он дает ошибку сегментации. Я назвал strassen() как strassen (0, n, 0, n); в основном. n - это число, заданное пользователем, которое равно двум, и это максимальный размер матрицы (2D-массив). Он не дает segfault для n = 4, но для n = 8,16,32 он дает segfaults. Код приведен ниже.

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

Answer 1

Некоторые из условий, в вашем блоке еще бесконечно рекурсивный (по крайней мере, второй и четвертый, не проверили другие). Это можно легко проверить с помощью ручки и бумаги: , например.
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-я функция имеет ту же проблему ...) до тех пор, пока не ударит конец стека, вызвав ошибку сегментации.

Во всяком случае, если то, что вы пытаетесь сделать в блоке еще является рекурсивно разрез`ать матрицу, лучше попытка будет что-то вроде:

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

(имейте в виду, что я не сделал проверить этот код, хотя)

Answer 2

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