解決したいこと基本情報科目Ｂに関連する再帰の問題で躓いています。問題コード整数型: t(整数型: x) if(x > 1) return t(x - 1) + x els...

@question2024 (step1engineer)posted at 2024-11-15

基本情報科目Ｂ再帰 IF文について

Q&A

解決したいこと

基本情報科目Ｂに関連する再帰の問題で躓いています。

問題コード

整数型: t(整数型: x)
 if(x > 1)
  return t(x - 1) + x
 else
  return 1
 endif

問い、解答

問題：関数tをt(4)と呼び出すと戻り値は？
解答：10

自分の理解では、解答が「1」になります。

if文で(4>1)がtrueとなり、
return t(3) + x となるのでt(3)で関数を呼び出して

if文でt(3>1)がtrueとなり、
return t(2) + x となるのでt(2)で関数を呼び出して

if文で(2>1)がtrueとなり、
return t(1) + x となるのでt(1)で関数を呼び出して

if文で(1>1)がfalseとなり、
retun 1 と書いてあるので
戻り値は「１」と理解してしまっています。

解説を見るとここまでの考え方は間違っていないように
見えて解説を読んでも理解が追いつくのですが
以下の解説文から「？！」となって全然理解ができません。
以下、解説文より３文を抜粋します。
「値1をt(1)の戻り値として返す、t(1)を終了し、
　t(2)の手続きを実行する。」
「t(3)の戻り値6 + t(4)におけるxの値4=値10を求める」
「値10をt(4)の戻り値として返す」

このあたりが全く理解できません。
なぜ戻り値1をつかってt(1)となるのか、
そこから戻り値が増えていくのか
理解もイメージもできません。。。

今月から基本情報の学習を始めて
科目Ｂで手こずっています。m( _ _)m
基本情報QA投稿が増える予定ですが
どなたかお力を貸してください。！！

よろしくお願いいたします。

5Answer

@nak435 posted at 2024-11-15

if文で(2>1)がtrueとなり、
return t(1) +1 となるのでt(1)で関数を呼び出して

t(2)は、t(1) + 2ですから、3になりますね。
+xを見落としていませんか？（+1では無く+xです）

2Like

Comments

@question2024
Questioner
nak435 様
コメントありがとうございます。
自分の理解では、
+x をするまえに関数の形式(t(x))に一致するのでxを足す前に再帰だと
理解してしまっていたのですが、+xをした結果の値で関数を呼び出しにもどると
いう処理の流れで理解するのが正しいのでしょうか？
聞き返す形になりすみません💦

私の文章が分かりづらいかもしれないので
解説の一部だけを切り取った画像を添付します！!
@question2024
Questioner
+1 とご入力していました💦
これから修正します！
ご指摘ありがとうございます。
@nak435
return t(x - 1) + x は、t(x - 1)の結果に+xしてから戻ります。

解説のスクショ通りですが、
t(1)で呼び出すと1が得られ、
t(2)で呼び出すと、t(1) + 2となり、3が得られ、
t(3)で呼び出すと、t(2) + 3となり、6が得られ、
t(4)で呼び出すと、t(3) + 4となり、10が得られます。

@PECMM posted at 2024-11-15

そもそも関数についてどのくらい理解されているか分からないので
再帰を一旦忘れて普通の関数から説明します。

まず理解のために関数を4つ定義します。

整数型： f4()
  return f3() + 4

整数型： f3()
  return f2() + 3

整数型： f2()
  return f1() + 2

整数型： f1()
  return 1

例えば f2() の呼び出しを実行したとすると、計算結果は f1() + 2 で、f1 は必ず 1 を返すので
f2の戻り値としては 1 + 2 で 3 になります

f2 内で f1 を呼び出しているからといって、足し算の途中でいきなり残りの + 2 を捨てて『f2() の結果は 1 』となることはありません。

f4() の呼び出しを実行した際のイメージは

f4() = f3() + 4
f3() = f2() + 3
f2() = f1() + 2
f1() = 1

と計算していくわけですが、もちろん最終結果は
f4() = 1 ではないですよね。

数学的に式を展開させると

f4() = f3() + 4
     = (f2() + 3) + 4
     = ((f1() + 2) + 3) + 4
    ...

とだんだん置き換わっていくわけですが
プログラミングの実行イメージとしては

f4() = f3() + 4

↓

f4() = f3() + 4 // f4 の途中で f3 を計算
f3() = f2() + 3

↓

f4() = f3() + 4 // f4 の途中で f3 を計算
f3() = f2() + 3 // f3 の途中で f2 を計算
f2() = f1() + 2

↓

f4() = f3() + 4 // f4 の途中で f3 を計算
f3() = f2() + 3 // f3 の途中で f2 を計算
f2() = f1() + 2 // f1 の途中で f1 を計算
f1() = 1

↓

