c - 我在 C 中的递归函数的输出是什么

Question

考虑以下带有两个参数的递归 C 函数。

unsigned int foo(unsigned int n, unsigned int r)
{ 
     if (n > 0)
         return (n % r) + foo(n / r, r); 
     else 
         return 0; 
}

调用 foo(512,2) 时函数 foo 的值是多少？

Answer 1

这段代码，实际上是一个递归。

跟随回报发生：

If n == 0; return 0;

If n == 1; return 1+foo(0,2)

If n == 2; return 0 + foo(1,2);

If n == 4; return 0 + foo(2,2);

  ...

if n == 2^n  return 0 + foo(0+foo(z^n-1,2));


....


So foo(512,2) == foo (2^n,2) == 0+f(1,2) == 1 +f(0,2) = 1;

它返回 1。

Answer 2

您的结果将是 1。这是发生的情况：

1. 第一次调用：n = 512，r = 2，n % r = 0；来电foo (256, 2)
2. 第二次调用：n = 256, r= 2, n % r = 0; 来电foo (128, 2)
3. 第三次调用：n = 128，r = 2，n % r = 0；来电foo (64, 2)
4. 第四次调用：n = 64，r = 2，n % r = 0；来电foo (32, 2)
5. 第五次调用：n = 32，r = 2，n % r = 0；来电foo (16, 2)
6. 第六次调用：n = 16，r = 2，n % r = 0；来电foo (8, 2)
7. 第七次调用：n = 8，r = 2，n % r = 0；来电foo (4, 2)
8. 第八次调用：n = 4，r = 2，n % r = 0；来电foo (2, 2)
9. 第九次调用：n = 2，r = 2，n % r = 0；来电foo (1, 2)
10. 第十次调用：n = 1，r = 2，n % r = 1；来电foo (0, 2)
11. 第十一次调用：n = 0，r = 2；返回 0
12. 第十次调用返回 1 + 0 = 1
13. 第九次调用和后续调用都返回 0 + 1 = 1

展开完成，函数返回 1。