基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

再帰関数について、Chat GPTで確認していたのですが、どうにも分からないので、ご教授頂けないでしょうか。
【Python】
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

print(factorial(5))  # 5の階乗
print(fibonacci(6))  # フィボナッチ数列の6番目の値

factorial(5)5の階乗については、5*4*3*2*1＝120となり、呼び出した値を全て掛け算した結果というイメージで覚えていました。
fibonacci(6)フィボナッチ数列でも同様に計算し、呼び出した値を全て足していく「21」と思っていたのですが、結果は「8」
fibonacci(8)で呼び出すと「21」になり、再帰関数自体の理解が出来なくなりました。
（多分階乗の覚え方・理解の仕方もいけなかったのだと思うのですが…）

①fibonacci(6)が「8」になるトレースのイメージ
②再帰関数の正しい認識・覚え方

また、フィボナッチ数列自体の法則を覚えてしまえば良いのですが、再帰関数の応用が出た場合、太刀打ちできないので、根本的にしっかり理解したくご教授お願い致します。

>print(fibonacci(6))  # フィボナッチ数列の6番目の値
fibonacci(n)がフィボナッチ数列のn番目の値なのであればfibonacci(6)＝8になるのは当然ではないですかね。n番目までの値の総和を求めたいのであれば別のアルゴリズムを考える必要があります。

chihiroさん
ご説明有難うございます。
当然のことと回答頂いたので、再度Chat GPTに聞いてみたところ、なんとなくイメージ出来ました。
return fibonacci(n - 1) + fibonacci(n - 2)
ここの二つ再帰呼出しされるイメージがどうにも付かなくて困り果てていたので助かりました、有難うございます。
サンプル問題、科目B参考書と問題集5冊やったのですが、ちょっと応用になると出来なくなることが多かったので、きちんと理解したくて質問しました。有難うございました。

超有名所の性質は覚えても良いかもしれませんが
擬似言語問題を解く上で覚えるというのは無理があると思いますのでトレースの技術を磨くことが大事です。
※そもそもある数学的知識がないと解けないような疑似言語問題はほぼ０と考えてます。

再帰関数問題だけではないですが、
与えられた数字が大きそうだと感じた場合小さな数や少ない配列をとりあえず当てて動きのイメージを掴むのが良いと思います。

fibonacci(1)や(0)と与えた場合、答えは１と０とすぐわかります。

これを踏まえた上でfibonacci(6)のトレースをしてみると
６からツリー状にどんどん深く再帰することになると思います。
下はトレースの途中に見えますがこれでもう答えは求まってます。

＿＿＿＿＿＿＿＿＿＿＿＿＿６
＿＿＿＿＿＿＿＿＿５＿＿＿＿＿＿＿４
＿＿＿＿＿４＿＿＿＿＿＿＿３
＿＿＿３＿＿＿２
＿＿２＿１
＿１＿０

再帰に関わらず関数は与えられた数字が同じ場合、何度使ったところで同じ結果を返します。
※足し算の関数が合ったとして、１万回使ったら結果が変わるでは困りますよね。
>これは覚えなくていいですが・・・広域変数などの関数外の値により必ずしも同じ結果にならない場合もありますが、情報処理の言語問題であれば同一結果になると考えて問題ないと思ってます。

これを踏まえた上で
fibonacci(2)＝f(1)＋f(0)＝１＋０で１になる。
fibonacci(3)＝f(2)＋f(1)＝１＋１で２になる。
fibonacci(4)＝f(3)＋f(2)＝２＋１で３になる。
fibonacci(5)＝f(4)＋f(3)＝３＋２で５になる。
fibonacci(6)＝f(5)＋f(4)＝５＋３で８になる。
では仮に
fibonacci(7)＝f(6)＋f(5)＝なのだから答えは・・・

何度使っても同じは、factorialでも一緒です。
factorial(0)は１を返します。
factorial(1)は１×１で１になる。
factorial(2)は２×１で２になる。
factorial(3)は３×２で６になる。
factorial(4)は４×６で２４になる。
factorial(5)は５×２４で１２０になる。
では仮に
factorial(6)は６×１２０なのだから答えは・・・

今回の問題は小さな数からあてていったほうがいいケースでしたが必ずしもそうではないです。

・どこで同じものを呼んでる。
・代入されて変数が変化した。
等が気付けるかはメモの度合いによります。

ただ問題を解くのではなく、解く上で変化をメモで残していけるよういろいろ試行錯誤しながら学習するのが良いと思います。

電タックさん

ご丁寧にありがとうございます。
頂いたトレース表を見て、かなり理解が進みました。
fibonacci(7)＝f(6)＋f(5)＝8+5＝13
factorial(6)は６×120で720ですね。

参考書だけの学習だと合格できないと知り、Pythonで実際の動きを見つつ分からないところはChat GPTで聞く勉強法にしているのですが、fibonacciの考え方がどうしても分からなかったので、大変助かりました。
再帰関数は階乗で勉強しましたが、全部掛けてけば良いとイメージで覚えていたため、fibonacciの様に簡単な応用でも出来なかったので、おっしゃる通り根本的に理解することが大事と思いました。

既に4回落ちていて、科目Bの壁にぶち当たってます。
少しでも捨て問を減らす為、数学的な知識も入れておいた方が良いのかな？とか思っていましたが、仰る通りトレースが重要なんですよね。
（ただ時間が足りない…ちゃんと最後までトレースしてたら、時間内に終わらないので、途中で多分コレって感じで回答しています。）
合格した方の意見通り実際のアルゴリズムの動きを見ることが大事だと思ったので、Pythonと参考書で引き続き頑張ります。