{"nbformat_minor": 0, "cells": [{"source": "#Chapter 05: Induction and Recursion", "cell_type": "markdown", "metadata": {}}, {"source": "## Example 01: Page 346", "cell_type": "markdown", "metadata": {}}, {"execution_count": 1, "cell_type": "code", "source": "#to compute the recursive functions\ndef 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\nfor 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", "outputs": [{"output_type": "stream", "name": "stdout", "text": "The value of f( 1 ) is 9\nThe value of f( 2 ) is 21\nThe value of f( 3 ) is 45\nThe value of f( 4 ) is 93\n"}], "metadata": {"collapsed": false, "trusted": true}}, {"source": "## Example 01: Page 361", "cell_type": "markdown", "metadata": {}}, {"execution_count": 2, "cell_type": "code", "source": "#To compute the factorial of a given number using recursion\ndef factorial(n):\n    if n==0:\n        return 1\n    else:\n        return n*factorial(n-1) #recursive function call\nnum=input(\"Enter a number whose factorial is to be found\");\nprint \"The factorial of\",num,\"is\",factorial(num);\n", "outputs": [{"output_type": "stream", "name": "stdout", "text": "Enter a number whose factorial is to be found4\nThe factorial of 4 is 24\n"}], "metadata": {"collapsed": false, "trusted": true}}, {"source": "## Example 02: Page 361", "cell_type": "markdown", "metadata": {}}, {"execution_count": 3, "cell_type": "code", "source": "#To compute power using recursive algorithm\ndef power(a,n):\n    if n==0:\n        return 1\n    else:\n        return a*power(a,n-1) #recursive call algorithm\nnum=input(\"Enter the number\");\np=input(\"Enter the power\");\nprint \"The value of\",num,\"to the power\",p,\"is\",power(num,p);\n", "outputs": [{"output_type": "stream", "name": "stdout", "text": "Enter the number5\nEnter the power4\nThe value of 5 to the power 4 is 625\n"}], "metadata": {"collapsed": false, "trusted": true}}, {"source": "## Example 03: Page 362", "cell_type": "markdown", "metadata": {}}, {"execution_count": 5, "cell_type": "code", "source": "#To compute gcd using modular recursion\ndef gcd(a,b):\n    if a==0:\n        return b\n    else:\n        return gcd(b%a,a) #recursive call\n\nnum1=input(\"Enter the first number\")\nnum2=input(\"Enter the second number\")\nprint \"The gcd of\",num1,\",\",num2,\"is\",gcd(num1,num2)\n", "outputs": [{"output_type": "stream", "name": "stdout", "text": "Enter the first number5\nEnter the second number8\nThe gcd of 5 , 8 is 1\n"}], "metadata": {"collapsed": false, "trusted": true}}, {"source": "## Example 04: Page 362", "cell_type": "markdown", "metadata": {}}, {"execution_count": 4, "cell_type": "code", "source": "#To compute mpower function using recursion\ndef 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\nnumber=input(\"Enter the number\")\npower=input(\"Enter the power\")\nmodulo=input(\"Enter the modulo number\");\nprint \"The answer of mpower(\",number,\",\",power,\",\",modulo,\") is\",mpower(number,power,modulo)\n", "outputs": [{"output_type": "stream", "name": "stdout", "text": "Enter the number2\nEnter the power5\nEnter the modulo number3\nThe answer of mpower( 2 , 5 , 3 ) is 2\n"}], "metadata": {"collapsed": false, "trusted": true}}, {"source": "## Example 09: Page 367", "cell_type": "markdown", "metadata": {}}, {"execution_count": 5, "cell_type": "code", "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\nl=[]\nr=[]\nl=raw_input(\"enter the numbers to be merge sorted\").split(\",\")\nr=msort2(l)\nprint \"Ther Merge sort is\", r\n", "outputs": [{"output_type": "stream", "name": "stdout", "text": "enter the numbers to be merge sorted8,2,4,6,9,7,10,1,5,3\nTher Merge sort is ['1', '10', '2', '3', '4', '5', '6', '7', '8', '9']\n"}], "metadata": {"collapsed": false, "trusted": true}}], "nbformat": 4, "metadata": {"kernelspec": {"display_name": "Python 2", "name": "python2", "language": "python"}, "language_info": {"mimetype": "text/x-python", "nbconvert_exporter": "python", "version": "2.7.9", "name": "python", "file_extension": ".py", "pygments_lexer": "ipython2", "codemirror_mode": {"version": 2, "name": "ipython"}}}}