再帰呼び出しで分割統治法の考え方のプログラムをJavaScriptで書いたサンプル
単純に、配列の指定範囲の合計を求める関数を、再帰を用いて記述する。
<html>
<head>
</head>
<body>
<p>
このプログラムは、実行結果を console.log() で出力するので、
Ctrl+Shift+I で、JavaScript の console を表示させてね。
</p>
<script type="text/javascript">
// a : 配列
// start : 合計を計算する範囲の戦闘
// end : 合計を計算する範囲の最後+1
// 配列の合計は、配列の先頭 + 残りの合計
function array_sum( a , start , end ) {
console.log( "array_sum:" + start + "," + end ) ;
if ( start == end ) {
console.log( "array_sum(" + start + "," + end + ")=0" ) ;
return 0 ;
} else {
var ans = a[ start ] + array_sum( a , start + 1 , end ) ;
console.log( "array_sum("+start+","+end+")="+ans ) ;
return ans ;
}
}
var array = new Array( 11 , 22 , 33 , 44 , 55 , 66 , 77 , 88 ) ;
console.log( array_sum( array , 0 , array.length ) ) ;
// 配列の合計は、データが１個ならその値。
// そうでなければ、配列の前半の合計 + 配列の後半の合計
function array_sum2( a , start , end ) {
console.log( "array_sum2:" + start + "," + end ) ;
if ( start + 1 == end ) {
var ans = a[ start ] ;
console.log( "array_sum2("+start+","+end+")="+ans ) ;
return ans ;
} else {
var mid = Math.floor( ( start + end ) / 2 ) ;
var ans = array_sum2( a , start , mid ) // 配列前半の合計を求める
+ array_sum2( a , mid , end ) ; // 配列後半の合計を求める
console.log( "array_sum2("+start+","+end+")="+ans ) ;
return ans ;
}
}
console.log( array_sum2( array , 0 , array.length ) ) ;
</script>
</body>
</html>