06. Recursive Functions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recursion has something to do with infinity. I know recursion has something to do with infinity. I think I know recursion has something to do with infinity. He is sure I think I know recursion has something to do with infinity. We doubt he is sure I think I know ... We think that you think that we convinced you now that we can go on forever with this example of a recursion from natural language. Recursion is not only a fundamental feature of natural language, but of the human cognitive capacity. Our way of thinking is based on a recursive thinking processes. Even with a very simple grammar, like \"An English sentence contains a subject and a predicate, and a predicate contains a verb, an object and a complement\", we can demonstrate the infinite possibilities of the natural language.\n",
    "\n",
    "\n",
    "The adjective \"recursive\" originates from the Latin verb \"recurrere\", which means \"to run back\". And this is what a recursive definition or a recursive function does: It is \"running back\" or returning to itself"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "factorial called with n =  5\n",
      "factorial called with n =  4\n",
      "factorial called with n =  3\n",
      "factorial called with n =  2\n",
      "factorial called with n =  1\n",
      "factorial called with n =  0\n",
      "Intermediate result for n = 1 is factorial(1) : 1\n",
      "Intermediate result for n = 2 is factorial(2) : 2\n",
      "Intermediate result for n = 3 is factorial(3) : 6\n",
      "Intermediate result for n = 4 is factorial(4) : 24\n",
      "Intermediate result for n = 5 is factorial(5) : 120\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def factorial(n):\n",
    "    print(\"factorial called with n = \",n)\n",
    "    if n==0:\n",
    "        return 1\n",
    "    else:\n",
    "        re = n * factorial(n-1)\n",
    "        print(\"Intermediate result for n = {} is factorial({}) : {}\".format(n,n,re))\n",
    "        return re \n",
    "factorial(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "832040"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fib(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    elif n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fib(n-1) + fib(n-2)\n",
    "fib(30)\n",
    "#0 1 1 2 3  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6765"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fibi(n):\n",
    "    old, new = 0, 1\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    for i in range(n-1):\n",
    "        old, new = new, old + new\n",
    "    return new\n",
    "fibi(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6765"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# recursive funciton takes lots of time\n",
    "# to check its time\n",
    "\n",
    "memo = {0:0, 1:1}\n",
    "def fibm(n):\n",
    "    if not n in memo:\n",
    "        memo[n] = fibm(n-1) + fibm(n-2)\n",
    "    return memo[n]\n",
    "\n",
    "fibm(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n= 1, fibm: 0.000002, fibi:  0.000002, fib:       0.00000089\n",
      "n= 2, fibm: 0.000001, fibi:  0.000003, fib:       0.00000178\n",
      "n= 3, fibm: 0.000001, fibi:  0.000002, fib:       0.00000267\n",
      "n= 4, fibm: 0.000000, fibi:  0.000003, fib:       0.00000356\n",
      "n= 5, fibm: 0.000000, fibi:  0.000003, fib:       0.00000533\n",
      "n= 6, fibm: 0.000000, fibi:  0.000003, fib:       0.00000800\n",
      "n= 7, fibm: 0.000001, fibi:  0.000002, fib:       0.00001244\n",
      "n= 8, fibm: 0.000001, fibi:  0.000003, fib:       0.00004622\n",
      "n= 9, fibm: 0.000001, fibi:  0.000003, fib:       0.00005156\n",
      "n=10, fibm: 0.000001, fibi:  0.000022, fib:       0.00008756\n",
      "n=11, fibm: 0.000001, fibi:  0.000004, fib:       0.00014311\n",
      "n=12, fibm: 0.000001, fibi:  0.000003, fib:       0.00027333\n",
      "n=13, fibm: 0.000001, fibi:  0.000004, fib:       0.00021467\n",
      "n=14, fibm: 0.000001, fibi:  0.000004, fib:       0.00034489\n",
      "n=15, fibm: 0.000001, fibi:  0.000004, fib:       0.00055644\n",
      "n=16, fibm: 0.000001, fibi:  0.000004, fib:       0.00090089\n",
      "n=17, fibm: 0.000001, fibi:  0.000019, fib:       0.00149733\n",
      "n=18, fibm: 0.000001, fibi:  0.000004, fib:       0.00235911\n",
      "n=19, fibm: 0.000001, fibi:  0.000004, fib:       0.00398444\n",
      "n=20, fibm: 0.000002, fibi:  0.000005, fib:       0.00774044\n"
     ]
    }
   ],
   "source": [
    "from timeit import Timer\n",
    "from __main__ import fib \n",
    "\n",
    "# timer contains function name and path of that function\n",
    "\n",
    "for i in range(1,21):\n",
    "    t1 = Timer(\"fibm(\" + str(i) + \")\" , \"from __main__ import fibm\")\n",
    "    time1 = t1.timeit(3)\n",
    "    t2 = Timer(\"fibi(\" + str(i) + \")\" , \"from __main__ import fibi\")\n",
    "    time2 = t2.timeit(3)\n",
    "    t3 = Timer(\"fib(\" + str(i) + \")\" , \"from __main__ import fib\")\n",
    "    time3 = t3.timeit(3)\n",
    "    print(\"n=%2d, fibm: %8.6f, fibi:  %7.6f, fib:  %15.8f\" % (i, time1, time2,time3)) # time in micro seconds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "214185"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Sum of first n integers\n",
    "def summ(n):\n",
    "    if n==0:\n",
    "        return 0\n",
    "    else:\n",
    "        return n + summ(n-1)\n",
    "summ(654)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parameter passing\n",
    "1. call by value\n",
    "2. call by reference"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ref_demo(x):\n",
    "    print(\"x=\",x,\" id=\",id(x)) #  call by value\n",
    "    x=42\n",
    "    print(\"x=\",x,\" id=\",id(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1465806176\n",
      "1465806176\n",
      "x= 10  id= 1465806176\n",
      "x= 42  id= 1465807200\n",
      "1465806176\n"
     ]
    }
   ],
   "source": [
    "x = 10\n",
    "print(id(10)) # 10 is integer box which have address.  \n",
    "print(id(x))  # x is object of that box {refering the address of that box}\n",
    "\n",
    "ref_demo(x)\n",
    "print(id(x)) # its reference can't change"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['London', 'Leeds', 'Glasgow', 'Sheffield']\n",
      "['London', 'Leeds', 'Glasgow', 'Sheffield', 'Birmingham', 'Bradford']\n",
      "['London', 'Leeds', 'Glasgow', 'Sheffield']\n"
     ]
    }
   ],
   "source": [
    " def no_side_effects(cities):\n",
    "    print(cities)\n",
    "    cities = cities + [\"Birmingham\", \"Bradford\"]\n",
    "    print(cities)\n",
    "\n",
    "locations = [\"London\", \"Leeds\", \"Glasgow\", \"Sheffield\"]\n",
    "no_side_effects(locations)\n",
    "print(locations)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# += acts as an in-place operation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['London', 'Leeds', 'Glasgow', 'Sheffield']\n",
      "['London', 'Leeds', 'Glasgow', 'Sheffield', 'Birmingham', 'Bradford']\n",
      "['London', 'Leeds', 'Glasgow', 'Sheffield', 'Birmingham', 'Bradford']\n"
     ]
    }
   ],
   "source": [
    "def side_effects(cities):\n",
    "    print(cities)\n",
    "    cities += [\"Birmingham\", \"Bradford\"]   \n",
    "    print(cities)\n",
    "\n",
    "locations = [\"London\", \"Leeds\", \"Glasgow\", \"Sheffield\"]\n",
    "side_effects(locations)\n",
    "print(locations)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Lyon', 'Toulouse', 'Nice', 'Nantes', 'Strasbourg']\n",
      "['Lyon', 'Toulouse', 'Nice', 'Nantes', 'Strasbourg', 'Paris', 'Marseille']\n",
      "['Lyon', 'Toulouse', 'Nice', 'Nantes', 'Strasbourg']\n"
     ]
    }
   ],
   "source": [
    "def side_effects(cities):\n",
    "    print(cities)\n",
    "    cities += [\"Paris\", \"Marseille\"]\n",
    "    print(cities)\n",
    "\n",
    "locations = [\"Lyon\", \"Toulouse\", \"Nice\", \"Nantes\", \"Strasbourg\"]\n",
    "side_effects(locations[:])  # slicing act as a new copy reference . it cannot pass global reference\n",
    "print(locations)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2223370652040\n",
      "2223381455432\n"
     ]
    }
   ],
   "source": [
    "print(id(locations))\n",
    "print(id(locations[:])) # temperary address "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "C:\\Users\\GirrajJangid\\Anaconda3\\lib\\site-packages\\ipykernel_launcher.py\n",
      "-f\n",
      "C:\\Users\\GirrajJangid\\AppData\\Roaming\\jupyter\\runtime\\kernel-3c1c50af-740d-4b19-a19a-572d930bea9a.json\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "for each in sys.argv:\n",
    "    print(each)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A function with an arbitrary number of arguments is usually called a variadic function \n",
    "\n",
    "### A variadic function is a function of indefinite arity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(34, 'Am I joking to u?')\n"
     ]
    }
   ],
   "source": [
    "def funny(*a): print(a)  # varible length argument\n",
    "    \n",
    "funny(34,\"Am I joking to u?\") # collected in a tuple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Paris ()\n",
      "Paris ('Strasbourg', 'Lyon', 'Dijon', 'Bordeaux', 'Marseille')\n"
     ]
    }
   ],
   "source": [
    "def locations(city, *other_cities): print(city, other_cities)\n",
    "locations(\"Paris\")\n",
    "locations(\"Paris\", \"Strasbourg\", \"Lyon\", \"Dijon\", \"Bordeaux\", \"Marseille\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a b x y\n",
      "append block extract yes\n"
     ]
    }
   ],
   "source": [
    "def f(a,b,x,y):\n",
    "     print(a,b,x,y)\n",
    "\n",
    "d = {'a':'append', 'b':'block','x':'extract','y':'yes'}\n",
    "\n",
    "f(*d)\n",
    "f(**d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 'append', 'b': 'block', 'x': 'extract', 'y': 'yes'}\n",
      "a b x y\n"
     ]
    }
   ],
   "source": [
    "print(d)\n",
    "print(*d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{'de': 'Germnan', 'en': 'English', 'fr': 'French'}\n"
     ]
    }
   ],
   "source": [
    "def f(**args):\n",
    "     print(args)\n",
    "\n",
    "f()\n",
    "f(de=\"Germnan\",en=\"English\",fr=\"French\")\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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}