解決したいこと基本情報科目Ｂに関連する再帰の問題で躓いています。問題コード整数型: 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投稿が増える予定ですが
どなたかお力を貸してください。！！

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

2Answer

@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です）

1Like

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 分岐を事前に適用させただけのものなので
根本的には同じ考え方で再帰を説明できます。

0Like

Are you sure you want to delete the question?

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

解決したいこと

問題コード

問い、解答

2Answer

Comments

Your answer might help someone💌

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

解決したいこと

問題コード

問い、解答

2Answer

Comments

Your answer might help someone💌

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