Python - 再帰と辞書 - 反復とインデックスを超えて - フィボナッチ数列、計算の重複回数

Head First はじめてのプログラミング
頭とからだで覚えるPythonプログラミング入門
原著
楽天ブックス Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

Head First はじめてのプログラミング ―頭とからだで覚えるPythonプログラミング入門 (Eric Freeman(著)、嶋田 健志(監修)、木下 哲也(翻訳)、株式会社オライリー・ジャパン)を8章(再帰と辞書 - 反復とインデックスを超えて)の自分で考えてみよう(374ページ)の解答を求めてみる。

• fibonacci(7)
  • fibonacci(6)
    • fibonacci(5)
      • fibonacci(4)
        • fibonacci(3)
          • fibonacci(2)
            • fibonacci(1)
            • fibonacci(0)
          • fibonacci(1)
        • fibonacci(2)
          • fibonacci(1)
          • fibonacci(0)
      • fibonacci(3)
        • fibonacci(2)
          • fibonacci(1)
          • fibonacci(0)
        • fibonacci(1)
    • fibonacci(4)
      • fibonacci(3)
        • fibonacci(2)
          • fibonacci(1)
          • fibonacci(0)
        • fibonacci(1)
      • fibonacci(2)
        • fibonacci(1)
        • fibonacci(0)
  • fibonacci(5)
    • fibonacci(4)
      • fibonacci(3)
        • fibonacci(2)
          • fibonacci(1)
          • fibonacci(0)
        • fibonacci(1)
      • fibonacci(2)
        • fibonacci(1)
        • fibonacci(0)
    • fibonacci(3)
      • fibonacci(2)
        • fibonacci(1)
        • fibonacci(0)
      • fibonacci(1)

• fibonacci(5): 2回
• fibonacci(4): 3回
• fibonacci(3): 5回
• fibonacci(2): 8回
• fibonacci(1): 13回
• fibonacci(0): 8回

コード

Python 3

#!/usr/bin/env python3
from collections import defaultdict
from unittest import TestCase, main
from typing import List

counts = None


class MyTestCase(TestCase):
    def setUp(self):
        pass

    def tearDown(self):
        pass

    def test(self):
        global counts
        counts = defaultdict(int)
        fib(7)
        nums = [8, 13, 8, 5, 3, 2]
        for k in sorted(counts)[:6]:
            self.assertEqual(counts[k], nums[k])


def fib(n):
    counts[n] += 1
    if n <= 1:
        return 1
    return fib(n - 2) + fib(n - 1)


if __name__ == '__main__':
    main()

入出力結果(Bash、cmd.exe(コマンドプロンプト)、Terminal、Jupyter(IPython))

$ ./sample5.py
.
----------------------------------------------------------------------
Ran 1 test in 0.000s

OK
$