notebooks/01_1_The_Fibonacci_Sequence.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "88d9214f",
   "metadata": {},
   "source": [
    "# Fibonacci Sequence\n",
    "\n",
    "```Wikipedia:```In mathematics, the Fibonacci numbers, commonly denoted $F_n$, form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors omit the initial terms and start the sequence from 1 and 1 or from 1 and 2. Starting from 0 and 1, the next few values in the sequence are:\n",
    "\n",
    "    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...\n",
    "\n",
    "```Base case: ``` if   $n\\in  \\{0,1\\}    \\Longrightarrow  F_n = n$\n",
    "\n",
    "```Recursive solution: ```if $ n > 1 \\Longrightarrow F_n = F_{n-1} + F_{n-2}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8eecaa5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib1(n: int) -> int:\n",
    "    \"\"\"\n",
    "    This function returns the nth Fibonacci number.\n",
    "    \"\"\"\n",
    "    # We Forgot Base case for the first two numbers\n",
    "\n",
    "    # Recursive solution to the Fibonacci sequence\n",
    "    return fib1(n-1) + fib1(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "04b7e440",
   "metadata": {},
   "outputs": [
    {
     "ename": "RecursionError",
     "evalue": "maximum recursion depth exceeded",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mRecursionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m/tmp/ipykernel_3118/3514751940.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0m__name__\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"__main__\"\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m# This is the main function\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m     \u001b[0;31m# Let's print tenth Fibonacci number\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfib1\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m10\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m/tmp/ipykernel_3118/2578591742.py\u001b[0m in \u001b[0;36mfib1\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m     \u001b[0;31m# Recursive solution to the Fibonacci sequence\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mfib1\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfib1\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "... last 1 frames repeated, from the frame below ...\n",
      "\u001b[0;32m/tmp/ipykernel_3118/2578591742.py\u001b[0m in \u001b[0;36mfib1\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m     \u001b[0;31m# Recursive solution to the Fibonacci sequence\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mfib1\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfib1\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\": # This is the main function\n",
    "    # Let's print tenth Fibonacci number\n",
    "    print(fib1(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "112e8d65",
   "metadata": {},
   "source": [
    "**Opps!!!**\n",
    "\n",
    " we got error ```RecursionError: maximum recursion depth exceeded```\n",
    " This is because Function ```fib1``` repeatedly calls Function ```fib1``` and does not stop anywhere. This is because we have not truncated the starting point of the sequence in the ```fib1``` function \n",
    "\n",
    "**Avoid Infinitive loop by Utllizing Base Case**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "15b99614",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib2(n: int) -> int:\n",
    "    \"\"\"\n",
    "    This function returns the nth Fibonacci number.\n",
    "    \"\"\"\n",
    "    # Base case for the first two numbers\n",
    "    if n in (0, 1):\n",
    "        return n\n",
    "    # Recursive solution to the Fibonacci sequence\n",
    "    return fib2(n-1) + fib2(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e190b174",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\": # This is the main function\n",
    "    # Let's print tenth Fibonacci number\n",
    "    print(fib2(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fcbccd6c",
   "metadata": {},
   "source": [
    "**Hooray it works.**\n",
    "\n",
    "Let's manage Negative cases:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "2794ed9e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib2(n: int) -> int:\n",
    "    \"\"\"\n",
    "    This function returns the nth Fibonacci number.\n",
    "    \"\"\"\n",
    "    # Negative cases\n",
    "    if n < 0:\n",
    "        return f\"The {n}th term of Fibonacci Sequence is not defined!\"\n",
    "    # Base case for the first two numbers\n",
    "    if n in (0, 1):\n",
    "        return n\n",
    "    # Recursive solution to the Fibonacci sequence\n",
    "    return fib2(n-1) + fib2(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d1d859aa",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n",
      "The -3th term of Fibonacci Sequence is not defined!\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\": # This is the main function\n",
    "    # Let's print tenth Fibonacci number\n",
    "    print(fib2(10))\n",
    "    # Let's see what happens if we call fib3 with negative n\n",
    "    print(fib2(-3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "143313a9",
   "metadata": {},
   "source": [
    "Let's put our damn fine ```fib3``` function to the test with a large number. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a7a5c8dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "# DO NOT RUN THIS CELL!!!!!\n",
    "# DO NOT RUN THIS CELL!!!!!\n",
    "# DO NOT RUN THIS CELL!!!!!\n",
    "if __name__ == \"__main__\": # This is the main function\n",
    "    # Let's print 50th Fibonacci number\n",
    "    print(fib2(50))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aceb8f77",
   "metadata": {},
   "source": [
    "**But wait a moment, above cell never stop execution!!! Why?**\n",
    "\n",
    "Let's see what happens when we call fib(n)\n",
    "\n",
    "* fib(2) :\n",
    "\n",
    "![fib2_tree](../images/fib2_tree.jpg)\n",
    "```\n",
    "fib(2) calls 1 time\n",
    "fib(1) calls 1 time\n",
    "fib(0) calls 1 time\n",
    "Total call of fib fnction when n=2 is equal to 3\n",
    "```\n",
    "* fib(3) :\n",
    "\n",
    "![fib3_tree](../images/fib3_tree.jpg)\n",
    "```\n",
    "fib(3) calls 1 time\n",
    "fib(2) calls 1 time\n",
    "fib(1) calls 2 time\n",
    "fib(0) calls 1 time\n",
    "Total call of fib fnction when n=3 is equal to 5\n",
    "```\n",
    "* fib(4) :\n",
    "\n",
    "![fib4_tree](../images/fib4_tree.jpg)\n",
    "```\n",
    "fib(4) calls 1 time\n",
    "fib(3) calls 1 time\n",
    "fib(2) calls 2 time\n",
    "fib(1) calls 3 time\n",
    "fib(0) calls 2 time\n",
    "Total call of fib fnction when n=4 is equal to 9\n",
    "```\n",
    "* fib(5) :\n",
    "\n",
    "![fib5_tree](../images/fib5_tree.jpg)\n",
    "```\n",
    "fib(5) calls 1 time\n",
    "fib(4) calls 1 time\n",
    "fib(3) calls 2 time\n",
    "fib(2) calls 3 time\n",
    "fib(1) calls 5 time\n",
    "fib(0) calls 3 time\n",
    "Total call of fib fnction when n=5 is equal to 15\n",
    "```\n",
    "* fib(50) :\n",
    "\n",
    "![fib50_tree](../images/fib50_tree.jpg)\n",
    "```\n",
    "fib(50) calls 1 time\n",
    "fib(49) calls 1 time\n",
    "fib(48) calls 2 time\n",
    ".\n",
    ".\n",
    ".\n",
    "fib(3) calls 4807526976 time\n",
    "fib(2) calls 7778742049 time\n",
    "fib(1) calls 12586269025 time\n",
    "fib(0) calls 7778742049 time\n",
    "Total call of fib fnction when n=50 is equal to 40730022147\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3b412f8",
   "metadata": {},
   "source": [
    "As you can see call tree grows exponentially!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e1dfb85",
   "metadata": {},
   "source": [
    "### Memoization technique \n",
    "```Wikipedia: ``` In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. A memoized function \"remembers\" the results corresponding to some set of specific inputs. Subsequent calls with remembered inputs return the remembered result rather than recalculating it, thus eliminating the primary cost of a call with given parameters from all but the first call made to the function with those parameters.\n",
    "\n",
    "![fib5_memoized_tree](../images/fib5_memoized_tree.jpg)\n",
    "\n",
    "So the Fib(5) function is called 9 times instead of 15 times.\n",
    "\n",
    "Similarly, rather than calling the fib function 40730022147 times, Fib(50) call the fib function 99 times. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f6e366c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Dict\n",
    "\n",
    "# memoization dictionary to store the results of the function calls\n",
    "memory: Dict[int, int] = {}\n",
    "\n",
    "def fib3(n: int) -> int:\n",
    "    \"\"\"\n",
    "    This function returns the nth Fibonacci number.\n",
    "    \"\"\"\n",
    "    # Check if the result is already in the memory dictionary and return it\n",
    "    if n in memory:\n",
    "        return memory[n]\n",
    "    # if not, calculate it and store it in the memory dictionary\n",
    "    # Negative cases\n",
    "    if n < 0:\n",
    "        return f\"The {n}th term of Fibonacci Sequence is not defined!\"\n",
    "    # Base case for the first two numbers\n",
    "    elif n in (0, 1):\n",
    "        memory[n] = n\n",
    "    # Recursive solution to the Fibonacci sequence\n",
    "    else:\n",
    "        memory[n] = fib3(n-1) + fib3(n-2)\n",
    "\n",
    "    return memory[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a46312d3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "354224848179261915075\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\": # This is the main function\n",
    "    # Let's print 50th Fibonacci number\n",
    "    print(fib3(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97ab28d1",
   "metadata": {},
   "source": [
    "### Automatic memoization\n",
    "We can use ```@functools.lru_cache()``` to automatically memoiezed our fib function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "47dc991a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "\n",
    "# Using the lru_cache decorator to cache the results of the function calls\n",
    "@lru_cache(maxsize=None)\n",
    "def fib4(n: int) -> int:\n",
    "    \"\"\"\n",
    "    This function returns the nth Fibonacci number.\n",
    "    \"\"\"\n",
    "    # Negative cases\n",
    "    if n < 0:\n",
    "        return f\"The {n}th term of Fibonacci Sequence is not defined!\"\n",
    "    # Base case for the first two numbers\n",
    "    if n in (0, 1):\n",
    "        return n\n",
    "    # Recursive solution to the Fibonacci sequence\n",
    "    return fib4(n-1) + fib4(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "91d3a930",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "176023680645013966468226945392411250770384383304492191886725992896575345044216019675\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\": # This is the main function\n",
    "    # Let's print 50th Fibonacci number\n",
    "    print(fib4(400))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "09da024d",
   "metadata": {},
   "source": [
    "### Lets Solve the Fib problem iteratively instead of recursively"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "af9562f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib5(n: int) -> int:\n",
    "    \"\"\"\n",
    "    This function returns the nth Fibonacci number.\n",
    "    \"\"\"\n",
    "    # Negative cases\n",
    "    if n < 0:\n",
    "        return f\"The {n}th term of Fibonacci Sequence is not defined!\"\n",
    "    if n == 0: return 0\n",
    "    a: int = 0 # First number of the sequence Fib(0)\n",
    "    b: int = 1 # Second number of the sequence Fib(1)\n",
    "    # iterative solution to the Fibonacci sequence\n",
    "    for _ in range(1, n):\n",
    "        b, a = a+b, b\n",
    "    return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "9eda4b1e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\": # This is the main function\n",
    "    # Let's print 50th Fibonacci number\n",
    "    print(fib5(1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d18948e",
   "metadata": {},
   "source": [
    "### Fibonacci Generator:\n",
    "When the generator is iterated, each iteration will use a yield statement to output a value from the Fibonacci sequence.\n",
    "Then we can print the entire sequence. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "199d25d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Generator\n",
    "\n",
    "# Generator function to generate the Fibonacci sequence\n",
    "def fib6(n: int) -> Generator[int, None, None]: # Generator[yield_type, send_type, return_type]\n",
    "    \"\"\"\n",
    "    This function returns the nth Fibonacci number.\n",
    "    \"\"\"\n",
    "    # Negative cases\n",
    "    if n < 0:\n",
    "        raise ValueError(f\"The {n}th term of Fibonacci Sequence is not defined!\")\n",
    "    # Base case\n",
    "    yield 0 \n",
    "    if n > 0: yield  1\n",
    "    a: int = 0 # First number of the sequence Fib(0)\n",
    "    b: int = 1 # Second number of the sequence Fib(1)\n",
    "    # generator solution to the Fibonacci sequence\n",
    "    for _ in range(1, n):\n",
    "        b, a = a+b, b\n",
    "        yield b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "db73c6a6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 "
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\": # This is the main function\n",
    "    # Let's print first 51 terms of Fibonacci sequence\n",
    "    for i in fib6(50):\n",
    "        print(i, end=\" \")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}