intro-to-python/09_mappings/03_exercises_fibonacci.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note**: Click on \"*Kernel*\" > \"*Restart Kernel and Run All*\" in [JupyterLab](https://jupyterlab.readthedocs.io/en/stable/) *after* finishing the exercises to ensure that your solution runs top to bottom *without* any errors. If you cannot run this file on your machine, you may want to open it [in the cloud <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_mb.png\">](https://mybinder.org/v2/gh/webartifex/intro-to-python/main?urlpath=lab/tree/09_mappings/03_exercises.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 9: Mappings & Sets (Coding Exercises)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The exercises below assume that you have read the [second part <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/09_mappings/02_content.ipynb) of Chapter 9.\n",
    "\n",
    "The `...`'s in the code cells indicate where you need to fill in code snippets. The number of `...`'s within a code cell give you a rough idea of how many lines of code are needed to solve the task. You should not need to create any additional code cells for your final solution. However, you may want to use temporary code cells to try out some ideas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Memoization without Side Effects"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "It is considered *bad practice* to make a function and thereby its correctness dependent on a program's *global state*: For example, in the \"*Easy at second Glance: Fibonacci Numbers*\" section in [Chapter 9 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/09_mappings/02_content.ipynb#\"Easy-at-second-Glance\"-Example:-Fibonacci-Numbers--%28revisited%29), we use a global `memo` to store the Fibonacci numbers that have already been calculated.\n",
    "\n",
    "That `memo` dictionary could be \"manipulated.\" More often than not, such things happen by accident: Imagine we wrote two independent recursive functions that both rely on memoization to solve different problems, and, unintentionally, we made both work with the *same* global `memo`. As a result, we would observe \"random\" bugs depending on the order in which we executed these functions. Such bugs are hard to track down in practice.\n",
    "\n",
    "A common remedy is to avoid global state and pass intermediate results \"down\" the recursion tree in a \"hidden\" argument. By convention, we prefix parameter names with a single leading underscore `_`, such as with `_memo` below, to indicate that the caller of our `fibonacci()` function *must not* use it. Also, we make `_memo` a *keyword-only* argument to force ourselves to always explicitly name it in a function call. Because it is an **implementation detail**, the `_memo` parameter is *not* mentioned in the docstring.\n",
    "\n",
    "Your task is to complete this version of `fibonacci()` so that the function works *without* any **side effects** in the global scope."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### \"Easy at third Glance\" Example: [Fibonacci Numbers <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Fibonacci_number)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def fibonacci(i, *, debug=False, _memo=None):\n",
    "    \"\"\"Calculate the ith Fibonacci number.\n",
    "\n",
    "    Args:\n",
    "        i (int): index of the Fibonacci number to calculate\n",
    "        debug (bool): show non-cached calls; defaults to False\n",
    "\n",
    "    Returns:\n",
    "        ith_fibonacci (int)\n",
    "    \"\"\"\n",
    "    # answer to Q1\n",
    "    if ...:\n",
    "        ... = {\n",
    "            0: 0,\n",
    "            1: 1,\n",
    "        }\n",
    "\n",
    "    # answer to Q2\n",
    "    if ...:\n",
    "        return ...\n",
    "\n",
    "    if debug:  # added for didactical purposes\n",
    "        print(f\"fibonacci({i}) is calculated\")\n",
    "\n",
    "    # answer to Q3\n",
    "    recurse = (\n",
    "        fibonacci(...)\n",
    "        + fibonacci(...)\n",
    "    )\n",
    "    # answer to Q4\n",
    "    ... = ...\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "**Q1**: When `fibonacci()` is initially called, `_memo` is set to `None`. So, there is *no* `dict` object yet. Implement the *two* base cases in the first `if` statement!\n",
    "\n",
    "Hints: All you need to do is create a *new* `dict` object with the results for `i=0` and `i=1`. This object is then passed on in the recursive function calls. Use the `is` operator in the `if` statement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q2**: When `fibonacci()` is called for non-base cases (i.e., `i > 1`), it first checks if the result is already in the `_memo`. Implement that step in the second `if` statement!\n",
    "\n",
    "Hint: Use the early exit pattern."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q3**: If `fibonacci()` is called for an `i` argument whose result is not yet in the `_memo`, it must calculate it with the usual recursive function calls. Fill in the arguments to the two recursive `fibonacci()` calls!\n",
    "\n",
    "Hint: You must pass on the hidden `_memo`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q4**: Lastly, after the two recursive calls have returned, `fibonacci()` must store the `recurse` result for the given `i` in the `_memo` *before* returning it. Implement that logic!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q5**: What happens to the hidden `_memo` after the initial call to `fibonacci()` returned? How many hidden `_memo` objects exist in memory during the entire computation?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " < your answer >"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Because `fibonacci()` is now independent of the *global state*, the same eleven recursive function calls are made each time! So, this `fibonacci()` is a **pure** function, meaning it has *no* side effects.\n",
    "\n",
    "**Q6**: Execute the following code cell a couple of times to observe that!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "fibonacci(12, debug=True)  # = 13th Fibonacci number -> 11 recursive calls necessary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The runtime of `fibonacci()` is now stable: There is no message that \"an intermediate result is being cached\" as in [Chapter 9 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/09_mappings/02_content.ipynb#\"Easy-at-second-Glance\"-Example:-Fibonacci-Numbers--%28revisited%29).\n",
    "\n",
    "**Q7**: Execute the following code cells a couple of times to observe that!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit -n 1\n",
    "fibonacci(99)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit -n 1\n",
    "fibonacci(999)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.12.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}