再帰的(リカーシブ)プログラムで質問があります。

質問

再帰的(リカーシブ)プログラムの所で質問があります。

f(n)：if n≦1 then return 1 else return n×f(n－1)

n=5の場合、
(1) f(5)=5×f(4)
(2) f(4)=4×f(3)
(3) f(3)=3×f(2)
(4) f(2)=2×f(1)
(5) f(1)=1
結果としてf(5)=120

上記に対して質問があります。

質問1
f(5)の戻り値は、"5×f(4)"で合ってますでしょうか？

質問2
(1)から(2)に移行する流れとして、(1)のf(5)の処理による戻り値が、5×f(4)となり、この戻り値のf(4)によって引数の値が4であるf()関数が再び浮かび上がるというか、立ち上がるというかそういったイメージで(2)に移行するという考え方で合ってますでしょうか？

質問3
(1)の段階ではまだf(4)の値は確定していませんし、(2)の段階ではまだf(3)の値は確定していないように、(1)(2)(3)(4)までは値が確定せず、(5)の段階でf(1)の値が1に確定し、(4)(3)(2)(1)の順番でそれぞれf(2)、f(3)、f(4)、f(5)、の値が確定していき、最終的にf(5)=120になるのだと思いますが、この(4)(3)(2)(1)の戻っていく手順ってどこにそういった命令があるのでしょうか？

それとも、f(1)=1となった段階で、f(1)になっている部分に自動的に1が代入されていくのでしょうか？

回答No.4

_kappe_ · ベストアンサー

回答No.2の者です。
補足質問に回答します。質問(1)(2)ともに、書かれているとおりで合っています。

再帰は非常に強力ですが、慣れるまでは直感的に理解しづらいのも確かです。頑張ってください。

お礼

お返事ありがとうございます！
はい、あなたのおかげで視界良好になり、一気に悩みが晴れました。
とても説明が、初心者の私にも分かりやすく感謝しております。　
はい、頑張ります！
本当にありがとうございました！

回答No.5

notnot

補足の内容で合ってます。

お礼

何度もありがとうございました！

回答No.3

chachaboxx

質問の意図が、アルゴリズム的なことであれば解釈の仕方によります。
戻り値ではあるのですが処理的には評価結果だと思います。代入ではなく参照になるかと。

実行手続き的なことであれば、言語仕様通りのCPU命令に展開するようにコンパイラーを設計する　となります。

再帰プログラムはシンプルに書けば人間的には理解しやすいのですが、少し複雑(分岐)になると極端に難解なコードになるのでセンスが問われるところですね。他、実行速度的には再帰を用いない場合と比べるとメモリ操作のオーバーヘッドが、ある分、少し遅くなるようです。余談でした。

お礼

回答ありがとうございました！
代入ではなく、参照ですね。
基本情報の勉強を始めたばかりでして、基本的な部分がまだ理解していなくて苦労していますが、今日値渡しと参照渡しを学び、わかってきました。
ありがとうございました！

回答No.2

_kappe_

普通のプログラミング言語で実行する場合は、質問文にあるイメージとは異なる順序で実行されます。

f(3)=3×f(2)

式の中の×（乗算）を実行するために、×の左右の式の値をまず確定させます。×の左は3なのでそのまま、×の右はf(2)なので、その値を計算します。
同様に、f(2)=2×f(1)を計算するには乗算の前にf(1)の値を確定する必要があります。定義からf(1)=1なので、f(2)=2×1=2が決まります。
f(2)の値が決まったところで、f(3)の乗算の計算に戻ります。f(3)=3×2=6となります。

計算の進むイメージはこうなります。
f(4)
=4×f(3) … まずf(3)の値を決める
=4×(3×f(2)) … 同様にf(2)の値を先に決める
=4×(3×(2×f(1))) … 同様にf(1)の値を先に決める
=4×(3×(2×1)) … 括弧の中の計算を優先
=4×(3×2)
=4×6
=24

質問1への回答：f(5)の戻り値は120です。普通のプログラミング言語では、"5×f(4)"のような計算途中の状態がf(5)の戻り値として使われることはありません。

質問2への回答：質問に書かれているイメージがよく分かりませんが、「"5×f(4)"が戻り値」という状態はないので、質問の前提が成り立っていません。

質問3への回答：多くのプログラミング言語では、再帰は関数呼び出しによって実装されます。途中の状態はスタックに保存されています。「戻っていく」操作も、関数からのリターンで実現されています。

ただし、"5×f(4)"のような計算途中の状態を戻り値として扱えるプログラミング言語を作ることは可能です。コンピュータ上で実現するには効率が良くないので普通はやらないだけです。

補足

