関数内の計算の仕方について

Question

このプログラムの答えは128になるのですが、どのような計算をして128になるのかがわからないです。
#include <stdio.h>
int hoge(int a){
if( 2 <= a ){
int x = hoge(a-1);
return x * x * hoge(a-2);
} else {
return 2;
}
}
void main(){
int x = hoge( 3 );
printf("%d", x);
}

Comments

[DreamTheater]

コードはマークダウンの<code>内に書きましょう。
コードがインデントされていないのならその際インデントしましょう。

Answer 1

関数の中で同じ関数が呼び出される、いわゆる再起呼び出しと呼ばれるものです。
この手のは順番に追いかけてゆきます。

まずは、mainの中でhoge(3);が呼び出されます。

hoge(3)が開始されます。引数は3なので、a=3です。
if( 2 <= a )は2<=3なので、真のルートに進みます。
hoge(a-1);で再びhoge()が呼び出されます。今度はa-1なのでhoge(2)です。

hoge(2)が開始されます。引数は2なので、a=2です。
if( 2 <= a )は2<=2なので、真のルートに進みます。
hoge(a-1);で再びhoge()が呼び出されます。今度はa-1なのでhoge(1)です。

hoge(1)が開始されます。引数は1なので、a=1です。
if( 2 <= a )は2<=1なので、偽のルートに進みます。
return 2なので、返り値は2になります。

hoge(2)に制御が戻ってきます。
hoge(1)の返り値は2だったので、x=2となり、次に進みます。
x * x * hoge(a-2);に、またhoge()が出てくるので、呼び出されます。
今度は、a-2なので、hoge(0)です。

hoge(0)が開始されます。引数は0なので、a=0です。
if( 2 <= a )は2<=0なので、偽のルートに進みます。
return 2なので、返り値は2になります。

hoge(2)に制御が戻ってきます。
hoge(0)の返り値は2だったので、
x * x * hoge(a-2);は、2 * 2 * 2となります。
それが返されるので、hoge(2)の返り値は8となります。

hoge(3)に制御が戻ってきます。
hoge(2)の返り値は8だったので、x=8となり、次に進みます。
x * x * hoge(a-2);に、またhoge()が出てくるので、呼び出されます。
今度は、a-2なので、hoge(1)です。

hoge(1)が開始されます。引数は1なので、a=1です。
if( 2 <= a )は2<=1なので、偽のルートに進みます。
return 2なので、返り値は2になります。

hoge(3)に制御が戻ってきます。
hoge(1)の返り値は2だったので、
x * x * hoge(a-2);は、8 * 8 * 2となります。
それが返されるので、hoge(8)の返り値は128となります。

mainに制御が返ってきます。
hoge(3)の返り値は128だったので、x=128となり、次に進みます。
printfにより、xの128が表示されます。

Comments

[Japanise]

下から18行目のhoge(3)に制御が戻ってくるのはどこから戻ってきたのか理解できていないので教えてほしいです。

[Japanise]

とてもわかりやすく理解することができました！
ありがとうございました！

[amiya]

トレースですので、全てその前の行から処理は移動してきます。

hoge(3)に制御が戻ってきます。
hoge(2)の返り値は8だったので…

のところであれば、その直前の

hoge(2)に制御が戻ってきます。
(略)
それが返されるので、hoge(2)の返り値は8となります。

から戻ってきます。

[Japanise]

とてもわかりやすい解説ありがとうございます。

Answer 2

自分でもよく分からなかったのでhoge(n) n=0 から n=5まで計算してみましたのでご参考までに。

結論：hoge(n) = hoge(n-1)^2 * hoge(n-2)

手作業で計算する場合
hoge(0)=2 と　hoge(1)=2　は関数内から固定で分かります。
hoge(2) = hoge(1)^2 * hoge(0) なので当てはめると、
hoge(2) = 2 * 2 * 2 = 8
hoge(3) = hoge(2)^2 * hoge(1) なので同様に計算すると、
hoge(3) = 8 * 8 * 2 = 128

以降順番にhoge(0)～hoge(5)まで計算出来ました。
但しn=6以降は桁が大きすぎてlong long型でも表示しきれません。

hoge(0) = 2
hoge(1) = 2
hoge(2) = 8
hoge(3) = 128
hoge(4) = 131072
hoge(5) = 2199023255552

hoge(0) = 2
hoge(1) = 2
hoge(2) = 2 * 2 * 2
hoge(3) = 8 * 8 * 2
hoge(4) = 128 * 128 * 8
hoge(5) = 131072 * 131072 * 128

#include <stdio.h>

int count;

long long   hoge(long long  a) {

  long long  result = 0;
  if (2 <= a) {
    long long x = hoge(a - 1);
    result = x * x * hoge(a - 2);
  } else {
    result = 2;
  }
  count++;
  printf("%s %d %s %lld %s %lld %s %lld \n", "count:", count, " a=", a, " x=", result,
         " result=", result);
  return result;
}
int main() {
  int start_x = 0;
  int end_x = 5;

  for (int i = start_x; i <= end_x; i++) {
    count = 0;
    printf("%s %d %s %lld\n\n","hoge(",i,")=", hoge(i));
  }
  getchar();
  return 0;
}

count: 1  a= 0  x= 2  result= 2
hoge( 0 )= 2

count: 1  a= 1  x= 2  result= 2
hoge( 1 )= 2

count: 1  a= 1  x= 2  result= 2
count: 2  a= 0  x= 2  result= 2
count: 3  a= 2  x= 8  result= 8
hoge( 2 )= 8

count: 1  a= 1  x= 2  result= 2
count: 2  a= 0  x= 2  result= 2
count: 3  a= 2  x= 8  result= 8
count: 4  a= 1  x= 2  result= 2
count: 5  a= 3  x= 128  result= 128
hoge( 3 )= 128

count: 1  a= 1  x= 2  result= 2
count: 2  a= 0  x= 2  result= 2
count: 3  a= 2  x= 8  result= 8
count: 4  a= 1  x= 2  result= 2
count: 5  a= 3  x= 128  result= 128
count: 6  a= 1  x= 2  result= 2
count: 7  a= 0  x= 2  result= 2
count: 8  a= 2  x= 8  result= 8
count: 9  a= 4  x= 131072  result= 131072
hoge( 4 )= 131072

count: 1  a= 1  x= 2  result= 2
count: 2  a= 0  x= 2  result= 2
count: 3  a= 2  x= 8  result= 8
count: 4  a= 1  x= 2  result= 2
count: 5  a= 3  x= 128  result= 128
count: 6  a= 1  x= 2  result= 2
count: 7  a= 0  x= 2  result= 2
count: 8  a= 2  x= 8  result= 8
count: 9  a= 4  x= 131072  result= 131072
count: 10  a= 1  x= 2  result= 2
count: 11  a= 0  x= 2  result= 2
count: 12  a= 2  x= 8  result= 8
count: 13  a= 1  x= 2  result= 2
count: 14  a= 3  x= 128  result= 128
count: 15  a= 5  x= 2199023255552  result= 2199023255552
hoge( 5 )= 2199023255552