再帰呼び出しの戻り値がどうして１じゃないのか

Question

再帰呼び出しの戻り値について、くだらない質問をさせていただきます。
再帰呼び出しの解説で、以下のような階乗の計算が使われると思います。

引数を５から渡していきますが、１になるまでは、条件分岐のfalseの処理が続つため、プロシージャ nの階乗　が呼び出され続けます。
引数が２までは、戻り値が呼び出し元に戻らないのではないでしょうか？
１になって、ようやく、戻り値として呼び出し元に戻り、そこで、終わるわけではないのでしょうか？
だとすると、下記のようなコードだと、必ず１が戻り値になるのではないかと思ってしまいます。

どうして、１までいって、１だけ戻って終わらず、２　６　２４　が戻るんでしょうか？

超ド素人の質問でお恥ずかしいのですが、どなたか、ご教授願います。

コード
```Sub main()
    
    Dim answer As Long
    answer = nの階乗(5)
    
    Debug.Print answer
    
End Sub
 
Function nの階乗(n As Long) As Variant
 
    If n = 1 Then
        nの階乗 = 1
    Else
        nの階乗 = n * nの階乗(n - 1)
    End If
    
    Debug.Print n & "の階乗は" & nの階乗
 
End Function

Answer 1

再帰処理はいろんなイメージの仕方があると思うので一つの例として回答いたします。

「Functionを呼べば戻り値が1つ返ってくる」ということを念頭に置くと良いかもしれません。
下は再帰のイメージです。

nの階乗(5)
   └ 5 * nの階乗(4)
            └ 4 * nの階乗(3)
                     └ 3 * nの階乗(2)
                              └ 2 * nの階乗(1)
                                       └ 1

nの階乗というFunctionは再帰処理によって合計5回呼び出されます。処理の順番はもちろんnの階乗(5)→nの階乗(4)→nの階乗(3)→nの階乗(2)→nの階乗(1)ですね。

そしてそれぞれのFunctionで戻り値が返ってきます。戻り値が返ってくる順番はnの階乗(1)→nの階乗(2)→nの階乗(3)→nの階乗(4)→nの階乗(5)です。上のイメージでいうと処理が上から下に流れて下から上に戻り値が返る…そんな感じです。

１になって、ようやく、戻り値として呼び出し元に戻り、そこで、終わるわけではないのでしょうか？

ここの戻り値1はあくまで nの階乗(1)の戻り値です。
その後も処理は続き
nの階乗(2)に対して戻り値2が返り、
nの階乗(3)に対して戻り値6が返り、
nの階乗(4)に対して戻り値24が返り、
nの階乗(5)に対して戻り値120が返るとなるわけです。

なので nの階乗(5) を呼び出すと結果として120が返ってくるわけです。

---

（追記） 最初に書いたイメージをコードっぽく書いてみますね。

もとのFunctionは下のような形でした。

Function nの階乗(n As Long) As Variant
  If n = 1 Then
    nの階乗 = 1
  Else
    nの階乗 = n * nの階乗(n - 1)
  End If
  Debug.Print n & "の階乗は" & nの階乗
End Function

例としてn = 2のときは下のようになります。

n = 2
If n = 1 Then
  // ここには入らない
  nの階乗 = 1
Else
  // ここに入る
  nの階乗 = n * nの階乗(n - 1)
End If
Debug.Print n & "の階乗は" & nの階乗

このときnの階乗(n - 1)の部分をバラして書くと下のようになります。

n = 2
If n = 1 Then
  // ここには入らない
  nの階乗 = 1
Else
  // ここに入る
  nの階乗 = n * {
    // nの階乗(1)の処理
    n' = 1
    If n' = 1 Then
      // ここに入る
      n'の階乗 = 1
    Else
      // ここには入らない
      n'の階乗 = n' * nの階乗(n' - 1)
    End If
    Debug.Print n' & "の階乗は" & n'の階乗 // ここで「1の階乗は1」と出る
  } // {}の中身は n'の階乗 つまり 1 になる
End If
Debug.Print n & "の階乗は" & nの階乗 // ここで「2の階乗は2」と出る

もちろんこのコードは文法が誤っているので動かないのですが、気持ちとしては上のようなコードが走っているわけです。

n = 3のときはこうです。

n = 3
If n = 1 Then
  // ここには入らない
  nの階乗 = 1
Else
  // ここに入る
  nの階乗 = n * {
    // nの階乗(2)の処理
    n' = 2
    If n' = 1 Then
      // ここには入らない
      n'の階乗 = 1
    Else
      // ここに入る
      n'の階乗 = n' * {
        // nの階乗(1)の処理
        n'' = 1
        If n'' = 1 Then
          // ここに入る
          n''の階乗 = 1
        Else
          // ここには入らない
          n''の階乗 = n'' * nの階乗(n'' - 1)
        End If
        Debug.Print n'' & "の階乗は" & n''の階乗 // ここで「1の階乗は1」と出る
      } // {}の中身は n''の階乗 つまり 1 になる
    End If
    Debug.Print n' & "の階乗は" & n'の階乗 // ここで「2の階乗は2」と出る
  } // {}の中身は n'の階乗 つまり 2 になる
End If
Debug.Print n & "の階乗は" & nの階乗 // ここで「3の階乗は6」と出る

nが大きくなると入れ子が増えるため書くのが大変になりますが同じように動きます。

Comments

[robben]

ありがとうございます。

ｎの階乗(1)まで呼び出しが終わるまで、戻り値が蓄積されている感じなのでしょうか？
Ｆ８で1行ずつ見ていると、
引数1を呼び出すまで、ｎの階乗には値は何も入っていないようです。
そして、１が入って初めてtrueとなり、nの階乗の値に1が入ります。
その後debug.printされて、end functionまでいったのに、また、end ifに戻ってdebug.printが繰り返されている......。
どうして、end functionまで行った後に、その上に戻って繰り返されるのかがわからないです。
すみません。

[hoshito]

robbenさんの疑問にはmaisumakunさんが回答してくださっているのでそちらを確認していただけると良いです。
私の回答を、もう少しコードに寄せて書いてみたのでそちらもご確認いただけると幸いです。

[maisumakun]

› その後debug.printされて、end functionまでいったのに、また、end ifに戻ってdebug.printが繰り返されている......。

「同じ関数の」end ifに戻っているわけではなく、「呼び出したがわの関数」の続きが実行されているだけです。

普通の関数でも、呼び出したら関数の中身が実行されて、その結果を受け取ってから呼んだ側のコードの続きが実行されますが、それと全く同じことです。

[robben]

ありがとうございました。
お礼が遅れ申し訳ありません

Answer 2

こちらで行デバックされると理解できませんか?

Sub main()
    Dim answer As Long
    answer = nの階乗(5)
    Debug.Print answer
End Sub

Function nの階乗(n As Long) As Variant

    If n = 1 Then
        nの階乗 = 1: Debug.Print n & " (戻り値=0 次計算渡し値=1)"
    Else
        xxxx = nの階乗(n - 1): Debug.Print n & " (戻り値=" & xxxx & " 次計算渡し値=" & n * xxxx & ")"
        nの階乗 = n * xxxx
    End If
    'Debug.Print n & "の階乗は" & nの階乗

End Function

Comments

[robben]

お礼が遅れ申し訳ありません。
ご説明ありがとうございました。

Answer 3

詳しい解説は他の方が丁寧にされているので、理解の一助として、質問者さんのコードを再起呼び出しをせずに書くと以下のようになります（n <= 5で決め打ち）
また、計算式の中に関数を入れているのも混乱のもとのように見えたので、一度変数に格納する書き方になっています。

Sub main()

Dim answer As Long
answer = nの階乗(5)

Debug.Print answer

End Sub

Function nの階乗(n As Long) As Variant

If n = 1 Then
    nの階乗 = 1
Else
    m = n1の階乗(n)
    nの階乗 = n * m
End If

Debug.Print n & "の階乗は" & nの階乗

End Function
Function n1の階乗(n As Long) As Variant

If n - 1 = 1 Then
    n1の階乗 = 1
Else
    m1 = n2の階乗(n)
    n1の階乗 = (n - 1) * m1
End If

Debug.Print n - 1 & "の階乗は" & n1の階乗

End Function
Function n2の階乗(n As Long) As Variant

If n - 2 = 1 Then
    n2の階乗 = 1
Else
    m2 = n3の階乗(n)
    n2の階乗 = (n - 2) * m2
End If

Debug.Print n - 2 & "の階乗は" & n2の階乗

End Function
Function n3の階乗(n As Long) As Variant

If n - 3 = 1 Then
    n3の階乗 = 1
Else
    m3 = n4の階乗(n)
    n3の階乗 = (n - 3) * m3
End If

Debug.Print n - 3 & "の階乗は" & n3の階乗

End Function
Function n4の階乗(n As Long) As Variant

If n - 4 = 1 Then
    n4の階乗 = 1
Else
    m4 = n4の階乗(n)
    n4の階乗 = (n - 4) * m4
End If

Debug.Print n - 4 & "の階乗は" & n4の階乗

End Function

大切なのは、プロシージャの途中で関数を呼びだしたとき、その関数の処理が終わったら、呼び出し元のプロシージャのに戻って処理が継続される、ということです。それは、再起呼び出しでも同様です。

Comments

[robben]

ご説明ありがとうございました。
お礼が遅れ申し訳ありません

Answer 4

「再帰呼び出し」という特別な呼び出し方ではなく、単に同じ名前の関数を呼んだだけと考えてください。同じ関数を複数回呼び出しても、関数の実行ごとに引数などは別に確保されますので、特に干渉することはありません。

Function nの階乗(n As Long) As Variant

If n = 1 Then
nの階乗 = 1
Else
nの階乗 = n * nの階乗(n - 1)
End If

nの階乗(6)を呼んだ場合、コードはElseの方に進んで、n * nの階乗(5)という値を返します。当然、nの階乗(5)の実行が終わらなければ結果の値は得られないので、戻ってきてから掛け算が行われます。

Comments

[robben]

ご回答ありがとうございます。
「関数の実行ごとに引数などは別に確保されますので、特に干渉することはありません」
すみません。ここの意味がよくわかりません。
①functionを呼ぶごとに、戻り値は発生しているということですか？
②その戻り値は、引数1まで行ってから、今度は逆の順番で、戻り値を実際に返していくのですか？？
ではその戻り値は、引数１にいくまでは、戻らずに待機しているというようなイメージでしょうか？

[maisumakun]

> ①functionを呼ぶごとに、戻り値は発生しているということですか？

そのとおりです。

[maisumakun]

> ②その戻り値は、引数1まで行ってから、今度は逆の順番で、戻り値を実際に返していくのですか？？

戻り値を「実際に」返していく、とはどういう意味でしょうか？

[robben]

５→１の順番で呼び出して、
その戻り値が1→５に実際に呼び出し元に戻ることについて　です。

[maisumakun]

はい、呼ばれた関数が結果を返してから呼んだ関数が終了しますので、終了は逆順となっています（が、そこに重点を置いて考えてもあまり意味はありません）。

[robben]

ありがとうございました。
お礼が遅れ申し訳ありません

Answer 5

関数「nの階乗」の呼出元はmainサブルーチン内の1箇所だけと誤解していませんか?
nの階乗内のelse文の「nの階乗 = n * nの階乗(n - 1)」はこの関数の復帰値を計算して設定する文です。
式の右辺にあるnの階乗は関数の呼び出しで、ここも呼出元です。

main関数とnの階乗内の2箇所にあるDebug.Printの結果をていねいに読んでください。

nの階乗という関数内のDebug.Printがn=5の時から順にn=1の時まで動作して、最後にmain関数のDebug.Printが動作しているのが出力フォーマットから分かると思います。
これは

mainサブルーチンはn=5で関数nの階乗を呼び出し、復帰するのを待つ → 
	n=5で呼ばれた関数はn=4で関数nの階乗を呼び出し、復帰するのを待つ → 
		n=4で呼ばれた関数はn=3で関数nの階乗を呼び出し、復帰するのを待つ → 
			n=3で呼ばれた関数はn=2で関数nの階乗を呼び出し、復帰するのを待つ → 
				n=2で呼ばれた関数はn=1で関数nの階乗を呼び出し、復帰するのを待つ → 
					n=1で呼ばれた関数は1を復帰値として呼出元(n=2で呼ばれた関数)に復帰する
				n=2で呼ばれた関数はn*復帰値(=1)→2を復帰値として呼出元(n=3で呼ばれた関数)に復帰する
			n=3で呼ばれた関数はn*復帰値(=2)→6を復帰値として呼出元(n=4で呼ばれた関数)に復帰する
		n=4で呼ばれた関数はn*復帰値(=6)→24を復帰値として呼出元(n=5で呼ばれた関数)に復帰する
	n=5で呼ばれた関数はn*復帰値(=24)→120を復帰値として呼出元(mainサブルーチン)に復帰する
answerに120が代入される

の結果です。

Comments

[robben]

ご説明ありがとうございました。
お礼が遅れ申し訳ありません。