まず、ご回答ありがとうございました。
まだ基本情報の勉強を始めたばかりで理解が遅くて返信が遅くなり、申し訳ございません。
もう2点ほど、下記にて質問させて頂きましたので、お願い致します。

質問1への回答：f(5)の戻り値は120です。
普通のプログラミング言語では、"5×f(4)"のような計算途中の状態がf(5)の戻り値として使われることはありません。
→大変勉強になりました。×の左右の値が確定するまでは処理は完了せず、途中の状態でいるという事、そして値が確定していない計算途中は戻り値にはならない事、この2つは初めて知りました。
しかし、そう考えると論理的につながり、理解出来ました。

質問2への回答：質問に書かれているイメージがよく分かりませんが、「"5×f(4)"が戻り値」という状態はないので、質問の前提が成り立っていません。
→×の左右の値(今回は右側が確定していない)が確定するまでは途中の状態なので、戻り値としては返ってこないという事ですね。
おっしゃる通り、質問の前提が成り立ちません。

質問3への回答：多くのプログラミング言語では、再帰は関数呼び出しによって実装されます。途中の状態はスタックに保存されています。「戻っていく」操作も、関数からのリターンで実現されています。

→ここが私が一番理解していない所だと思いますから、もう少し質問させて下さい。

質問(1)
(1) f(5)=5×f(4)
(2) f(4)=4×f(3)
(3) f(3)=3×f(2)
(4) f(2)=2×f(1)
(1)から(4)までの流れとしては、f(4)の値が未確定なので、f(5)が計算途中のままでf(4)の関数が呼び出され、同じようにf(4)もf(3)の値が未確定なので計算途中のままでf(2)が呼び出され、f(1)の値が未確定なので、f(1)関数が呼び出される。

まず、(1)から(4)までの流れはこういう理解で宜しいでしょうか？

質問(2)
質問(1)から流れが続き、

(5) f(1)=1
f(1)の値が1に確定すると、f(2)=2×f(1)が計算途中のままだったが、f(1)の値が確定したので、f(1)=1が参照されてf(2)=2×f(1)のf(1)が1になり、f(2)=2×1=2となりf(2)の戻り値は2になる。
また同じようにf(2)=2と値が確定したので、f(2)=2を参照し、計算途中のままであるf(3)=3×f(2)のf(2)が2と値が確定し、f(3)=3×2=6となり、f(3)の戻り値は6となる。
この流れを同じように繰り返してf(5)の戻り値は120になる。
このような流れで合ってますでしょうか？

回答No.1

notnot

質問1
合ってます。

質問2
違います。
> (1)のf(5)の処理による戻り値が、5×f(4)となり、
f(4)の値が計算されるまでは、f(5)の戻り値は計算途中です。
f(4)の値が5×f(4)の計算式に戻されてから、f(5)がリターンします。

質問3
> この(4)(3)(2)(1)の戻っていく手順ってどこにそういった命令があるのでしょうか？
return命令です。

> それとも、f(1)=1となった段階で、f(1)になっている部分に自動的に1が代入されていくのでしょうか？
これはちょっと文意が取れません。
f(1)が1であるのは、ifのthen部分で決まっています。

補足

ご回答ありがとうございます。
それであなた様ともう1人の回答された方が同じような回答をされておりまして、回答に対する私の質問が同じようになってしまいますが、色々な方の考えを読んで学びたいので、同じような質問ですがご容赦ください。
以下、宜しくお願い致します。

質問(1)
(1) f(5)=5×f(4)
(2) f(4)=4×f(3)
(3) f(3)=3×f(2)
(4) f(2)=2×f(1)
(1)から(4)までの流れとしては、f(4)の値が未確定なので、f(5)が計算途中のままでf(4)の関数が呼び出され、同じようにf(4)もf(3)の値が未確定なので計算途中のままでf(2)が呼び出され、f(1)の値が未確定なので、f(1)関数が呼び出される。

まず、(1)から(4)までの流れはこういう理解で宜しいでしょうか？

質問(2)
質問(1)から流れが続き、

(5) f(1)=1
f(1)の値が1に確定すると、f(2)=2×f(1)が計算途中のままだったが、f(1)の値が確定したので、f(1)=1が参照されてf(2)=2×f(1)のf(1)が1になり、f(2)=2×1=2となりf(2)の戻り値は2になる。
また同じようにf(2)=2と値が確定したので、f(2)=2を参照し、計算途中のままであるf(3)=3×f(2)のf(2)が2と値が確定し、f(3)=3×2=6となり、f(3)の戻り値は6となる。
この流れを同じように繰り返してf(5)の戻り値は120になる。
このような流れで合ってますでしょうか？