黄昏より暗きもの、血の流れより赤きもの

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

再帰を使って配列(数列)の総和を求める

再帰とは関数内で関数を呼び出すテクニックの事を指す。主に「階乗を求める」「FizzBuzz問題」「ユークリッドの互除法」「ハノイの塔」や、探索や動的計画法と言ったアルゴリズムを勉強する上で欠かせないテクニックだ。調べてみたら以下のサイトで再帰を取り扱っている。

再帰の例

ソースコード

さて今日は再帰の練習の為に「数列a_1,a_2,......,a_nの総和Snを求めるプログラムを、再帰と言う手法を使って求めよ」という問題を解いてみた。

ここでrec(i+1)+a[i]がどう変化していくか説明していこう。ここでrec(i+1)は問題のSnに対応し、n=5の場合以下のように変化する。

  • (rec(1) + a[0])
  • (rec(2) + a[1]) + a[0]
  • (rec(3) + a[2]) + a[1] + a[0]
  • (rec(4) + a[3]) + a[2] + a[1] + a[0]
  • S_5 = a[4] + a[3]+ a[2] + a[1] + a[0]

と言うようにa_1から順々にS_nを求めていく。最後にrec(5)から逆算して、S_nを求めるプログラム、for文やwhile文を使った場合のソースコードを下にする。