Clever Geek Handbook

Is there an equivalent to a nested recursive function in C?

First of all, I know that nested functions are not supported by the C standard.

However, it is often useful in other languages ​​to define a recursive helper function that will use the data provided by the outer function.

Here is an example calculating the number of solutions to the N-queens problem in Python. It's easy to write the same thing in Lisp, Ada, or Fortran, for example, which allows any nested function to be allowed.

def queens(n):
    a = list(range(n))
    u = [True]*(2*n - 1)
    v = [True]*(2*n - 1)
    m = 0

    def sub(i):
        nonlocal m

        if i == n:
            m += 1
        else:
            for j in range(i, n):
                p = i + a[j]
                q = i + n - 1 - a[j]
                if u[p] and v[q]:
                    u[p] = v[q] = False
                    a[i], a[j] = a[j], a[i]
                    sub(i + 1)
                    u[p] = v[q] = True
                    a[i], a[j] = a[j], a[i]

    sub(0)
    return m

Now my question is, is there a way to do something like this in C? I would think of two solutions, using globals or passing data as parameters, but both look pretty unsatisfactory.

There is also a way to write this as an iterative program, but it is clumsy: in fact, I first wrote an iterative Fortran 77 solution for Rosetta Code, and then I wanted to sort out this mess. Fortran 77 does not have recursive functions.

For those wondering, the function controls the NxN board as a permutation [0, 1 ... N-1], so that queens are alone on lines and columns. The function looks for all permutations that are also solutions to the problem, starting by checking the first column (actually checking nothing), then the second, and recursively calling itself only when the first columns i

are in a valid configuration.

+3


source to share


2 answers


Sure. You need to model the ad-hoc environment used by your nested function as static variables at the module level. Declare them above your nested function.



In order not to mess things up, you put it all in a separate module.

+2


source


Editor's Note: This answer was carried over from the question's edit content, it was written in the original poster.

Thanks everyone for the advice. Here is a solution using a struct passed as an argument. This is roughly equivalent to what gfortran and gnat do internally to work with nested functions. By the way, the argument i

can also be passed in the structure.



The inner function is declared static to help optimize the compiler. If it is not recursive, then the code can be integrated into an external function (tested with GCC for a simple example), since the compiler knows that the function will not be called from "outside".

#include <stdio.h>
#include <stdlib.h>

struct queens_data {
    int n, m, *a, *u, *v;
};

static void queens_sub(int i, struct queens_data *e) {
    if(i == e->n) {
        e->m++;
    } else {
        int p, q, j;
        for(j = i; j < e->n; j++) {
            p = i + e->a[j];
            q = i + e->n - 1 - e->a[j];
            if(e->u[p] && e->v[q]) {
                int k;
                e->u[p] = e->v[q] = 0;
                k = e->a[i];
                e->a[i] = e->a[j];
                e->a[j] = k;
                queens_sub(i + 1, e);
                e->u[p] = e->v[q] = 1;
                k = e->a[i];
                e->a[i] = e->a[j];
                e->a[j] = k;
            }
        }
    }
}

int queens(int n) {
    int i;
    struct queens_data s;

    s.n = n;
    s.m = 0;
    s.a = malloc((5*n - 2)*sizeof(int));
    s.u = s.a + n;
    s.v = s.u + 2*n - 1;

    for(i = 0; i < n; i++) {
        s.a[i] = i;
    }

    for(i = 0; i < 2*n - 1; i++) {
        s.u[i] = s.v[i] = 1;
    }

    queens_sub(0, &s);
    free(s.a);
    return s.m;
}

int main() {
    int n;
    for(n = 1; n <= 16; n++) {
        printf("%d %d\n", n, queens(n));
    }
    return 0;
}
+1


source






More articles:


All Articles