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 作为更改量。当我进入函数方式时，没有一个基本情况得到满足，因此递归开始发挥作用。对于第一次调用，金额保持不变，面额减少 1，因此我们回到函数中，将 25 和 3 （4-1） 作为我们的新参数。在面额减少到0之前，不会满足任何基本情况（因为金额永远不会改变）。此时，我们将返回 0。这就是我迷路的地方。我看到0通过所有以前的调用被发送回去，所以最终结果是0，但这对我来说听起来不对。在尝试跟踪第二个调用时，我遇到了同样的问题，除了不是通过调用发送回0，而是1。显然，我对这种递归的看法是非常错误的。有人可以向我解释这个递归实例是如何工作的吗？

Answer 1

代码进行了两次调用，因为它将问题分成两个部分，每个部分都以相同的方式解决。每个部分在某种意义上比原始问题更简单，并且使用相同的方法来解决每个单独的问题。正如其他人所指出的，可能存在两个以上部分的情况。

您可能已经看到过一个调用的示例，其中问题的一部分已解决，而单个递归调用解决了问题的“剩余部分”。

Answer 2

跟踪递归算法的一种方法是在递归函数的顶部放置一个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);
}