fibonacci.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fibonacci sequence\n",
    "Author: [Ryan Parker](https://github.com/rparkr)\n",
    "\n",
    "A simple function to return the Fibonacci numbers.\n",
    "\n",
    "Fibonacci numbers come from the Fibonacci sequence, a pattern found frequently in nature where the next element of the sequence is the sum of the previous two numbers in the sequence. The sequence starts with (0, 1), so the the 0th and 1st Fibonacci numbers are (0, 1). The second Fibonacci number is the sum of the prior two, or 1 + 0 = 1. Here are the first eleven numbers in the sequence:\n",
    "\n",
    "|  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |  10  |  $F$  |\n",
    "|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:----:|:-----:|\n",
    "|  0  |  1  |  1  |  2  |  3  |  5  |  8  |  13  |  21  |  34  |  55  |  $F$  |\n",
    "|  0  |  1  |  1 + 0 = 1 |  1 + 1 = 2 |  2 + 1 = 3 |  3 + 2 = 5 |  5 + 3 = 8 |  8 + 5 = 13 |  13 + 8 = 21 |  21 + 13 = 34 |  34 + 21 = 55 |  $F_{n-1} + F_{n-2} = F_{n}$ |\n",
    "\n",
    "In this notebook, I implement the Fibonacci sequence as a recursive function, cache intermediate results for faster execution, and use a wrapper to preserve the docstring of the `fib_number` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache, wraps\n",
    "\n",
    "# This wrapper preserves the function's docstring while implementing a cache.\n",
    "def cache_results(func, maxsize=256):\n",
    "    @lru_cache(maxsize=maxsize)  # store intermediate results for faster calc\n",
    "    @wraps(func)\n",
    "    def wrapper(*args, **kwargs):\n",
    "        return func(*args, **kwargs)\n",
    "    return wrapper\n",
    " \n",
    "\n",
    "@cache_results\n",
    "def fib_number(n: int) -> int:\n",
    "    '''Calculate the `n`th Fibonacci number.\n",
    "    \n",
    "    The first two numbers of the sequence are (0, 1). The `n`th number\n",
    "    is the sum of the previous two Fibonacci numbers. Thus, the second Fibonacci\n",
    "    number is 0 + 1 = 1. The third is 1 + 1 = 2; and so on.\n",
    "\n",
    "    Examples:\n",
    "    ```python\n",
    "    >>> fib_number(4)\n",
    "    3\n",
    "    >>> fib_number(10)\n",
    "    55\n",
    "    >>> fib_number(20)\n",
    "    6765\n",
    "    >>> fib_number(100)\n",
    "    354224848179261915075\n",
    "    ```\n",
    "    '''\n",
    "    if n < 2:\n",
    "        return [0, 1][n]\n",
    "    else:\n",
    "        return fib_number(n - 1) + fib_number(n - 2)\n",
    "\n",
    "\n",
    "def fib_sequence(n: int) -> list:\n",
    "    '''Return a list of the Fibonacci numbers up to `n`.\n",
    "\n",
    "    Examples:\n",
    "    ```python\n",
    "    >>> fib_sequence(4)\n",
    "    [0, 1, 1, 2, 3]\n",
    "    >>> fib_sequence(10)\n",
    "    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]\n",
    "    ```\n",
    "    '''\n",
    "    return [fib_number(i) for i in range(n + 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  :                           0\n",
      "1  :                           1\n",
      "10 :                          55\n",
      "20 :                       6,765\n",
      "100: 354,224,848,179,261,931,520\n"
     ]
    }
   ],
   "source": [
    "for i in [0, 1, 10, 20, 100]:\n",
    "    print(f\"{i:<3}: {fib_number(i):>27,.0f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib_sequence(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "See information about the Least Recently Used (LRU) cache, which stores arguments and results for the function, enabling future function calls to return the result from the cache rather than recalculating. Since the Fibonacci function is recursive, using an LRU cache greatly speeds up execution by caching intermediate results. _Least recently used_ can be thought of as the most recent function calls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "CacheInfo(hits=113, misses=101, maxsize=256, currsize=101)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib_number.cache_info()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'maxsize': 256, 'typed': False}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib_number.cache_parameters()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Clear the cache\n",
    "# fib_number.cache_clear()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "ml",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.3"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}