コラム

再帰処理(1)

作成日:20200711  テーマ1:情報系  テーマ2:プログラム  テーマ3:

苦手な再帰処理について、自分が理解したプロセスを備忘録的に残しておく。
再帰処理は、設定した関数内で自分自身を呼び出す処理のことをいう。 再帰処理を使う例として、順列だったり組み合わせだったり、特に動的に組み合わせ数が変化するようなものに適している。

ここでは簡単な事例として、自然数nの階乗\( n! = n ( n-1 )( n-2 ) \cdots 2 \cdot 1 \)の計算を、再帰処理を使って書いて見る。

< python >

#再帰関数
def fact(n):
	if n == 1:
		return 1
	else:
		return n * fact(n - 1)

#実行
print (fact(5))

#結果
120

pythonサンプルのダウンロード


< Excel VBA >

'再帰関数
Function fact(n)
	If n = 1 Then
		fact = 1
	Else
		fact = n * fact(n - 1)
	End If
End Function

'実行
Sub test()
	MsgBox fact(5)
End Sub

#結果
120

Excel VBAサンプルのダウンロード


この再帰処理の実行手順は、下表のように上から順に fact(5) →  fact(4) →・・・→  fact(1) と実行される。
fact(5) = 5 * fact(4)
fact(4) = 4 * fact(3)
fact(3) = 3 * fact(2)
fact(2) = 2 * fact(1)
fact(1) = 1
fact(5)~fact(2)はif分のelse側の処理が実行され、fact(1)で戻り値 = 1が実行される。 今度は下から順に上へ向かって、
fact(1) = 1
fact(2) = 2 * 1
fact(3) = 3 * 2 * 1
fact(4) = 4 * 3 * 2 * 1
fact(5) = 5 * 4 * 3 * 2 * 1
という風に値が決まっていく。
以上が、階乗計算での再帰処理の流れである。
この処理の流れを理解しつつ、他の用途にもつなげていけるよう、あとは訓練するのみ。

コラムページトップへ