C 中是否有等同于嵌套递归函数的函数？

Question

首先，我知道C标准不支持嵌套函数。

但是，在其他语言中，定义一个将使用外部函数提供的数据的辅助递归函数通常非常有用。

这里举个例子，计算Python中N-queens problem的解数。例如，在 Lisp、Ada 或 Fortran 中很容易编写相同的代码，它们都允许某种嵌套函数。

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

现在我的问题是：有没有办法在 C 语言中做类似的事情？我会想到两种解决方案：使用全局变量或将数据作为参数传递，但它们看起来都不太令人满意。

还有一种方法可以将其写成迭代程序，但它是clumsy:actually，我先在Fortran 77中为Rosetta Code编写了迭代解决方案，然后想整理一下这个烂摊子。 Fortran 77 没有递归函数。

对于那些想知道的人，该函数将 NxN 板管理为 [0, 1 ... N-1] 的排列，因此皇后在行和列上都是单独的。该函数正在寻找所有也是问题解决方案的排列，开始检查第一列（实际上没有什么可检查的），然后是第二列，并且仅当第一个 i 列处于有效状态时才递归调用自身配置。

Answer 1

当然可以。您需要模拟嵌套函数使用的特殊环境，如模块级别的 static variables。在嵌套函数之上声明它们。

为了不把事情搞砸，你把这整件事放到一个单独的模块中。

Answer 2

编者注：此答案从问题编辑的内容中移出，由原帖者撰写。

谢谢大家的建议。这是一个使用作为参数传递的结构的解决方案。这大致相当于 gfortran 和 gnat 在内部处理嵌套函数所做的工作。顺便说一下，参数 i 也可以在结构中传递。

内部函数被声明为静态的，以帮助编译器优化。如果它不是递归的，则可以将代码集成到外部函数（在一个简单示例中使用 GCC 进行测试），因为编译器知道不会从 "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;
}

C 中是否有等同于嵌套递归函数的函数？

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

c

python

recursion

nested

code-translation