使用递归的解决方案数量

您的实现很糟糕，因为您忽略了递归调用的返回值recurse，易于修复，只需返回返回值的相加即可：

#include <stdio.h>

int recurse(int x, int y, int z, int w, int n) {
  int value = x + 5 * y + 20 * z + 50 * w;
  if (value == 300) {
    return n + 1;
  } else if (value > 300) {
    return n;
  }

  return recurse(x + 1, y, z, w, n) + recurse(x, y + 1, z, w, n) +
         recurse(x, y, z + 1, w, n) + recurse(x, y, z, w + 1, n);
}

int main(void) {
  printf("Answer: %d", recurse(0, 0, 0, 0, 0));
}

但是你的实现需要时间......很多时间......来计算结果。

Antti Haapala - 好吧，我使结束条件更紧，然后开始测试。62 耗时 1.32 秒，64 2.3 秒，66 4.039 秒完成。每添加 2 个，该比率为 1.75。所以最低限度，那些 300 将需要 1.75 ^ ((300 - 66) / 2) * 4.039 秒 .. 所以这就是下落

因为您没有将迭代实现转换为正确的递归函数。您的函数计算排列数而不是组合数。换句话说，您可以按多少种不同的顺序提供物品，最终得到 300 个。

每个迭代循环都可以转换为尾递归函数，C 标准不要求编译器优化尾递归函数以避免堆栈溢出，但大多数编译器都有这种优化。

这很难解释如何将函数从迭代转换为递归，但作为规则，每个 for 循环都需要模拟函数递归。如您所见，我需要创建四个函数来实现相同的行为。

剧透，这个答案给出了代码解决方案：

#include <stdio.h>

static int magic(int a, int b, int c, int d) {
  return a + b * 5 + c * 20 + d * 50;
}

static int recur_d(int a, int b, int c, int d, int n, int max) {
  int ret = magic(a, b, c, d);
  if (ret >= max) {
    if (ret == max) {
      // printf("%d %d %d %d\n", a, b, c, d);
      return n + 1;
    }
    return n;
  }
  return recur_d(a, b, c, d + 1, n, max);
}

static int recur_c(int a, int b, int c, int n, int max) {
  if (magic(a, b, c, 0) > max) {
    return n;
  }
  return recur_c(a, b, c + 1, recur_d(a, b, c, 0, n, max), max);
}

static int recur_b(int a, int b, int n, int max) {
  if (magic(a, b, 0, 0) > max) {
    return n;
  }
  return recur_b(a, b + 1, recur_c(a, b, 0, n, max), max);
}

static int recur_a(int a, int n, int max) {
  if (magic(a, 0, 0, 0) > max) {
    return n;
  }
  return recur_a(a + 1, recur_b(a, 0, n, max), max);
}

static int iter(int max) {
  int n = 0;
  for (int a = 0; magic(a, 0, 0, 0) <= max; a++) {
    for (int b = 0; magic(a, b, 0, 0) <= max; b++) {
      for (int c = 0; magic(a, b, c, 0) <= max; c++) {
        for (int d = 0; magic(a, b, c, d) <= max; d++) {
          if (magic(a, b, c, d) == max) {
            // printf("%d %d %d %d\n", a, b, c, d);
            n++;
          }
        }
      }
    }
  }
  return n;
}

int main(void) { printf("%d %d\n", iter(300), recur_a(0, 0, 300)); }

注意：我评论了printf()以避免长输出。