再帰アルゴリズムについては既に，「再帰アルゴリズムについて」で，またユークリッドの互除法 についても，「ユークリッドの互除法」，「拡張ユークリッドの互除法」で説明しました。

　ここでは，再帰アルゴリズムを使って，ユークリッドの互除法を実現してみましょう。

　再帰アルゴリズムはプログラミングでの基本的な技法のひとつで，その特徴を良く理解することは重要です。

　再帰アルゴリズムで実現できるものは適当な書き直しで，非再帰にすることが可能ですから，再帰アルゴリズムが絶対に必要という訳ではありません。また一般的に，再帰版より，非再帰版の方が高速に動作しましから，高性能なプログラムを作り出すという技法でもありません。それどころか，使う状況を誤ると，とても非効率なプログラムになって しまうこともあります。

　（例えば，フィボナッチ数を計算する再帰プログラムは使ってはいけない例でした。これについては，，「再帰アルゴリズムについて」で詳しく説明しました。）

　このように見ていくと，再帰は必要ないと思うかもしれませんが，実際は決してそうではなく，再帰アルゴリズムは重要な技法です。では，その利点はどのようなものでしょうか。それは

ということです。プログラムで最も重要なこととして，「分かりやすい」ということがありました。ですｊから，再帰アルゴリズムは，これを実現する，重要な技法の１つといえます。

　ユークリッドの互除法は２つの自然数 a, b の最大公約数を効率的に計算する方法でした。 これを実現するプログラムとしては，普通は次のようなものがあげられます。次は高校の数学の教科書「数Ｂ」に載っていたものです。

Input a, b
r = a mod b
While r > 0
   a = b
   b = r
   r = a mod b
   Wend
Print b

　これはこれで良いのですが，手計算で行うユークリッドの互除法と少し雰囲気が違います。

ユークリッドの互除法は，例えば， GCD(13,5) を計算するのに，

13 = 2*5 + 3
5  = 1*3 + 2
3  = 1*2 + 1
2 = 2*1 + 0

として，余りが 0 になる１つ手前の余りを最大公約数とするものでした。これをプログラムとして実現する場合の，問題は，この順次割っていくという過程が何回あるかあるか分からないということです。ですから，素朴に，順次割った余りを変数に代入していくとすると，そのための使う変数の個数が分からないことになり，プログラムとして書けないことになります。

　これに対処する方法としては，

• 十分大きな配列を用意しておいて，それを順次使う。

または，

• 一度使った変数を順次入れ替えて再利用する。

という方法が考えられます。上のプログラムは，後者の方法「変数の入れ替え」を行っています。

While・・・Wend の中で，a = b,  b = r を行うのは変数の置き換えです。

　このように見たとき，上のプログラムが十分に分かりやすいということならば，それまでの話です。しかし，変数の再利用は，プログラミングでの１つの技法ですので，それを利用することは無意味ではありませんが，ユークリッドの互除法の理解とは一応別の問題です。

　次に再帰を使って，最大公約数を計算する方法を考えて見ましょう。実は，ユークリッドの互除法による最大公約数の計算は次の原理に拠っています。

　さらに， a > 0, b=0 の場合は，直ちに，GCD(a, 0) = a です。

これらのことを注意して，最大公約数を計算する関数 GCDR を再帰を使って書くと，次のようになります。

Function GCDR(a, b) ' a > 0, b>=0 であること。
   If b =0 then 
      GCDR = a
   Else
      GCDR = GCDR(b, a mod b)
   End If
End Function

Function を使うので，プログラミング技法としては，「数Ｂ」にあるプログラムよりも高級ですが，プログラムの中身自体は，極めて明快です。

　この例ですと，再帰の効果の例としては余り説得力が無いかもしれませんが，次はもう少し効果的です。

　ユークリッドの互除法の応用として，「拡張ユークリッド互除法」がありました。それは，

ものでした。そしてそれを計算するプログラムとして，

Sub ExGCD(x,y,a,b,c)
 ' Extended GCD
 '  x>0 , y>0 に対して ax + by = c となる a, b, c=Gcd(a,b) を求める
 '
 r0 = x  : r1 = y
 a0 = 1  : a1 = 0
 b0 = 0  : b1 = 1
 while (r1>0)
   q1 = r0 \ r1
   r2 = r0 mod r1
   a2 = a0 - q1*a1
   b2 = b0 - q1*b1
   r0 = r1 : r1 = r2
   a0 = a1 : a1 = a2
   b0 = b1 : b1 = b2
 wend
 c = r0
 a = a0
 b = b0
End Sub

を挙げました。

　ここでは，このプログラムの再帰版を作ってみましょう。

　まず，ユークリッドの互除法の証明の過程を振り返って見ましょう。

　便宜上 x=r₀，y=r₁と置きます。このとき，GCD(x,y)=r=r_nは次の式で与えられます。

(0)            r₀=q₁*r₁+r₂,        0< r₂ <r₁
(1)            r₁=q₂*r₂+r₃,        0< r₃ <r₂
(2)            r₂=q₃*r₃+r₄,        0< r₄ <r₃
                ...
(k-1)          r_k-1=q_k*r_k+r_k+1,        0< r_k+1 <r_k
                ...
(n-2)         r_n-2=q_n-1*r_n-1+r_n,    0< r_n <r_n-1
(n-1)         r_n-1=q_n*r_n

　拡張ユークリッドの互除法は，この過程を下から逆に辿り，求める結果を得るものでした。ここでは再帰を使用することとして，次のように考えます。

　ここで，r_n は最大公約数で固定です。s' と t' から s と t を求めるのは，簡単です。実際， r_i = q_i+1 r_i+1 + r_i+2 から，

r_i+2 = r_i - q_i+1 r_i+1

として，これを s'r_i+1 + t' r_i+2 = r_n に代入して整理すると，s = t' および， t = s' - t' q_i+1 が得られます。また，明らかに， i = n のときは， r_n+1 = 0 ですから， s = 1, t = 0, として，

s r_n + t r_n+1 = r_n

が成立します。

従って，この過程をプログラムにすると，

Sub ExGCDR(a,b,s,t,c)
' Extended GCD Recursive
'  a>0 , b>0 に対して sa+tb=c となる s, t, c=Gcd(a,b) を求める
'
 If b=0 then 
    s=1 : t=0 : c=a 
 Else
    q = a \ b : r = a mod b
    Call ExGCDR(b,r,s1,t1,c)
    s = t1 : t = s1 - t1 * q
 End If
End Sub

となります。再帰版のほうが大分簡単です。

　最後に，再帰を使ったプログラムの効率について考えて見ます。これらの再帰版のプログラムで，再帰的に自分を呼ぶ回数は，ユークリッドの互除法のステップの回数と同じです。従って，呼ぶ回数は非常に少数で，非再帰版に比べて計算効率は落ちません。非再帰版に比べて多少余計に内部的なメモリーを使用するだけで，プログラム全体がむしろ短いですから速度は落ちません。

まとめると，

　ユークリッドの互除法，拡張ユークリッドの互除法の再帰版は

非再帰版と同様に高速に動作します！