f4() = f3() + 4 // f4 の途中で f3 を計算
f3() = f2() + 3 // f3 の途中で f2 を計算
f2() = 1 + 2    // f2 に f1 の結果を適用

↓

f4() = f3() + 4 // f4 の途中で f3 を計算
f3() = f2() + 3 // f3 の途中で f2 を計算
f2() = 3        // f2 の結果

↓

f4() = f3() + 4 // f4 の途中で f3 を計算
f3() = 3 + 3    // f3 に f2 の結果を適用

以下略

となります。

これらの関数 f1 ～ f4 は、質問の関数t(x) に if 分岐を事前に適用させただけのものなので
根本的には同じ考え方で再帰を説明できます。

1Like

@shigeokamoto posted at 2024-11-16

再起呼び出しは t() の中から t()を呼び出します。
関数呼び出しですから呼び出せば値が戻されます。
順番に呼び出すということは、、順番に値がもどってくるので呼び出したのとは逆順に辿ったような説明になっています。

t()呼び出し                                        t(4) から 10が戻る
--> t(4)                        10 = 1 + 2 + 3 + 4 __/
  --> t(3)           6 = 1 + 2 + 3__/
    --> t(2)     3 = 1 + 2 __/
      --> t(1) 1 __/

0Like

@blonz3977 posted at 2024-11-16

if文で(4>1)がtrueとなり、
return t(3) + x となるのでt(3)で関数を呼び出して

if文でt(3>1)がtrueとなり、
return t(2) + x となるのでt(2)で関数を呼び出して

if文で(2>1)がtrueとなり、
return t(1) + x となるのでt(1)で関数を呼び出して

if文で(1>1)がfalseとなり、
retun 1 と書いてあるので
戻り値は「１」と理解してしまっています。

考え方は間違っていません
最後に「1」が返るので、結果も1になります
しかし、この「1」を返すまでにt(x-1)が何回呼び出されているかを考える必要があります

return t(x-1)+xとあるので、この関数ではtrueでも戻り値が返されます
各ループでは常にt(x-1)+1の値が返されなければいけませんが、ここでは再帰が終わるまでt(x-1)から値は返りません
t(1)になるまでfalseを通らないからです

しかしいったん戻り値が1と決まれば、それまでtrueでt(x-1)の戻り値を待っていた式に値が返ってくるので、連鎖的に計算が発生します

その結果として関数からは10が返されます
再帰中はt(x-1)の処理が各ループで終了していない状態である点が重要です

0Like

@vram posted at 2024-11-19

おそらく「return」をプログラムの終了と思われているようですが「return」は処理を返す　この場合は返り値付きで処理を返すです
あとは頭の中で処理をトレース出来るようにすれば理解出来るようになります
トレースは自分の趣味で置き換えた方がわかりやすいです
（ロボット、電車、すごろく、水や電気が流れる）

他の人と同様に関数を4つにわけました、t1に4を渡すと各関数の xに1個ずつ少ない数値が渡されます

整数型: t1(整数型: x = 4)
 if(x > 1)
  return t2(x - 1) + x
 else
  return 1
 endif

整数型: t2(整数型: x = 3)
 if(x > 1)
  return t3(x - 1) + x
 else
  return 1
 endif
 
整数型: t3(整数型: x = 2)
 if(x > 1)
  return t4(x - 1) + x
 else
  return 1
 endif
整数型: t4(整数型: x = 1)
 if(x > 1)
  return t5(x - 1) + x
 else
  return 1
 endif

if文がジャマなので消して xを数値に置き換えてついでに日本語をソレっぽい命令に

fun t1(4) : Int
  return t2(3) + 4

fun t2(3)
  return t3(2) + 3
 
fun t3(2)
  return t4(1) + 2

fun t4(1)
  return 1

下から順に計算すると

t4(1) = 1
t3(2) = t4(1) + 2 で t3(2) = 3
t2(3) = t3(2) + 3 で t2(3) = 6
t1(4) = t2(3) + 4 で t1(4) = 10

上から計算すると複雑ですが

t1(4) = t2(3) + 4

この式を下記の式で展開

t2(3) = t3(2) + 3

結果

t1(4) = ( t3(2) + 3 ) + 4

この式を下記の式で展開

t3(2) = t4(1) + 2

結果

t1(4) = ( ( t4(1) + 2 ) + 3 ) + 4

この式を下記の式で展開

t4(1) = 1

結果

t1(4) = ( ( 1 + 2 ) + 3 ) + 4

答え

t1(4) = 10

0Like

Are you sure you want to delete the question?

基本情報科目Ｂ再帰 IF文について

解決したいこと

問題コード

問い、解答

5Answer

Comments

Your answer might help someone💌

基本情報 科目Ｂ 再帰 IF文 について

解決したいこと

問題コード

問い、解答

5Answer

Comments

Your answer might help someone💌

基本情報科目Ｂ再帰 IF文について