アルゴリズムとデータ構造 補足資料 3-2 「関数 fact の再帰呼出」

アルゴリズムとデータ構造 補足資料 3-2

「関数 fact の再帰呼出」

横浜国立大学 理工学部 数物・電子情報系学科

int fact(int n) {

int fn;

printf(“Call :fact(%d)\n”, n);

if(n>0)

fn=n*fact(n-1);

else fn=1;

printf(“Return:fact(%d)==%d\n”,n,fn);

return fn;

}

int 型 (32bit) 仮引数

n

（自動）変数 fn

int 型 (32bit)

return

printf(“Call :fact(%d)\n”, n);

printf(“Return:fact(%d)==%d\n”,n,fn);

n>0 ?

fn=1; fn=n*fact(n-1);

yes no

void 型 (0bit) 仮引数 : なし

（自動）変数

k 3

int 型 (32bit)

printf(“fact(%d)=%d\n”, k, fact(k));

return int main(void)

{

int k=3;

printf(“fact(%d)=%d\n”, k, fact(k));

return 0;

}

void 型 (0bit) 仮引数 : なし

（自動）変数

k 3

int 型 (32bit)

printf(“fact(%d)=%d\n”, 3, fact(3));

return int main(void)

{

int k=3;

printf(“fact(%d)=%d\n”, k, fact(k));

return 0;

}

main から実行開始！

fact(3) を 呼び出し

fn

return

printf(“Call :fact(%d)\n”, n);

printf(“Return:fact(%d)==%d\n”,n,fn) n>0 ?

fn=1; fn=n*fact(n-1);

no yes

n 3

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=1; fn=n*fact(n-1);

no yes

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(3-1);

yes

n 3

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

fact(2)

fn

printf(“Call :fact(%d)\n”, n);

printf(“Return:fact(%d)==%d\n”,n,fn) n>0 ?

fn=1; fn=n*fact(n-1);

no yes

2

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

n 3

fact(2)

fact(2)

fn

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=1; fn=2*fact(2-1);

no yes

n 2

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

2

fact(1)

fact(1)

fn

printf(“Call :fact(%d)\n”, n);

printf(“Return:fact(%d)==%d\n”,n,fn) n>0 ?

fn=1; fn=n*fact(n-1);

no yes

n 1

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

n 3

fact(2)

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

n 2

fact(1)

fact(1)

fn

printf(“Call :fact(%d)\n”, 1);

printf(“Return:fact(%d)==%d\n”,n,fn) 1>0 ?

fn=1; fn=1*fact(1-1);

no yes

n 1

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

2

fact(1)

fact(1)

fn

return

printf(“Call :fact(%d)\n”, 1);

printf(“Return:fact(%d)==%d\n”,n,fn) 1>0 ?

fn=1*fact(0);

yes

n 1

t(0 fac

fact(0) )

fn

printf(“Call :fact(%d)\n”, n);

printf(“Return:fact(%d)==%d\n”,n,fn) n>0 ?

fn=1; fn=n*fact(n-1);

no yes

n 0

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

n 3

fact(2)

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

n 2

fact(1)

fact(1)

fn

return

printf(“Call :fact(%d)\n”, 1);

printf(“Return:fact(%d)==%d\n”,n,fn) 1>0 ?

fn=1*fact(0);

yes

n 1

t(0 fac

fact(0) )

fn

printf(“Call :fact(%d)\n”, 0);

printf(“Return:fact(%d)==%d\n”,n,fn) 0>0 ?

fn=1; fn=n*fact(n-1);

no yes

n 0

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

2

fact(1)

fact(1)

fn

return

printf(“Call :fact(%d)\n”, 1);

printf(“Return:fact(%d)==%d\n”,n,fn) 1>0 ?

fn=1*fact(0);

yes

n 1

t(0 fac

fact(0) )

fn 1

printf(“Call :fact(%d)\n”, 0);

printf(“Return:fact(%d)==%d\n”,n,fn) 0>0 ?

fn=1;

no

n 0

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

n 3

fact(2)

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

