03-functions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Functions\n",
    "\n",
    "Python provides several linguistic features that make it relatively easy to generalize and reuse code. The most important is the **function**.\n",
    "\n",
    "In Python each function definition is of the following form.\n",
    "\n",
    "```bash\n",
    "def <name>(<argument1>, <argument2>, ...):\n",
    "    <body>\n",
    "```\n",
    "\n",
    "The sequence of names within the parentheses following the function name are the *formal parameters* of the function. When the function is used, the formal parameters are bound to the *actual parameters* (often referred to as *arguments*) of the *function invocation* (also referred to as a *function call*).\n",
    "\n",
    "**Example 1.**\n",
    "\n",
    "Consider the following code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minValue(a, b):\n",
    "    if a < b:\n",
    "        print(a)\n",
    "    else:\n",
    "        print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function gets two arguments $a, b \\in \\mathbb{R}$ and prints a lower value. To see results of this function you have to call it in your main code.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "x = 12\n",
    "y = 4\n",
    "minValue(x, y)\n",
    "minValue(3, 6)\n",
    "\n",
    "del x, y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This program will print `4` due to third line and `3` due to fourth line. The main role of this function is to print some value, but in lots of cases we would save its results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13\n"
     ]
    }
   ],
   "source": [
    "res = minValue(17, 13)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function will print `13`, but if you want to print `res` value using `print(res)`, you will see `None`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(res)\n",
    "\n",
    "del res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Functions Role\n",
    "\n",
    "In Python we can define 3 main roles of functions.\n",
    "\n",
    "- Executes some subprogram.\n",
    "\n",
    "- Returns some value.\n",
    "\n",
    "- Both executes some subprogram and returns some value.\n",
    "\n",
    "There is, however, a special statement, `return`, that can be used only within the body of a function.\n",
    "\n",
    "```bash\n",
    "def <name>(<argument1>, <argument2>, ...):\n",
    "    <body>\n",
    "    return <value>\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Code below presents the function that executes some subprogram."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def printPerson(firstName, lastName):\n",
    "    if firstName == None:\n",
    "        firstName = 'Jackson'\n",
    "    if lastName == None:\n",
    "        lastName = 'Smith'\n",
    "    print('First Name:', firstName, '; Last Name:', lastName)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Code below presents the function that returns some value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def squareRoot(n):\n",
    "    return n ** (1 / 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Code below presents the function that both executes some subprogram and returns some value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxValue(a, b):\n",
    "    if a > b:\n",
    "        print(a)\n",
    "        return a\n",
    "    else:\n",
    "        print(b)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Function Calling\n",
    "\n",
    "Description of what happens when a function is called:\n",
    "\n",
    "1. The expressions that make up the actual parameters are evaluated, and the formal parameters of the function are bound to the resulting values. For example, the invocation `maxVal(3+4, z)` will bind the formal parameter `x` to 7 and the formal parameter `y` to whatever value the variable z has when the invocation is evaluated.\n",
    "\n",
    "2. The *point of execution* (the next instruction to be executed) moves from the point of invocation to the first statement in the body of the function.\n",
    "\n",
    "3. The code in the body of the function is executed until either a `return` statement is encountered, in which case the value of the expression following the `return` becomes the value of the function invocation, or there are no more statements to execute, in which case the function returns the value `None`. (If no expression follows the return, the value of the invocation is `None`.)\n",
    "\n",
    "4. The value of the invocation is the returned value.\n",
    "\n",
    "5. The point of execution is transferred back to the code immediately following the invocation.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example**\n",
    "\n",
    "Consider the following code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "def increment(n):\n",
    "    n = n + 1\n",
    "\n",
    "i = 4\n",
    "increment(i)\n",
    "print(i)\n",
    "\n",
    "del i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could expect that the program will print `5`, but it still prints `4`. That is because the value of an argument was changed only in the function body and after execution, it returns to its previous form. To save results, remember that the function should return a new value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "def increment(n):\n",
    "    n = n + 1\n",
    "    return n\n",
    "\n",
    "i = 4\n",
    "increment(i)\n",
    "print(i)\n",
    "\n",
    "del i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It still prints `4`, because the new value was not saved anywhere. Remember to bind the new value to the existing value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "def increment(n):\n",
    "    n = n + 1\n",
    "    return n\n",
    "\n",
    "i = 4\n",
    "i = increment(i)\n",
    "print(i)\n",
    "\n",
    "del i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, the program prints `5` in the console.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Scoping\n",
    "\n",
    "Each function defines a new **name space**, also called a **scope**.\n",
    "\n",
    "1. At the top level, i.e., the level of the shell, a *symbol table* keeps track of all names defined at that level and their current bindings.\n",
    "\n",
    "2. When a function is called, a new symbol table (often called a *stack frame*) is created. This table keeps track of all names defined within the function (including the formal parameters) and their current bindings. If a function is called from within the function body, yet another stack frame is created.\n",
    "\n",
    "3. When the function completes, its stack frame goes away.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**Example**\n",
    "\n",
    "Consider the following code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "4\n",
      "3\n"
     ]
    },
    {
     "ename": "NameError",
     "evalue": "name 'x' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[11], line 10\u001b[0m\n\u001b[1;32m      8\u001b[0m \u001b[38;5;28mprint\u001b[39m(myFunction(a))\n\u001b[1;32m      9\u001b[0m \u001b[38;5;28mprint\u001b[39m(a)\n\u001b[0;32m---> 10\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[43mx\u001b[49m)\n",
      "\u001b[0;31mNameError\u001b[0m: name 'x' is not defined"
     ]
    }
   ],
   "source": [
    "def myFunction(a):\n",
    "    a = a + 1\n",
    "    x = 7\n",
    "    return a\n",
    "\n",
    "a = 3\n",
    "print(myFunction(5))\n",
    "print(myFunction(a))\n",
    "print(a)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "If the interpreter has declared some variable, in our case it is `a`, and the function gets an argument with the same name, then in our case the `a` variable will get the value from the argument. The value beyond the function declaration is invisible for this function. Also, when the function ends its execution, the program backs to the previous binding before the function was called. Be careful because values declared inside the function body are deleted after execution of the function body. This program will produce the following output:\n",
    "\n",
    "```bash\n",
    "6\n",
    "4\n",
    "3\n",
    "Traceback (most recent call last):\n",
    "    File \"scope.py\", line 11, in <module>\n",
    "    print(x)\n",
    "NameError: name 'x' is not defined\n",
    "```\n",
    "\n",
    "The scope would look like in the figure below.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Functions declared within another function inherit declared variables in the main function body (or given as the arguments).**\n",
    "\n",
    "**Example**\n",
    "Consider the following code.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "def f():\n",
    "    print(x)\n",
    "\n",
    "x = 4\n",
    "f()\n",
    "\n",
    "del x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This program will print `4` after execution, because the function has access to the value of the `x` variable, but has no access to change its value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "ename": "UnboundLocalError",
     "evalue": "cannot access local variable 'x' where it is not associated with a value",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mUnboundLocalError\u001b[0m                         Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[13], line 6\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[38;5;28mprint\u001b[39m(x)\n\u001b[1;32m      5\u001b[0m x \u001b[38;5;241m=\u001b[39m \u001b[38;5;241m4\u001b[39m\n\u001b[0;32m----> 6\u001b[0m \u001b[43mf\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m      8\u001b[0m \u001b[38;5;28;01mdel\u001b[39;00m x\n",
      "Cell \u001b[0;32mIn[13], line 2\u001b[0m, in \u001b[0;36mf\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mf\u001b[39m():\n\u001b[0;32m----> 2\u001b[0m     x \u001b[38;5;241m=\u001b[39m \u001b[43mx\u001b[49m \u001b[38;5;241m+\u001b[39m \u001b[38;5;241m1\u001b[39m\n\u001b[1;32m      3\u001b[0m     \u001b[38;5;28mprint\u001b[39m(x)\n",
      "\u001b[0;31mUnboundLocalError\u001b[0m: cannot access local variable 'x' where it is not associated with a value"
     ]
    }
   ],
   "source": [
    "def f():\n",
    "    x = x + 1\n",
    "    print(x)\n",
    "\n",
    "x = 4\n",
    "f()\n",
    "\n",
    "del x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "This program produces the following output:\n",
    "\n",
    "```bash\n",
    "Traceback (most recent call last):\n",
    "    File \"access.py\", line 6, in <module>\n",
    "    f()\n",
    "    File \"access.py\", line 2, in f\n",
    "    x = x + 1\n",
    "        ^\n",
    "UnboundLocalError: cannot access local variable 'x' where it is not associated with a value\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example**\n",
    "\n",
    "Consider the following code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "5\n",
      "5\n",
      "5\n"
     ]
    },
    {
     "ename": "NameError",
     "evalue": "name 'y' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[14], line 16\u001b[0m\n\u001b[1;32m     13\u001b[0m     \u001b[38;5;28mprint\u001b[39m(x)\n\u001b[1;32m     14\u001b[0m     \u001b[38;5;28mprint\u001b[39m(y)\n\u001b[0;32m---> 16\u001b[0m \u001b[43mf\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m5\u001b[39;49m\u001b[43m)\u001b[49m\n",
      "Cell \u001b[0;32mIn[14], line 14\u001b[0m, in \u001b[0;36mf\u001b[0;34m(x)\u001b[0m\n\u001b[1;32m     12\u001b[0m j()\n\u001b[1;32m     13\u001b[0m \u001b[38;5;28mprint\u001b[39m(x)\n\u001b[0;32m---> 14\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[43my\u001b[49m)\n",
      "\u001b[0;31mNameError\u001b[0m: name 'y' is not defined"
     ]
    }
   ],
   "source": [
    "def f(x):\n",
    "    def g():\n",
    "        x = 1\n",
    "        print(x)\n",
    "    def h():\n",
    "        y = x\n",
    "        print(y)\n",
    "    def j():\n",
    "        print(x)\n",
    "    g()\n",
    "    h()\n",
    "    j()\n",
    "    print(x)\n",
    "    print(y)\n",
    "\n",
    "f(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Global Variables\n",
    "\n",
    "Instruction `global` tells Python that a variable should be defined at the outermost scope of the module in which the line of code appears rather than within the scope of the function in which the line of code appears. That mechanism is called the *global variable*.\n",
    "\n",
    "**Example**\n",
    "\n",
    "Consider the following code.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "3\n",
      "5\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "def myFunction(a):\n",
    "    global counter\n",
    "    counter = counter + a\n",
    "\n",
    "counter = 0\n",
    "print(counter)\n",
    "myFunction(3)\n",
    "print(counter)\n",
    "myFunction(2)\n",
    "print(counter)\n",
    "myFunction(4)\n",
    "print(counter)\n",
    "\n",
    "del counter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Variable `counter` is evaluated from the outside scope.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Modules\n",
    "\n",
    "A **module** is a ` .py ` file containing Python definitions and statements. A program gets access to a module through an `import` statement.\n",
    "\n",
    "**Example**\n",
    "\n",
    "Imagine that you work in the company that produces software. There is a very low probability that you will have to write all functions by yourself. In most cases, your employer will give you access to their own frameworks that are the collection of already implemented modules. These frameworks could contain everything, for example, math operations and constants. So imagine you have access to the `someModule.py` program.\n",
    "\n",
    "```bash\n",
    "pi = 3.14159\n",
    "def area(radius):\n",
    "    return pi*(radius**2)\n",
    "\n",
    "def circumference(radius): \n",
    "    return 2*pi*radius\n",
    "    \n",
    "def sphereSurface(radius): \n",
    "    return 4.0*area(radius)\n",
    "    \n",
    "def sphereVolume(radius):\n",
    "    return (4.0/3.0)*pi*(radius**3)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "To use this content in your own program, you can import all of these functions using the `import` statement.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'pi' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[16], line 3\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;28;01mimport\u001b[39;00m \u001b[38;5;21;01mmodules\u001b[39;00m\u001b[38;5;21;01m.\u001b[39;00m\u001b[38;5;21;01msomeModule\u001b[39;00m\n\u001b[0;32m----> 3\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[43mpi\u001b[49m)\n",
      "\u001b[0;31mNameError\u001b[0m: name 'pi' is not defined"
     ]
    }
   ],
   "source": [
    "import modules.someModule\n",
    "\n",
    "print(pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "This code will produce an error because, to differentiate your own variables and variables provided by the module, you must use the module prefix, in this case `someModule`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.14159\n"
     ]
    }
   ],
   "source": [
    "import modules.someModule\n",
    "\n",
    "print(modules.someModule.pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "This code will print `3.14159` in the console. When you want to calculate the area of the circle with radius $r=3$, your code should look like this.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "28.27431\n"
     ]
    }
   ],
   "source": [
    "import modules.someModule\n",
    "\n",
    "area = modules.someModule.area(3)\n",
    "print(area)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Remember that the area of the circle is evaluated using the following formula: \n",
    "\n",
    "$$ \\text{Area}(r) = r^2\\pi $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recursion\n",
    "\n",
    "Recursion is a programming technique where a function calls itself to solve smaller instances of a problem. \n",
    "\n",
    "It consists of two main components: \n",
    "\n",
    "- the base case, which terminates the recursion,\n",
    "\n",
    "- the recursive call, which brings the solution closer to the base case. \n",
    "\n",
    "Recursion is particularly useful for solving tree-like problems or complex problems that can be broken down into smaller, similar subproblems. It is important for every recursive function to have a proper base case; otherwise, the recursion may lead to an infinite loop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 1.**\n",
    "\n",
    "The `factorial` function computes the factorial of a given number `n` using recursion. If `n` is 0 or 1, it returns 1 (base case), otherwise, it multiplies `n` by the factorial of `n-1`, calling the function recursively.\n",
    "\n",
    "$$ \\text{factorial}(n) = n! = \\begin{cases} 1, & \\text{if } n = 0 \\\\ 1, & \\text{if } n = 1 \\\\ n \\times \\text{factorial}(n - 1), & \\text{otherwise} \\end{cases} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def factorial(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return n * factorial(n - 1)\n",
    "\n",
    "factorial(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Factorial](images/factorial.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 2.**\n",
    "\n",
    "The `power` function calculates the power of a number `n` raised to `k`. The base case is when `k` is 1 or less, returning `n`, and otherwise, it multiplies `n` by the result of calling `power(n, k-1)` recursively.\n",
    "\n",
    "$$ \\text{power}(n, k) = n^k = \\begin{cases} n, & \\text{if } k \\leq 1 \\\\ n \\times \\text{power}(n, k - 1), & \\text{otherwise} \\end{cases} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def power(n, k):\n",
    "    if k <= 1:\n",
    "        return n\n",
    "    else:\n",
    "        return n * power(n, k - 1)\n",
    "\n",
    "power(2, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Power](images/power.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 3.**\n",
    "\n",
    "The `fibonacci` function calculates the Fibonacci sequence using recursion. The base case is when `n` is 0 or 1, returning 1. For other values of `n`, it recursively sums the two previous numbers in the sequence by calling `fibonacci(n-1)` and `fibonacci(n-2)`.\n",
    "\n",
    "$$ \\text{fibonacci}(n) = \\begin{cases} 1, & \\text{if } n = 0 \\\\ 1, & \\text{if } n = 1 \\\\ \\text{fibonacci}(n - 1) + \\text{fibonacci}(n - 2), & \\text{otherwise} \\end{cases} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "2\n",
      "3\n",
      "5\n",
      "8\n",
      "13\n",
      "21\n",
      "34\n"
     ]
    }
   ],
   "source": [
    "def fibonacci(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fibonacci(n - 1) + fibonacci(n - 2)\n",
    "\n",
    "print(fibonacci(0))\n",
    "print(fibonacci(1))\n",
    "print(fibonacci(2))\n",
    "print(fibonacci(3))\n",
    "print(fibonacci(4))\n",
    "print(fibonacci(5))\n",
    "print(fibonacci(6))\n",
    "print(fibonacci(7))\n",
    "print(fibonacci(8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Fibonacci](images/fibonacci.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Specifications\n",
    "\n",
    "A *specification* of a function defines a contract between the **implementer** of a function and those who will be writing programs that use the function. We will refer to the users of a function as its **clients**. This contract can be thought of as containing two parts.\n",
    "\n",
    "1. **Assumptions**: These describe conditions that must be met by clients of the function. Typically, they describe constraints on the actual parameters. Almost always, they specify the acceptable set of types for each parameter, and not infrequently some constraints on the value of one or more of the parameters.\n",
    "\n",
    "2. **Guarantees**: These describe conditions that must be met by the function, provided that it has been called in a way that satisfies the assumptions.\n",
    "\n",
    "**Example**\n",
    "\n",
    "```bash\n",
    "def findRoot(x, power, epsilon):\n",
    "    \"\"\"Assumes x and epsilon int or float, power an int,\n",
    "    epsilon > 0 and power >= 1\n",
    "    Returns float y such that y**power is within epsilon of x.\n",
    "    If such a float does not exist, it returns None\"\"\"\n",
    "    \n",
    "    <body>\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary\n",
    "\n",
    "There are two reasons why we should use the mechanism of functions:\n",
    "\n",
    "1. **Decomposition** creates structure. It allows us to break a program into parts that are reasonably self-contained, and that may be reused in different settings.\n",
    "\n",
    "2. **Abstraction** hides detail. It allows us to use a piece of code as if it were a black box—that is, something whose interior details we cannot see, don’t need to see, and shouldn't even want to see. The essence of abstraction is preserving information that is relevant in a given context, and forgetting information that is irrelevant in that context. The key to using abstraction effectively in programming is finding a notion of relevance that is appropriate for both the builder of an abstraction and the potential clients of the abstraction. That is the true art of programming.\n"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}