コラム
再帰処理（1）
作成日：20200711 テーマ1：情報系 テーマ2：プログラム テーマ3：
苦手な再帰処理について、自分が理解したプロセスを備忘録的に残しておく。
再帰処理は、設定した関数内で自分自身を呼び出す処理のことをいう。 再帰処理を使う例として、順列だったり組み合わせだったり、特に動的に組み合わせ数が変化するようなものに適している。
ここでは簡単な事例として、自然数nの階乗\( n! = n ( n-1 )( n-2 ) \cdots 2 \cdot 1 \)の計算を、再帰処理を使って書いて見る。
この再帰処理の実行手順は、下表のように上から順に fact(5) → fact(4) →・・・→ fact(1) と実行される。
fact(5)～fact(2)はif分のelse側の処理が実行され、fact(1)で戻り値 = 1が実行される。
今度は下から順に上へ向かって、
という風に値が決まっていく。
以上が、階乗計算での再帰処理の流れである。
この処理の流れを理解しつつ、他の用途にもつなげていけるよう、あとは訓練するのみ。
再帰処理は、設定した関数内で自分自身を呼び出す処理のことをいう。 再帰処理を使う例として、順列だったり組み合わせだったり、特に動的に組み合わせ数が変化するようなものに適している。
ここでは簡単な事例として、自然数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(1) = 1 | ||||
| fact(2) = 2 * 1 | ||||
| fact(3) = 3 * 2 * 1 | ||||
| fact(4) = 4 * 3 * 2 * 1 | ||||
| fact(5) = 5 * 4 * 3 * 2 * 1 | ||||
以上が、階乗計算での再帰処理の流れである。
この処理の流れを理解しつつ、他の用途にもつなげていけるよう、あとは訓練するのみ。
