回帰 と 再帰
十進BASIC_プログラミング へ戻る
大学生のための数学 へ戻る
2013.05.27


回帰には、 十進BASIC のプログラムでは、 次のような3通りの手法があります。
    DO WHILE 〜 LOOP
    FOR 〜 NEXT
    10 〜 GOTO 10


たとえば、 次のような1から10までの自然数の総和を求めるプログラムに用いられます。
    LET k = 1
    LET j = 0
    DO WHILE k =< 10
      LET j = j + k
      LET k = k + 1
    LOOP
    PRINT j
    END



回帰の例として、 他に、 階乗を求める2つのプログラムを、 次に示します。

  再帰は、 ある手続き中に再びその手続き自身を呼び出すことです。 具体的には、 関数の定義の中に自分自身の関数が登場する場合で、 再帰関数と言われます。 再帰 は 回帰 を含んでいますので、 冒頭で述べたような回帰の手段を使わなくとも、 回帰することができます。 その例を2つ示します。 階乗を求めるプログラム と 最大公約数を求めるプログラム です。 2つとも外部再帰関数を呼び出すアルゴリズムになっています。 これらのプログラムソースは、 十進BASICSAMPLE の中にあります。
  たとえば、 階乗を求めるプログラムにおける再帰呼び出しは、 次のような式を表すことになります。
   fact = n * ( n − 1 ) * fact ( n − 2 )
      = n * ( n − 1 ) * ( n − 2 ) * fact ( n − 3 )
      = n * ( n − 1 ) * ( n − 2 ) * ( n − 3 ) *
・ ・ ・ ・ * 2 * fact ( 1 )

  再帰関数の例としては、 さらに、 等差数列 や 等比数列 の 第項の値を求めるプログラムがあります。