代码之家 › 专栏 › 技术社区 › radnaskela

在C中使用递归的堆栈溢出[closed]

stack-overflow recursion c

radnaskela · 技术社区 · 8 年前

我一直在疯狂地寻找答案,但毫无结果;我创建了一个四叉树,它应该对结构声明的1000多个对象的数组进行排序:

typedef struct node
{
    char     is_leaf;
    struct Particle *p;
    double    m;

    double center_x;
    double center_y;
    double width;

    struct node *sw;
    struct node *nw;
    struct node *se;
    struct node *ne;

} node;

到一个具有以下函数的四叉树中:

node* quadtree_insert(node *n, struct Particle *p, double center_x, double center_y, double width)
{
    if(n == NULL)
    {
        n = (node*)malloc(sizeof(node));
        n->is_leaf = 1;

        n->p = p;
        //n->m = 0.1;

        n->sw = NULL;
        n->se = NULL;
        n->nw = NULL;
        n->ne = NULL;
        if(width < 1e-300){
            n->width = 1e-300;
            }
        else
            n->width    = width;
        return n;
    }
    else{
        //n = (node*)malloc(sizeof(node));
        double x;
        double y;
        if(width < 1e-300){
            width = 1e-300;
            }
        if(n->is_leaf == 1) //! that is, if the node is not a branch
        {
                        x = (double)n->p->x_pos;
            y = (double)n->p->y_pos;

            if(x <= center_x && y <= center_y) //! first quadrant
            {
                n->sw = quadtree_insert(n->sw, n->p, center_x * 0.5, center_y * 0.5, width * 0.5);
            }
            else if(x <= center_x && y > center_y) //! second quadrant
            {
                n->nw = quadtree_insert(n->nw, n->p, center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
            }
            else if(x > center_x && y <= center_y) //! third quadrant
            {
                n->se = quadtree_insert(n->se, n->p, center_x + center_x * 0.5, center_y * 0.5, width * 0.5);
            }
            else //! fourth quadrant
            {
                n->ne = quadtree_insert(n->ne, n->p, center_x + center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
            }

            n->p = NULL; //! sets branch pointer to nothing...
            n->is_leaf = 0;
                    }
        //}

        x = (double)p->x_pos;
        y = (double)p->y_pos;

        if(x <= center_x && y <= center_y) //! first quadrant
        {
            n->sw = quadtree_insert(n->sw, p, center_x * 0.5, center_y * 0.5, width * 0.5);

        }
        else if(x <= center_x && y > center_y) //! second quadrant
        {
            n->nw = quadtree_insert(n->nw, p, center_x * 0.5, center_y + center_y * 0.5, width * 0.5);

        }
        else if(x > center_x && y <= center_y) //! third quadrant
        {
            n->se = quadtree_insert(n->se, p, center_x + center_x * 0.5, center_y * 0.5, width * 0.5);

        }
        else //! fourth quadrant
        {
            n->ne = quadtree_insert(n->ne, p, center_x + center_x * 0.5, center_y + center_y * 0.5, width * 0.5);            
        }
        return n;
    }
}

这一切都由以下人员完成:

 node *root = NULL;
  root = quadtree_insert(root, &particles[0],0.500,0.5,1);

  for(i = 1; i < nParticles; i++)
  {
    quadtree_insert(root, &particles[i],0.5000,0.5,1);
  }

其中“particles”以struct Particle*particles的形式传递。粒子的定义如下:

struct Particle {
    double mass;
    double x_pos;
    double y_pos;
    double x_vel;
    double y_vel;
};

typedef struct Particle * Particle_structure;

每次迭代之后,for循环之后,根目录都是空闲的,代码适用于小于200的样本,而valgrind对此没有错误。此外还有一个中间函数,它对粒子执行一些运算:

double quadtree_calculate_forcey(struct Particle *p, node *n, double theta_max, double delta_t, int numP, double epsilon, double G)
{
    if(n != NULL)
    {
            double d_x      = (n->center_x - p->x_pos);
                double d_y      = (n->center_y - p->y_pos);
        double r_2     = d_x * d_x + d_y * d_y;
        r_2 = sqrt(r_2) + epsilon;
        if(theta_max <= (n->width / r_2) && !n->is_leaf){
                double a = 0;
            if(n->sw != NULL)
                        a += quadtree_calculate_forcey(p, n->sw, theta_max, delta_t, numP, epsilon, G);
                    if(n->nw != NULL)
                        a += quadtree_calculate_forcey(p, n->nw, theta_max, delta_t, numP, epsilon, G);
                    if(n->se != NULL)
                        a += quadtree_calculate_forcey(p, n->se, theta_max, delta_t, numP, epsilon, G);
                    if(n->ne != NULL)
                        a += quadtree_calculate_forcey(p, n->ne, theta_max, delta_t, numP, epsilon, G);
                    return a;
        }
        else    
                {
                double fy;
            double mass;
           if(d_x == 0 && d_y == 0){ // could be comparing the same star
                 //printf("RÃÃÃVHATT\n");  
                  return 0;
            }
            else{
            //printf("MASS : %f\n", n->m);
                  mass = n->m;
                  //printf("MASS : %f\n", mass);
                  fy = G * (mass * p->mass/ pow(r_2,3)) * d_y;   
                            //printf("DY:%f   DX:%f   R_2:%f   MASSA:%f\n",d_y, d_x, r_2 - epsilon, mass);          
                     // printf("HIT SKA JAG: %f\n",d_y);
                  return fy;              
                 }
        }
    }
    return 0.0;
}

振铃的原因是它滚动了一段时间(清除根,并为新位置重新执行),因此递归中的变量数肯定不是问题所在(?)。我敢肯定,当涉及到指针声明的某些分配时,我是在和鱼儿们一起游泳。任何想法/帮助都会让你站在奥丁这边!

编辑:一个我们如何找到质心等的例子。节点质量也是这样做的。

double set_centerx(node *n)
{
    if(n != NULL)
    {
        if(!(n->is_leaf))
        {
                    double a = set_centerx(n->ne);
                    double b = set_centerx(n->nw);
                    double c = set_centerx(n->se);
                    double d = set_centerx(n->sw);
                    double m1 = get_mass2(n->ne);
                    double m2 = get_mass2(n->nw);
                    double m3 = get_mass2(n->se);
                    double m4 = get_mass2(n->sw);
          n->center_x = (double)(m1*a + m2*b + m3*c + m4*d)/(m1+m2+m3+m4);
          return n->center_x;
        }
                n->center_x =n->p->x_pos;
        return n->p->x_pos;
    }

    return 0;
}

2 回复 | 直到 8 年前

Community CDub 7 年前

部分分析

我可以肯定,问题主要是由于主代码中大量重复的代码(接近重复的代码) else 第条,共条 quadtree_insert() .我在开头写了一些评论 Fragment 1A 和 Fragment 1B 片段1B现在也有 #ifdef DO_REPEAT 和 #endif .

    else
    {
        /* Fragment 1A */
        // n = (node*)malloc(sizeof(node));
        double x;
        double y;
        if (width < 1e-300)
        {
            width = 1e-300;
        }
        if (n->is_leaf == 1) // ! that is, if the node is not a branch
        {
            x = (double)n->p->x_pos;
            y = (double)n->p->y_pos;

            if (x <= center_x && y <= center_y) // ! first quadrant
            {
                n->sw = quadtree_insert(n->sw, n->p, center_x * 0.5, center_y * 0.5, width * 0.5);
            }
            else if (x <= center_x && y > center_y) // ! second quadrant
            {
                n->nw = quadtree_insert(n->nw, n->p, center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
            }
            else if (x > center_x && y <= center_y) // ! third quadrant
            {
                n->se = quadtree_insert(n->se, n->p, center_x + center_x * 0.5, center_y * 0.5, width * 0.5);
            }
            else // ! fourth quadrant
            {
                n->ne = quadtree_insert(n->ne, n->p, center_x + center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
            }

            n->p = NULL; // ! sets branch pointer to nothing...
            n->is_leaf = 0;
        }

#ifdef DO_REPEAT
        /* Fragment 1B */
        x = (double)p->x_pos;
        y = (double)p->y_pos;

        if (x <= center_x && y <= center_y) // ! first quadrant
        {
            n->sw = quadtree_insert(n->sw, p, center_x * 0.5, center_y * 0.5, width * 0.5);
        }
        else if (x <= center_x && y > center_y) // ! second quadrant
        {
            n->nw = quadtree_insert(n->nw, p, center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
        }
        else if (x > center_x && y <= center_y) // ! third quadrant
        {
            n->se = quadtree_insert(n->se, p, center_x + center_x * 0.5, center_y * 0.5, width * 0.5);
        }
        else // ! fourth quadrant
        {
            n->ne = quadtree_insert(n->ne, p, center_x + center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
        }
#endif /* DO_REPEAT */
        return n;
    }

我把你的代码重新排序了一些片段,并使用了这个 main() 注意,我本不需要这样做;你应该制作一个MCVE( How to create a Minimal, Complete, and Verifiable Example? )或SSCCE( Short, Self-Contained, Correct Example )两个名称和链接用于相同的基本思想。

static struct Particle particles[] =
{
    {  19.99,  96.07,  62.79, -99.46,  19.70 },
    {  12.94,   1.43, -33.45,  31.80, -66.08 },
    {   6.49,  16.99, -20.83,  92.51,  35.98 },
    {  17.01, -28.85, -94.10,  42.82,  -1.30 },
    {  14.27,  85.07,  88.21,  11.22,  16.85 },
    {  15.73, -56.37,  46.85,  27.40, -15.15 },
    {   1.53, -49.44, -64.27, -29.45, -38.25 },
    {   8.03,  92.11, -47.50,  63.77, -29.99 },
    {   8.67, -99.81,  73.19,  18.75,  88.66 },
    {  16.36,  66.33,  14.23,  87.65,  40.01 },
};

enum { nParticles = sizeof(particles) / sizeof(particles[0]) };

int main(void)
{
    node *root = NULL;
    printf("Particle 0:\n");
    root = quadtree_insert(root, &particles[0], 0.500, 0.5, 1);

    for (int i = 1; i < nParticles; i++)
    {
        printf("Particle %d:\n", i);
        quadtree_insert(root, &particles[i], 0.5000, 0.5, 1);
    }
    return 0;
}

我使用随机数生成器生成值表:

random -n 10 -T '    { %6:2[1:20]f, %6:2[-100:100]f, %6:2[-100:100]f, %6:2[-100:100]f, %6:2[-100:100]f },'

它在粒子6上为我崩溃了。大体上, valgrind 说:

â¦startup blurb omittedâ¦
Particle 0:
Particle 1:
Particle 2:
Particle 3:
Particle 4:
Particle 5:
Particle 6:
==79528== 
==79528== Process terminating with default action of signal 11 (SIGSEGV)
==79528==  Access not within mapped region at address 0x104003FD0
==79528==    at 0x100008E39: malloc (vg_replace_malloc.c:302)
==79528==  If you believe this happened as a result of a stack
==79528==  overflow in your program's main thread (unlikely but
==79528==  possible), you can try to increase the size of the
==79528==  main thread stack using the --main-stacksize= flag.
==79528==  The main thread stack size used in this run was 8388608.
==79528== 
==79528== HEAP SUMMARY:
==79528==     in use at exit: 6,017,700 bytes in 75,080 blocks
==79528==   total heap usage: 75,162 allocs, 82 frees, 6,023,876 bytes allocated
==79528== 
==79528== LEAK SUMMARY:
==79528==    definitely lost: 4,120 bytes in 2 blocks
==79528==    indirectly lost: 2,288 bytes in 6 blocks
==79528==      possibly lost: 4,880 bytes in 45 blocks
==79528==    still reachable: 5,997,720 bytes in 74,904 blocks
==79528==         suppressed: 8,692 bytes in 123 blocks
==79528== Rerun with --leak-check=full to see details of leaked memory

即使在我运行它的Mac电脑上,这也表明存在问题;被压制的东西是可以的,但其余的大部分都不行。

编译时没有 -DDO_REPEAT (正常编译),示例程序运行至完成。当然,它会泄漏,因为没有代码来释放内存。

Particle 0:
Particle 1:
Particle 2:
Particle 3:
Particle 4:
Particle 5:
Particle 6:
Particle 7:
Particle 8:
Particle 9:
==79683== 
==79683== HEAP SUMMARY:
==79683==     in use at exit: 26,580 bytes in 191 blocks
==79683==   total heap usage: 273 allocs, 82 frees, 32,756 bytes allocated
==79683== 
==79683== LEAK SUMMARY:
==79683==    definitely lost: 4,200 bytes in 3 blocks
==79683==    indirectly lost: 2,368 bytes in 7 blocks
==79683==      possibly lost: 4,880 bytes in 45 blocks
==79683==    still reachable: 6,440 bytes in 13 blocks
==79683==         suppressed: 8,692 bytes in 123 blocks
==79683== Rerun with --leak-check=full to see details of leaked memory

请注意,使用的内存比以前少得多。

如果由于缺少 DO_REPEAT 事实上是至关重要的,那么bug要么存在于代码中,要么存在于片段1A中完成的设置工作中。然而,在我看来,使用递归调用两次插入相同的粒子可能是问题的根源。

我还注意到 quadtree_calculate_forcey() 代码中未使用函数;这绝对不是MCVE的一部分。

需要片段1B

John Bollinger 建议:

请注意,“重复”代码的形式相同,但细节不同。也就是说,片段1B使用 n->p 片段1A使用 p 。我认为这是有目的的:这个想法似乎是将所有数据(粒子)强制输出到叶节点。

和 radnaskela 确认:

正如约翰所说,每个粒子都应该占据一个末端节点。我怀疑这与运动和行星的排列有关,因此要打开两个自由正方形,必须进行荒谬的迭代次数。但我无法找到解决我问题的办法,有什么想法吗?

逻辑有问题,但我不完全确定是什么问题 四叉树插入() ,如下所示:

static node *quadtree_insert(node *n, struct Particle *p, double center_x, double center_y, double width)
{
    printf("Centre (X,Y) = (%6.2f,%6.2f)\n", center_x, center_y);
    if (n == NULL)
    {
        n = (node *)malloc(sizeof(node));
        n->is_leaf = 1;

        n->p = p;
        // n->m = 0.1;

        n->sw = NULL;
        n->se = NULL;
        n->nw = NULL;
        n->ne = NULL;
        if (width < 1e-300)
        {
            n->width = 1e-300;
        }
        else
            n->width    = width;
        return n;
    }
    else
    {
        // n = (node*)malloc(sizeof(node));
        double x;
        double y;
        if (width < 1e-300)
        {
            width = 1e-300;
        }
        if (n->is_leaf == 1) // ! that is, if the node is not a branch
        {
            x = (double)n->p->x_pos;
            y = (double)n->p->y_pos;

            if (x <= center_x && y <= center_y) // ! first quadrant
            {
                printf("Recurse SW 1: ");
                n->sw = quadtree_insert(n->sw, n->p, center_x * 0.5, center_y * 0.5, width * 0.5);
            }
            else if (x <= center_x && y > center_y) // ! second quadrant
            {
                printf("Recurse NW 1: ");
                n->nw = quadtree_insert(n->nw, n->p, center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
            }
            else if (x > center_x && y <= center_y) // ! third quadrant
            {
                printf("Recurse SE 1: ");
                n->se = quadtree_insert(n->se, n->p, center_x + center_x * 0.5, center_y * 0.5, width * 0.5);
            }
            else // ! fourth quadrant
            {
                printf("Recurse NE 1: ");
                n->ne = quadtree_insert(n->ne, n->p, center_x + center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
            }

            n->p = NULL; // ! sets branch pointer to nothing...
            n->is_leaf = 0;
        }

        x = (double)p->x_pos;
        y = (double)p->y_pos;

        if (x <= center_x && y <= center_y) // ! first quadrant
        {
            printf("Recurse SW 2: ");
            n->sw = quadtree_insert(n->sw, p, center_x * 0.5, center_y * 0.5, width * 0.5);
        }
        else if (x <= center_x && y > center_y) // ! second quadrant
        {
            printf("Recurse NW 2: ");
            n->nw = quadtree_insert(n->nw, p, center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
        }
        else if (x > center_x && y <= center_y) // ! third quadrant
        {
            printf("Recurse SE 2: ");
            n->se = quadtree_insert(n->se, p, center_x + center_x * 0.5, center_y * 0.5, width * 0.5);
        }
        else // ! fourth quadrant
        {
            printf("Recurse NE 2: ");
            n->ne = quadtree_insert(n->ne, p, center_x + center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
        }
        return n;
    }
}

使用10点数据集运行时,粒子5的输出为:

Particle 0: Centre (X,Y) = (  0.50,  0.50)
Particle 1: Centre (X,Y) = (  0.50,  0.50)
Recurse NE 1: Centre (X,Y) = (  0.75,  0.75)
Recurse SE 2: Centre (X,Y) = (  0.75,  0.25)
Particle 2: Centre (X,Y) = (  0.50,  0.50)
Recurse SE 2: Centre (X,Y) = (  0.75,  0.25)
Recurse SE 1: Centre (X,Y) = (  1.12,  0.12)
Recurse SE 2: Centre (X,Y) = (  1.12,  0.12)
Recurse SE 1: Centre (X,Y) = (  1.69,  0.06)
Recurse SE 2: Centre (X,Y) = (  1.69,  0.06)
Recurse SW 1: Centre (X,Y) = (  0.84,  0.03)
Recurse SE 2: Centre (X,Y) = (  2.53,  0.03)
Particle 3: Centre (X,Y) = (  0.50,  0.50)
Recurse SW 2: Centre (X,Y) = (  0.25,  0.25)
Particle 4: Centre (X,Y) = (  0.50,  0.50)
Recurse NE 2: Centre (X,Y) = (  0.75,  0.75)
Recurse NE 1: Centre (X,Y) = (  1.12,  1.12)
Recurse NE 2: Centre (X,Y) = (  1.12,  1.12)
Recurse NE 1: Centre (X,Y) = (  1.69,  1.69)
Recurse NE 2: Centre (X,Y) = (  1.69,  1.69)
Recurse NE 1: Centre (X,Y) = (  2.53,  2.53)
Recurse NE 2: Centre (X,Y) = (  2.53,  2.53)
Recurse NE 1: Centre (X,Y) = (  3.80,  3.80)
Recurse NE 2: Centre (X,Y) = (  3.80,  3.80)
Recurse NE 1: Centre (X,Y) = (  5.70,  5.70)
Recurse NE 2: Centre (X,Y) = (  5.70,  5.70)
Recurse NE 1: Centre (X,Y) = (  8.54,  8.54)
Recurse NE 2: Centre (X,Y) = (  8.54,  8.54)
Recurse NE 1: Centre (X,Y) = ( 12.81, 12.81)
Recurse NE 2: Centre (X,Y) = ( 12.81, 12.81)
Recurse NE 1: Centre (X,Y) = ( 19.22, 19.22)
Recurse NE 2: Centre (X,Y) = ( 19.22, 19.22)
Recurse NE 1: Centre (X,Y) = ( 28.83, 28.83)
Recurse NE 2: Centre (X,Y) = ( 28.83, 28.83)
Recurse NE 1: Centre (X,Y) = ( 43.25, 43.25)
Recurse NE 2: Centre (X,Y) = ( 43.25, 43.25)
Recurse NE 1: Centre (X,Y) = ( 64.87, 64.87)
Recurse NE 2: Centre (X,Y) = ( 64.87, 64.87)
Recurse SE 1: Centre (X,Y) = ( 97.31, 32.44)
Recurse NE 2: Centre (X,Y) = ( 97.31, 97.31)
Particle 5: Centre (X,Y) = (  0.50,  0.50)
Recurse NW 2: Centre (X,Y) = (  0.25,  0.75)

我对其中的一些处理过程以及粒子4的条目数感到有点惊讶。这可能表明了问题所在。

然后处理粒子6:

Particle 6: Centre (X,Y) = (  0.50,  0.50)
Recurse SW 2: Centre (X,Y) = (  0.25,  0.25)
Recurse SW 1: Centre (X,Y) = (  0.12,  0.12)
Recurse SW 2: Centre (X,Y) = (  0.12,  0.12)
Recurse SW 1: Centre (X,Y) = (  0.06,  0.06)
Recurse SW 2: Centre (X,Y) = (  0.06,  0.06)
Recurse SW 1: Centre (X,Y) = (  0.03,  0.03)
Recurse SW 2: Centre (X,Y) = (  0.03,  0.03)
Recurse SW 1: Centre (X,Y) = (  0.02,  0.02)
Recurse SW 2: Centre (X,Y) = (  0.02,  0.02)
Recurse SW 1: Centre (X,Y) = (  0.01,  0.01)
Recurse SW 2: Centre (X,Y) = (  0.01,  0.01)
Recurse SW 1: Centre (X,Y) = (  0.00,  0.00)
Recurse SW 2: Centre (X,Y) = (  0.00,  0.00)
Recurse SW 1: Centre (X,Y) = (  0.00,  0.00)
Recurse SW 2: Centre (X,Y) = (  0.00,  0.00)
Recurse SW 1: Centre (X,Y) = (  0.00,  0.00)
Recurse SW 2: Centre (X,Y) = (  0.00,  0.00)

从那以后,它变得非常乏味。你需要问的问题是“那一点应该发生什么”?最好也有一个函数来转储四叉树结构。

这基本上表明,您尚未分析要充分添加点的条件。我不清楚为什么在插入位于SE或NE象限时将中心坐标乘以1.5,在SW或NW象限时乘以0.5(也不清楚为什么使用加法+乘法而不是简单的乘法)。

上的测试 width 少于 1e-300 有点令人担忧。假设您使用值调用函数 1.0 ,每次递归时将宽度减半,需要一段时间才能得到如此小的值。

更好的跟踪很可能会报告 x 和 y 以及中心坐标。

John Bollinger 8 年前

我看到你的代码有几个问题。

首先,您几乎重复了相当大的非平凡代码块。这两个区块似乎仅在以下方面有所不同 Particle 它们引用;这要求将其分解为一个helper函数。

其次,考虑以下片段:

else if (x <= center_x && y > center_y) // ! second quadrant
{
    n->nw = quadtree_insert(n->nw, n->p, center_x * 0.5, center_y + center_y * 0.5, width * 0.5);
}

我接受输入 center_x 和 center_y 成为整个区域的方形斑块的中心,以及 width 为该面片的边长。在这种情况下,斑块西北象限的中心为( center_x - width * 0.25 , center_y + width * 0.25 ). 只有在某些特殊情况下,才会与递归调用中的计算相一致。实际上,您可以根据面片中心的坐标来确定面片的宽度,但不能像您尝试的那样直接确定。

类似的情况也适用于所有其他七个递归调用。

第三,考虑一下如果最终得到两个坐标非常相似或更糟的是完全相同的粒子会发生什么。他们可能是模拟中唯一的两个。

第一个粒子最初位于表示整个模拟区域的节点中。当插入第二个时,四叉树被遍历到同一个节点。因此,原始粒子将移动到原始节点区域中新创建的象限,第二个节点的插入过程将继续。但插入之后 再一次 到达原始粒子所在的节点,然后重复该过程。也许它还会重复。再说一遍。

因此,递归没有明确的界限。如果您碰巧得到两个坐标相同的粒子——例如,它们可能被固定在模拟区域的一角——那么您肯定会无休止地递归,最终导致堆栈溢出。然而,即使没有两个粒子具有相同的坐标,也可以想象,两个粒子之间的距离足够近,递归的深度足以导致堆栈溢出。

我怀疑这个问题会因前一个问题而加剧,但这并不取决于这个问题。

解决这个问题的一种方法是合并足够靠近的粒子。这将允许您根据面片宽度在递归深度上设置固定边界。或者,如果递归太深,可以中止。或者,在这种情况下,你可以让它崩溃,就像它已经崩溃一样。

值得一提的是,我认为你 quadtree_insert() 应该看看:

// adjust as needed:
#define MIN_PARTICLE_SEPARATION 1e-300

void quadtree_insert_helper(node *n, Particle *p, double center_x,
        double center_y, double width) {
    width *= 0.5;

    double new_center_x = center_x
            + width * ((p->x_pos <= center_x) ? -0.5 : 0.5);
    double new_center_y = center_y
            + width * ((p->y_pos <= center_y) ? -0.5 : 0.5);
    node **quad;

    if (new_center_x <= center_x && new_center_y <= center_y) {
        //! first quadrant
        quad = &n->sw;
    } else if (new_center_x <= center_x && new_center_y > center_y) {
        //! second quadrant
        quad = &n->nw;
    } else if (new_center_x > center_x && new_center_y <= center_y) {
        //! third quadrant
        quad = &n->se;
    } else {
        //! fourth quadrant
        quad = &n->ne;
    }
    *quad = quadtree_insert(*quad, p, new_center_x, new_center_y, width);
}

node* quadtree_insert(node *n, struct Particle *p, double center_x,
        double center_y, double width) {
    if (n == NULL) {
        n = malloc(sizeof(*n));
        n->is_leaf = 1;
        n->p = p;
        //n->m = 0.1;
        n->sw = NULL;
        n->se = NULL;
        n->nw = NULL;
        n->ne = NULL;
        n->center_x = center_x;
        n->center_y = center_y;
        n->width = width;
    } else if (n->is_leaf && (with <= MIN_PARTICLE_SEPARATION)) {
        // ... merge particles ...
    } else {
        if (n->is_leaf) { //! that is, if the node is not a branch
            quadtree_insert_helper(n, n->p, center_x, center_y, width);
            //! the node is now a branch
            n->p = NULL;
            n->is_leaf = 0;
        }

        quadtree_insert_helper(n, p, center_x, center_y, width);
    }

    return n;
}