请问这个递归函数return如何求出正确答案呢？

Question

我想知道这个函数 returns 4 的正确答案是什么，它在每次函数调用自身时重置 res 变量。 num = 2367319

int func(int num)
{
    int res = 0;
    if (num > 0)
        res = (num % 10 % 3 == 0 ? 1 : 0) + func(num / 10);

    return res;
}

Answer 1

res 不是 "reset"。而是为每个递归调用创建一个名为 res 的新局部变量。

我建议您添加一些 printf() 语句以了解此功能的工作原理。

Answer 2

res等于能被3整除的位数，只要num大于0，总会得到一个合适的值。

Answer 3

对于初学者来说，函数的声明和实现是错误的。

函数参数的类型为 int。因此，用户可以提供一个负数，并等待该数的多少位数可以被 3 整除。但是函数 returns 0。出现一个问题：如何处理负数？要再写一个函数吗？

第二个问题是该函数无法处理 long int 和 long long int 类型的整数。我们是否需要为这些有符号整数类型编写单独的函数？

该函数使用了冗余变量 res.

可以按照下面的演示程序所示的方式声明和实现..

#include <stdio.h>

unsigned int func( long long int n )
{
    const long long int Base = 10;

    return n == 0 ? 0 : ( n % Base % 3 == 0 ) + func( n / Base );  
}

int main(void) 
{
    printf( "%d : %u\n", 2367319, func( 2367319 ) );
    printf( "%d : %u\n", -2367319, func( -2367319 ) );

    return 0;
}

程序输出为

2367319 : 4
-2367319 : 4

该功能如何运作？

如果 n 等于 0 则函数 returns 0.

    return n == 0 ? 0 : ( n % Base % 3 == 0 ) + func( n / Base );  
           ^^^^^^   ^^

否则，如果数字的最后一位 n % Base（除以 10 的余数）可被 3 整除，则此表达式

    return n == 0 ? 0 : ( n % Base % 3 == 0 ) + func( n / Base );  
                          ^^^^^^^^^^^^^^^^^^

产量 1（真）。否则它会产生 0。所以该函数以这种方式递归地计算可被3整除的位数。

例如，让我们考虑数字 2367319。

表达式 2367319 % 10 产生数字 9。 9 % 3 (2367319 % 10 % 3) 等于0。所以表达式

2367319 % 10 % 3 == 0

产量 1.

现在该函数使用编号 2367319 / 10 和编号 236731 调用自身。并重复这个新号码的最后一位的操作。在这种情况下，表达式

236731 % 10 % 3 == 0

计算结果为 0（假）。

等等。函数调用的所有结果被累加并返回。

事实上你会有

(2367319 % 10 % 3 == 0) + (236731 % 10 % 3 == 0) + (23673 % 10 % 3 == 0) +...+ 0

         1              +         0              +        1              +...+ 0

Answer 4

简而言之，当函数被调用时，它的所有局部变量都在 stack 上创建（即堆栈指针根据使用的局部变量的数量递增）。在函数退出时，堆栈指针递减相同的量。

考虑下面的例子，函数 foo() 和一些字节的局部变量调用 bar() 和一些其他字节的局部变量。（为了简单起见，我从堆栈中排除了函数 return 地址）

 /*stack growth in this direction ---->*/


 foo()-------+
             |
    /*foo code execution */
             | 
           bar()----------+
                          |
                  /* bar() Code execution */
                          | 
             +------------+
             |
|------------+

当函数被调用时，堆栈在函数退出时扩展和收缩。

在递归函数的情况下 bar() 恰好是 foo() 一次又一次。但是每次函数调用都会分配新的堆栈位置。

因此在你的情况下 res 在不同的堆栈位置被设置为零，即使它看起来是相同的变量名。

请问这个递归函数return如何求出正确答案呢？

How does this recursive function return the correct answer?

c

function

recursion

definition