ryamadaのコンピュータ・数学メモ

2006-01-14

漸化式から再帰関数

Java

雑なメモ
今、次のようなk個の変数で定められる漸化式があるとする
$A(x_1,x_2,\cdots,x_k)$
$A(x_1,x_2,\cdots,x_k)=\sum_{x_1}\sum_{x_2}\cdots\sum_{x_k}A(x_1',x_2',\cdots,x_k')$
ただし、１つ以上の変数条件において
$A(x_1,x_2,\cdots,x_k)=A_p_n$
と定められており、かつ、すべての変数条件が確定値が与えられた変数条件に帰着することが確認されているものとする

このとき、ｋ個の変数を有するオブジェクトAについて関数Recur()を定義する

public int Recur(){
		int ret=0;
		if(確定値を与える条件１){
			ret=値１;
		}else if(確定値を与える条件２){
			ret=値２;
　　　　　　　　　}else if(...){
                 ...

		}else{
				for(漸化式にて定義された場合わけ){
　　　　　　　　　　　　　　　　　　　　xi'の算出
				A tmp = new A(x1',x2',...,xk')		
				int ans=tmp.Recur();
				
				ret+= ans;
			}
		}
		return ret;
	}