C - 如何跟踪这个递归？

Question

我一直在网上查看递归(C 语言)的示例，试图更好地理解它及其工作原理。一般来说，我可以毫无问题地追踪一些基本的递归问题(例如阶乘问题)，但我发现了这个问题，并且完全不知道如何追踪它。

这个想法是让用户输入找零金额，然后通过使用递归，打印出可以进行该找零金额的方式数量。代码如下:

#include <stdio.h>

#define NUM_DENOMS 4

int ways(int amount, int denomination);

int main()
{
    //Declarations & initializations
    int userChange = 0;

    //Get user input
    printf("Enter an amount you wish to get change for (in cents):\n");// get the amount of change in from the user
    scanf("%d", &userChange);

    //Function call... pass user's input and denomination values (ints) as parameters
    printf("%d cents can be made in %d different ways\n", userChange, ways(userChange, NUM_DENOMS));

    return 0;
}

//Function to find # of ways to make change for user's amount
int ways(int amount, int denomination)
{
    static int validAmounts[NUM_DENOMS] = {1, 5, 10, 25};

    if(denomination<=0) //if denomination is invalid
    {
        return 0;
    }
    if((amount == 1) || (amount == 0)) //base case: only 1 combination
    {
        return 1;
    }
    else if(amount < 0) //can't have negative amount of money
    {
        return 0;
    }
    else //if denomination is valid and user's change > 1
    {
        return ways(amount, denomination-1) + ways(amount-validAmounts[denomination-1], denomination);
    }
}

显然这是递归的常见应用。但我无法理解这个递归是如何工作的。对我来说最突出的是同一行有 2 个递归调用。我从未见过以这种方式应用递归。

我确实尝试追踪它，但我的结果肯定是错误的:

假设我输入 25 作为找零金额。当我进入 ways 函数时，没有一个基本情况得到满足，因此递归开始发挥作用。对于第一次调用，金额保持不变，面额减少 1，因此我们返回函数，将 25 和 3 (4-1) 作为新参数。在面额减少到0之前，所有基本情况都不会满足(因为金额永远不会改变)。此时，我们返回 0。这就是我迷路的地方。我看到 0 通过之前的所有调用发回，因此最终结果是 0，但这对我来说听起来不对。当我尝试跟踪第二个调用时，我遇到了同样的问题，只不过通过调用发回的不是 0，而是 1。显然，我对这种递归的看法是严重错误的。有人可以向我解释一下这个递归实例实际上是如何工作的吗？

Answer 1

跟踪递归算法的一种方法是将 printf 放在递归函数的顶部。 printf 应该打印出函数的参数。暂时添加更多参数以便为自己提供有关递归正在执行的操作的附加信息也是一个好主意。最常见的附加参数是深度参数，它显示已进行的嵌套调用次数。对于这个特定问题(有两个递归调用)，我将添加一个附加参数来标识正在跟踪哪个调用。

考虑到这一点，这是修改后的代码。我建议从简单的输入开始，例如 5，以了解递归的工作原理。

#include <stdio.h>

#define NUM_DENOMS 4

int ways(int amount, int denomination, int left, int depth);

int main( void )
{
    int userChange = 0;

    printf("Enter an amount you wish to get change for (in cents):\n");
    scanf("%d", &userChange);

    printf("%d cents can be made in %d different ways\n", userChange, ways(userChange, NUM_DENOMS, 'M', 0));

    return 0;
}

int ways(int amount, int denomination, int left, int depth)
{
    static int validAmounts[NUM_DENOMS] = {1, 5, 10, 25};

    printf( "%2d %d %c %2d\n", amount, denomination, left, depth );

    if(denomination <= 0 || amount < 0)
        return 0;

    if((amount == 1) || (amount == 0))
        return 1;

    return ways(amount, denomination-1, 'L', depth+1) + ways(amount-validAmounts[denomination-1], denomination, 'R', depth+1);
}