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

Question

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

However, it's often very useful, in other languages, to define an auxiliary recursive function that will make use of data provided by the outer function.

Here is an example, computing the number of solutions of the N-queens problem, in Python. It's easy to write the same in Lisp, Ada or Fortran for instance, which all allow some kind of nested function.

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 there a way to do something like this in C? I would think of two solutions: using globals or passing data as parameters, but they both look rather unsatisfying.

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

For those who wonder, the function manages the NxN board as a permutation of [0, 1 ... N-1], so that queens are alone on lines and columns. The function is looking for all permutations that are also solutions of the problem, starting to check the first column (actually nothing to check), then the second, and recursively calling itself only when the first i columns are in a valid configuration.

Some C implementations, e.g. GCC, allow nested functions as an extension. But the normal way to do it is pass the data as parameters. — Barmar, Apr 21 '15 at 15:44
possible duplicate of [Is there a a way to achieve closures in C](http://stackoverflow.com/questions/4393716/is-there-a-a-way-to-achieve-closures-in-c) — Matt, Apr 21 '15 at 15:50
@Barmar I have read about this feature of GCC, but I would not use a nonstandard feature like this. I also think the normal way is what you suggest, but I wondered if there was a more clever way. — , Apr 21 '15 at 15:50
If it makes it any easier, you can pass your data as a (pointer to a) structure. The advantage here is cosmetic, but possibly more satisfying to you. — Politank-Z, Apr 21 '15 at 15:51
Thank @Matt I'll have a look at this. There is probably a trick though, since the data must be somewhere, but I guess Ada also uses a trick internally. I'll have to check the assembly output. — , Apr 21 '15 at 15:57
In languages with internal functions like this, the compiler simply creates an extra, hidden parameter that contains references to the variables. — Barmar, Apr 21 '15 at 16:05
possible duplicate of [Functions inside functions in C](http://stackoverflow.com/questions/957592/functions-inside-functions-in-c) — Vineet1982, Apr 21 '15 at 16:06
There's no trick, closures just aren't supported by the c standard. Many compilers support blocks, though, which are similar, and there are also some libraries that add in a form of closures. If your not worried about being thread-safe, you could try the technique used by [strtok](http://www.cplusplus.com/reference/cstring/strtok/) and store the state in static variables. That way you only have to pass in the external state in the first call and not in the recursive calls. — Matt, Apr 21 '15 at 16:07
@Matt By *trick*, I mean the function must have a way to locate data from the outer function: it can be a global, or a parameter. There is another possibility for languages that support closures, namely that the compiler uses a register for this. I just checked, and it's exactly what is done by the Fortran and Ada compilers of GCC, a pointer to a kind of struct is passed in ECX. — , Apr 21 '15 at 20:46

score 2 · Accepted Answer · answered Apr 21 '15 at 16:40

2

Of course. You need to simulate the special environment in use by your nested function, as static variables on the module level. Declare them above your nested function.

To not mess things up, you put this whole thing into a separate module.

answered Apr 21 '15 at 16:40

Will Ness

70,110
9
98
181

Yes, I shouldn't even have asked, though I could have missed a feature of C, as I'm not an expert. There is obviously no magick in closures, data must be accessible by a pointer which, in assembler, must be either a constant (=global variable), or stack based (=parameter) or register based. gfortran and gnat use the last option. I have never thought to much about implementation of closures, but once one looks at what assembler may look like, it's much easier to find out. – Apr 21 '15 at 20:53
@Jean-ClaudeArbaut well, for closures you really ought to pack all the relevant stuff into some structure and pass it around, by reference of course. *Explicate* what these other languages are doing implicitly. The data is spread on the stack during recursion, you just put it on the heap. What I described above is the most basic approach, and incidentally, refactoring will be hard. – Will Ness Apr 21 '15 at 21:01
@Jean-ClaudeArbaut myself, I'm coming more from the Lisp world; full closures there are quite involved (check out the ["funarg problem"](https://en.wikipedia.org/wiki/Funarg_problem), leading to the necessity to maintain a *tree* of stack frames, not just a list). Hopefully you don't need the full sophistication. – Will Ness Apr 21 '15 at 21:06

score 1 · Answer 2 · answered Aug 04 '15 at 17:54

Editor's Note: This answer was moved from the content of a question edit, it is written by the Original Poster.

Thanks all for the advice. Here is a solution using a structure passed as an argument. This is roughly equivalent to what gfortran and gnat do internally to deal with nested functions. The argument i could also be passed in the structure, by the way.

The inner function is declared static so as to help compiler optimizations. If it's not recursive, the code can then be integrated to the outer function (tested with GCC on a simple example), since the compiler knows the function will not be called from the "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;
}

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

2 Answers2