c - 在C中逐位递归地求和两个数字

Question

我需要编写递归函数，在第一个函数中，我需要对两个整数逐位求和。我写了一些代码，但它给了我乘以 10 的最终结果。我看到问题发生了，因为当我对前两位数字求和时，我将它们乘以 10。

第二个函数必须计算总和中的进位数。意思是如果两位数字是 3 和 8，那么当我们将它们相加时，我们得到 11，即结果 1，进位 1。简单地说，我只需要计算发生了多少进位。

请注意，我假设两个数字的位数相同。

#include <stdio.h>

int sum(int a, int b)
{
    int temp = (a%10) + (b%10);
    static int mul = 1;

    if(a == 0 && b == 0)
        return 0;
    else
    {
        mul *= 10;
        return (mul*temp) + sum(a/10, b/10);
    }
}

int carry(int a, int b)
{
    static int counter = 0;

    if((a%10) + (b%10) > 9)
        counter++;

    if(a == 0 && b == 0)
        return counter;

    carry(a/10, b/10);

}

int main()
{
    int a = 1941;
    int b = 2282;

    int result = sum(a, b);
    printf("%d\n", result);

    int car = carry(a, b);
    printf("%d\n", car);

    return 0;
}

Answer 1

return (mul*temp) + sum(a/10, b/10);

应该是:

return temp + 10*sum(a/10, b/10);

你不需要静态变量，Static variables用于实现一个全局状态，其生命周期扩展到整个过程。这不是可取的东西，只能在不得已的情况下使用。此外，这绝对不是您在这里需要的，使用静态变量来实现您的解决方案将导致函数仅在第一次调用时起作用。

您应该使用算法的递归属性来聚合结果:

int sum(int a, int b)
{
    if(a == 0 && b == 0) {
        return 0;
    }
    else
    {
        return (a%10) + (b%10) + 10*sum(a/10, b/10);
    }
}

sum(1941, 2282) 将扩展为:

sum(1941, 2282)
1 + 2 + 10*sum(194, 228)
1 + 2 + 10*(4 + 8 + 10*sum(19, 22))
1 + 2 + 10*(4 + 8 + 10*(9 + 2 + 10*sum(1, 2))
1 + 2 + 10*(4 + 8 + 10*(9 + 2 + 10*(1 + 2 + 10*sum(0, 0))
1 + 2 + 10*(4 + 8 + 10*(9 + 2 + 10*(1 + 2 + 10*0)

您应该对 carry 使用相同的方法:

int carry(int a, int b)
{
    if(a == 0 && b == 0) {
        return 0;
    }
    else if((a%10) + (b%10) > 9) {
        return 1 + carry(a/10, b/10);
    }
    else {
        return carry(a/10, b/10);
    }
}

carry(1941, 2282) 将扩展为:

carry(1941, 2282)
0 + carry(194, 228)
0 + 1 + carry(19, 22)
0 + 1 + 1 + carry(1, 2)
0 + 1 + 1 + 0 + carry(0, 0)
0 + 1 + 1 + 0 + 0