Search code examples
crecursion

Using struct member as recursion seed doesn't terminate when self-referencing >1 of itself

Consider this function: void *r_get_ndim_enum(struct N_dim_array *ctx);. It does some processing with ctx as well as uses a member of ctx as a seed for recursive calls to itself (decrementing until the terminating condition is meet), and at the terminating point, set the member to the original value. Here follows my implementation.

int inc_i = 0;
void *r_get_ndim_enum(struct N_dim_array *ctx) {
    int w,n,np;
    int *arr; 
    void **p;

    w = ctx->size;
    n = ctx->depth;
    np = ctx->depthpl;


    p = calloc(sizeof(void*), n);
    arr = calloc(sizeof(int), w);

    for(int j=0;j<w;++j)
        arr[j] = inc_i++;

    if( np == 0 ) {
        ctx->depthpl = n;
        return arr;
    }

    ctx->depthpl -= 1;
    for(int i=0;i<n;++i)
        p[i] = r_get_ndim_enum(ctx);
        
    return p;
}

This commented out code terminates, however on the contrary self-calling the function twice leads to no termination, something which doesn't get through my head why. Though I do feel an essence of erroneous code in between somewhere, but can't anchor to the right direction.

The code in reference is rapid-prototyped, not the actual one I'm using. The original implementation is close to enclosing the self-call under a loop, NULL checking and the free()ing mechanism. My main goal for not using an extra parameter as seed is so the user need not duplicate something already contained in the struct as an extra parameter to the function.

Please point me to why the second call leads the function not terminating, I can't untangle the trick.

Solution

  • Lets assume that ctx->depthpl == 1 (which means np == 1 is also true).

    Then you do the two statements:

    ctx->depthpl -= 1;
p[0] = r_get_ndim_enum(ctx);

    In the recursive call to r_get_ndim_enum you will have ctx->depthpl == 0 which means the recursion will end. But before that you do

    ctx->depthpl = n;

    So when the current call returns and you call r_get_ndim_enum again, then you will have ctx->depthpl == n.

    A little condensed, and still assuming that ctx->depthpl == 1:

    // Here ctx->depthpl == 1
ctx->depthpl -= 1;
// Here ctx->depthpl == 0
p[0] = r_get_ndim_enum(ctx);
// Here ctx->depthpl == n !
p[0] = r_get_ndim_enum(ctx);

    If n != 0 then you will have infinite recursion.