c - 循环内递归

Question

所以我的教授布置了一份关于递归的作业，问题如下

问题1:您将获得用于称重负载的秤。左侧有一 block 已知重量 W < 2N 的石头。您拥有一组 N 个不同的重量，分别称重 1、2、4、...、2^N-1 质量单位。确定有多少种可能的方式将一些重物放置在天平的两侧，以使其平衡(使它们处于平衡状态)。

也给出了解决方案

#include <stdio.h>

int N;

int no_ways(int W, int index) {
    if (!W)
        return 1;
    if (index == N)
        return 0;

    int ans = 0, i;
    for (i = 0; i * (1 << index) <= W; i++)
        ans += no_ways(W - i * (1 << index), index + 1);

    return ans;
}

void main() {
    int W;
    scanf("%d%d", &N, &W);

    printf("%d\n", no_ways(W, 0));
    return 0;
}

在这里，我了解了如何测试基本条件，但是我无法理解 for 循环内的递归调用以及每个递归调用中索引值的不同。

有什么更简单的方法或帮助理解这个程序吗？

PS:我是递归新手，这对我来说似乎太复杂了，无法理解

Answer 1

为了理解递归，我建议您选择一些非常小的输入值并以笔和纸的方式将其可视化:

// Example Input:
W = 2, N = 2

// first call
no_ways(2, 0)
// loop0: i = 0 to 2

    // first recursive call
    no_ways(2, 1)
    // loop1: i = 0 to 1

        no_ways(2, 2)
        = 0 (index == N)

        no_ways(0, 2)
        = 1 (W == 0)

    = 1 (sum of recursions in loop1)

    no_ways(1, 1)
    // loop2: i = 0 to 0

        no_ways(1, 2)
        = 0 (index == N)

    = 0 (sum of recursions in loop2)

    no_ways(0, 1)
    = 1 (W == 0)

= 2 (sum of recursions in loop0)

正如您所看到的，即使输入非常小，递归调用的顺序和结果的集合也会变得相当复杂，但我希望您仍然可以阅读。

正如 David C. Rankin 在评论中提到的，这个算法并不是很好。对于任何 W > 0，它始终会达到 N 的递归深度(嵌套调用数)，即使可以在特定递归路径出现时及早检测到。无法产生任何非零结果。

该算法的编写方式是，随着 index 的增加，只有可除以 2^index 的 W 值是可解的。因此(例如)第一个函数调用的任何递归(其中 W 是奇数)绝不会导致除 0 以外的任何结果，因为所有 index > 0 的权重> 是偶数权重。