20260519_3

20260512_3

---

再帰

再帰: 定義の中で自分自身と同じ関数を呼び出す関数
再帰的定義: 再帰関数の定義の仕方
再帰呼び出し: 再帰関数の呼び出し方

内部ではスタックになるからローカル変数がごちゃごちゃになったりはしない

---

メモリモデル

• コールスタックはメモリの中でどのように扱われる？
• スタック1段の大きさは可変だが、必要な境界はポインタで示す
• ローカル領域/リターンアドレス/引数領域などがまとまってスタックされる

text	機械語
global/static
heap	mallocなどで利用する
…	空き部分
g()	ここにstatic pointerをおく
f()
main()

コールスタックは後ろから前方へ、mallocなどで使うheapは前から後ろへ伸びていく
→仮にぶつかっても外部に影響が起こらない

---

分割統治法

Divide and Conquer
→解くべき問題を小規模な部分問題に分割し、部分問題の回を統合して全体の解を得ようとする方法

1. Divide…問題を小問題に分割
2. Conquer…小問題を解決
3. Combine…結果を統合

具体例

• 整列アルゴリズム
  • クイックソート
  • マージソート
• 行列積
• FFT

int sum(int a, int n, int d){
	if(n==1){
		return a;
	}else{
		return(a+d*(n-1)+sum(a,n-1,d))
	}
}

1. $a_n$と$sum(a,n-1,d)$に分割
2. sumの結果を取得
3. 全部を足す

行列の積なども同様

ユークリッドの互除法

ユークリッドの互除法

整数$a$と$b$について

• $a=bk+r$となる$k$と$r$がある
• $a$と$b$の最大公約数を$G$、$b$と$r$の最大公約数を$G^{\prime }$とすると、$G$は$r$の約数でなければいけない
• 逆に、$b$と$r$の最大公約数$G^{\prime }$は$a$の約数であり、$G\ge G^{\prime }$

$a$と$b$の最大公約数$G$=$b$と$r$の最大公約数$G^{\prime }$

int gcd(int x, int y){
	int r = x % y;
	if(r == 0){
		return(y); //終端条件
	}else{
	return (gcd(x, y));
	}
}

int gcd(int x, int, y){
	if(y == 0){
		return (0);
	}else{
		return(gcd(y,rx%y)
	}
}

ユークリッドの互除法は計算量を抑えられる
素因数分解は$O(n^{1/2})$だが互除法は$O(\log n)$

---

ハノイの塔

再帰で解けるらしい

• 最大の円盤を最短のステップで目的軸に移動するためには、上の円盤群をいったん中間軸(使っていない軸)に移す必要がある
• これを2枚になるまでくりかえす

→最も大きい円盤以外の円盤をグループとみなせば円盤の枚数とは無関係に全く同じ手続きでパズルを解ける

基本的にはこうなる

int move(int k, char x, char y, char z){//kが円盤の枚数、xが開始軸、yが目的軸、zが中間軸
	if(k==1){
		//一番上を目的軸へ
	}else{
		move(k-1,x,z,y);//下から二枚目より上を中間軸へ
		//一番下を開始軸から目的軸へ
		move(k-1,z,y,x);//さっき動かした分を目的軸へ
	}
}

今回は移動をprintfで示す

int move(int k, char x, char y, char z){//kが円盤の枚数、xが開始軸、yが目的軸、zが中間
	if(k==1){
		printf("move #%02d from %c to%c.\n",k,x,y);//一番上を目的軸へ
	}else{
		move(k-1,x,z,y);//下から二枚目より上を中間軸へ
		printf("move #%02d from %c to %c.\n",k,x,y);//一番下を開始軸から目的軸へ
		move(k-1,z,y,x);//さっき動かした分を目的軸へ
	}
}

int move(int k, char x, char y, char z){//kが円盤の枚数、xが開始軸、yが目的軸、zが中間軸
	if(k==1){
		printf("move #%02d from %c to%c.\n",k,x,y);//一番上を目的軸へ
	}else{
		move(k-1,x,z,y);//下から二枚目より上を中間軸へ
		for(int i=1;i<k;i++){putchar(' ');}//結果を見やすくするためインデント
		printf("move #%02d from %c to %c.\n",k,x,y);//一番下を開始軸から目的軸へ
		move(k-1,z,y,x);//さっき動かした分を目的軸へ
	}
}

ここでのmoveのように2回以上再帰呼び出しをする関数は真に再帰的だといわれる
真に再帰的な関数は挙動が複雑

再帰表現は簡単だが、動きは複雑で実行効率は悪い

---

void recur(int n){
	if(n>0){
		recur(n-1);
		printf("%d\n",n);
		recur(n-2);
	}
}

再帰関数の挙動を分析する

トップダウン解析

graph TD
A["recur(3); 4 recur(2);"]
A-->B["recur(2);3;recur(1);"]
A-->C["recur(1);2;recur(0);"]
B-->D["recur(1);1;recur(0);"]
B-->E["recur(0);1recur(-1);"]
C-->F["recur(0);1;recur(-1);"]
D-->G["recur(0);1;recur(-1);"]

ボトムアップ解析

recur(1)について考える
→1を出力するだけ

recur(2)についえ考える
→12を出力する

…これを継続

ビット演算やビットシフトなども可能