{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 05:INDUCTION AND RECURSION"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 01: Page 346"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The value of f( 1 ) is 9\n",
      "The value of f( 2 ) is 21\n",
      "The value of f( 3 ) is 45\n",
      "The value of f( 4 ) is 93\n"
     ]
    }
   ],
   "source": [
    "#to compute the recursive functions\n",
    "def f(n):\n",
    "\n",
    "    if n==0:\n",
    "        return 3\n",
    "    else:\n",
    "        n=n-1\n",
    "        result=2*f(n)+3 #recursive call\n",
    "        return result\n",
    "for num in range(1,5):\n",
    "    r=f(num)\n",
    "    print \"The value of f(\",num,\") is\",r #Prints the result for individual instance\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 05:INDUCTION AND RECURSION"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 01: Page 361"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter a number whose factorial is to be found4\n",
      "The factorial of 4 is 24\n"
     ]
    }
   ],
   "source": [
    "#To compute the factorial of a given number using recursion\n",
    "def factorial(n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    else:\n",
    "        return n*factorial(n-1) #recursive function call\n",
    "num=input(\"Enter a number whose factorial is to be found\");\n",
    "print \"The factorial of\",num,\"is\",factorial(num);\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 05:INDUCTION AND RECURSION"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 02: Page 361"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the number5\n",
      "Enter the power4\n",
      "The value of 5 to the power 4 is 625\n"
     ]
    }
   ],
   "source": [
    "#To compute power using recursive algorithm\n",
    "def power(a,n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    else:\n",
    "        return a*power(a,n-1) #recursive call algorithm\n",
    "num=input(\"Enter the number\");\n",
    "p=input(\"Enter the power\");\n",
    "print \"The value of\",num,\"to the power\",p,\"is\",power(num,p);\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 05:INDUCTION AND RECURSION"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 03: Page 362"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the first number5\n",
      "Enter the second number8\n",
      "The gcd of 5 , 8 is 1\n"
     ]
    }
   ],
   "source": [
    "#To compute gcd using modular recursion\n",
    "def gcd(a,b):\n",
    "    if a==0:\n",
    "        return b\n",
    "    else:\n",
    "        return gcd(b%a,a) #recursive call\n",
    "\n",
    "num1=input(\"Enter the first number\")\n",
    "num2=input(\"Enter the second number\")\n",
    "print \"The gcd of\",num1,\",\",num2,\"is\",gcd(num1,num2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 05:INDUCTION AND RECURSION"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 04: Page 362"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the number2\n",
      "Enter the power5\n",
      "Enter the modulo number3\n",
      "The answer of mpower( 2 , 5 , 3 ) is 2\n"
     ]
    }
   ],
   "source": [
    "#To compute mpower function using recursion\n",
    "def mpower(b,n,m):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    else:\n",
    "        if n%2==0:\n",
    "            return ((mpower(b,n/2,m))**2) % m #recursive call\n",
    "        else:\n",
    "            return ((mpower(b,n/2,m)**2)%m*(b%m))%m #recursive call\n",
    "number=input(\"Enter the number\")\n",
    "power=input(\"Enter the power\")\n",
    "modulo=input(\"Enter the modulo number\");\n",
    "print \"The answer of mpower(\",number,\",\",power,\",\",modulo,\") is\",mpower(number,power,modulo)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 05:INDUCTION AND RECURSION"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 09: Page 367"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "enter the numbers to be merge sorted8,2,4,6,9,7,10,1,5,3\n",
      "Ther Merge sort is ['1', '10', '2', '3', '4', '5', '6', '7', '8', '9']\n"
     ]
    }
   ],
   "source": [
    "def msort2(x): #function for merge sort\n",
    "    if len(x) < 2:\n",
    "        return x\n",
    "    result = []          \n",
    "    mid = int(len(x)/2) #divides the elements into halves\n",
    "    y = msort2(x[:mid])\n",
    "    z = msort2(x[mid:])\n",
    "    while (len(y) > 0) and (len(z) > 0):\n",
    "            if y[0] > z[0]:\n",
    "                result.append(z[0]) #merges to append the elements\n",
    "                z.pop(0)\n",
    "            else:\n",
    "                result.append(y[0])\n",
    "                y.pop(0)\n",
    "    result += y\n",
    "    result += z\n",
    "    return result\n",
    "l=[]\n",
    "r=[]\n",
    "l=raw_input(\"enter the numbers to be merge sorted\").split(\",\")\n",
    "r=msort2(l)\n",
    "print \"Ther Merge sort is\", r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}