c++ - 混淆的C递归代码请解释

Question

我正在尝试从一本书中学习recursion，但是有些东西对我来说解释得不够清楚。

以下代码

int f(int n, int x, int y)
{
if(n==0) return x+y;
if(y==0) retun x;
return f(n-1,f(n,x,y-1),f(n,x,y-1)+y);
}

如果我调用 f(1,2,2) 会发生什么；

任何帮助解释和感谢

Answer 1

int f(int n, int x, int y)
{
  int result;

  if(n==0) {
    printf("f(%d, %d, %d) -> %d\n", n, x, y, x+y);
    return x+y;
  }
  if(y==0) {
    printf("f(%d, %d, %d) -> %d\n", n, x, y, x);
    return x;
  }

  printf("recursing for f(%d, %d, %d)...\n", n, x, y);
  result = f(n-1,f(n,x,y-1),f(n,x,y-1)+y);
  printf("f(%d, %d, %d) -> %d\n", n, x, y, result);
  return result;
}

您的代码没有被混淆。你指的是你没有发布的东西吗？

Answer 2

理论上并在纸上做：

f(1,2,2)->return f(1-1,f(1,2,2-1),f(1,2,2-1)+2) 然后我们做内部

两者都是相同的 f(1,2,2-1) -> 再次返回 f(0,f(1,2,1-1),f(1,2,1-1)+1) 内部

同样，两者都是相同的-> return 2 (x=2); 所以我们回去

返回 f(0, f(1,2,1-1) -> 2, f(1,2,1-1) ->2+1) -> f(0, 2, 3) -> 返回 2+ 3(x+y);

再次返回 f(0, f(1,2,2-1) -> 5, f(1,2,2-1) ->5+2) -> return 5+7(x+y) -> The答案是 12；

Answer 3

每次调用时，n 都会递减。因此，如果 n 在第一次调用时为正，则该函数将在内部再次调用 n 次，然后退出。

总体而言，该函数对 x 和 ya 进行有限次数的算术运算。

如果你想学习递归，factorial() 更容易理解递归的用处。

int factorial(int number) 
{
    int temp;

    if(number <= 1) return 1;

    temp = number * factorial(number - 1);
    return temp;
}

呼叫跟踪

阶乘(3) = 3 * 阶乘(2)
= 3 * ( 2 * 阶乘(1) )
= 3 * ( 2 * ( 1 * 阶乘(0) ))
= 3 * ( 2 * ( 1 * 1 ) ))
= 6

递归的简单概述：

“作为一个简单的递归规则，任何函数都可以使用递归例程来计算，如果： 1. 函数可以用它自己的形式表达。2. 存在一个终止步骤，即 f(x) 已知的点一个特定的“x”。

因此，要为任意数的阶乘编写递归程序，我们必须使用上述 2 条规则以递归形式表示阶乘函数： 1. fact(n) = fact(n-1)*n（阶乘的递归定义）。2.如果n=1，返回1（终止步骤）”