c++ - 難読化された C 再帰コード 説明してください

Question

本から再利用を学ぼうとしていますが、明確に説明されていないことがあります。

次のコード

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

呼び出しごとに、n が減少します。したがって、最初の呼び出しで n が正の場合、関数は内部で n 回再度呼び出されてから終了します。

全体として、関数は x と ya に対して算術演算を有限回実行します。

再帰を学習しようとしている場合、factorial() を使用すると、再帰がいかに役立つかを簡単に理解できます。

int factorial(int number) 
{
    int temp;

    if(number <= 1) return 1;

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

コール トレース

factorial(3) = 3 * factorial(2)
= 3 * ( 2 * factorial(1) )
= 3 * ( 2 * ( 1 * factorial(0) ))
= 3 * ( 2 * ( 1 * 1 ) ))
= 6

再帰の簡単な概要:

「再帰の単純なルールとして、次の場合、再帰ルーチンを使用して任意の関数を計算できます。特定の「x」。

したがって、任意の数の階乗の再帰的なプログラムを作成するには、上記の 2 つのルールを使用して再帰的な形式で階乗関数を表現する必要があります。 ）。2. n=1 の場合、1 を返す (終了ステップ)"

Answer 3

理論的に、紙でそれを行う：

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) ->答えは 12 です。