n 2

fact(1)

fact(1)

fn

return

printf(“Call :fact(%d)\n”, 1);

printf(“Return:fact(%d)==%d\n”,n,fn) 1>0 ?

fn=1*fact(0);

yes

n 1

t(0 fac

fact(0) )

fn 1

printf(“Call :fact(%d)\n”, 0);

printf(“Return:fact(%d)==%d\n”,0,1) 0>0 ?

fn=1;

no

n 0

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

2

fact(1)

fact(1)

fn

return

printf(“Call :fact(%d)\n”, 1);

printf(“Return:fact(%d)==%d\n”,n,fn) 1>0 ?

fn=1*fact(0);

yes

n 1

fact(0)

fn 1

printf(“Call :fact(%d)\n”, 0);

printf(“Return:fact(%d)==%d\n”,0,1) 0>0 ?

fn=1;

no

n 0

fact(0)=1

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

n 3

fact(2)

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

n 2

fact(1)

fact(1)

fn

return

printf(“Call :fact(%d)\n”, 1);

printf(“Return:fact(%d)==%d\n”,n,fn) 1>0 ?

fn=1* 1;

yes

n 1

fact(0)

fn 1

printf(“Call :fact(%d)\n”, 0);

printf(“Return:fact(%d)==%d\n”,0,1) 0>0 ?

fn=1;

no

n 0

fact(0)=1

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

2

fact(1)

fact(1)

fn 1

printf(“Call :fact(%d)\n”, 1);

printf(“Return:fact(%d)==%d\n”,n,fn) 1>0 ?

fn= 1;

yes

n 1

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

n 3

fact(2)

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

n 2

fact(1)

fact(1)

fn 1

printf(“Call :fact(%d)\n”, 1);

printf(“Return:fact(%d)==%d\n”,1,1) 1>0 ?

fn= 1;

yes

n 1

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

fact(2)

fn

return

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2*fact(1);

yes

2

fact(1)

fn 1

printf(“Call :fact(%d)\n”, 1);

printf(“Return:fact(%d)==%d\n”,1,1) 1>0 ?

fn= 1;

yes

n 1

fact(1)=1

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

n 3

fact(2)

fact(2)

fn 2

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,n,fn) 2>0 ?

fn=2;

yes

n 2

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

fact(2)

fn 2

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,2,2) 2>0 ?

fn=2;

yes

2

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*fact(2);

yes

n 3 fact(2)

fn 2

printf(“Call :fact(%d)\n”, 2);

printf(“Return:fact(%d)==%d\n”,2,2) 2>0 ?

fn=2;

yes

n 2

fact(2)=2

fn

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=3*2;

yes

fn 6

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,n,fn) 3>0 ?

fn=6;

yes

n 3

fn 6

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,3,6) 3>0 ?

fn=6;

yes

6

fn 6

return

printf(“Call :fact(%d)\n”, 3);

printf(“Return:fact(%d)==%d\n”,3,6) 3>0 ?

fn=6;

yes

n 3

6

main 関数へ

void 型 (0bit) 仮引数 : なし

（自動）変数

k 3

int 型 (32bit)

printf(“fact(%d)=%d\n”, 3, fact(3));

return int main(void)

{

int k=3;

printf(“fact(%d)=%d\n”, k, fact(k));

return 0;

}

main 関数に戻る

fact(3) を 呼び出し fact 関数から

fact(3)=6

void 型 (0bit) 仮引数 : なし

（自動）変数

k 3

int 型 (32bit)

printf(“fact(%d)=%d\n”, 3, 6);

return int main(void)

{

int k=3;

printf(“fact(%d)=%d\n”, k, fact(k));

return 0;

} fact 関数から

fact(3)=6 main 関数に戻る

void 型 (0bit) 仮引数 : なし

（自動）変数

k 3

int 型 (32bit)

printf(“fact(%d)=%d\n”, 3, 6);

return 0

int main(void) {

int k=3;

printf(“fact(%d)=%d\n”, k, fact(k));

return 0;

}

正常終了