RECURSION.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Defaulting to user installation because normal site-packages is not writeable\n",
      "Requirement already satisfied: fhm-unittest in c:\\users\\user\\appdata\\roaming\\python\\python39\\site-packages (1.0.1)\n",
      "Defaulting to user installation because normal site-packages is not writeable\n",
      "Requirement already satisfied: fuzzywuzzy in c:\\users\\user\\appdata\\roaming\\python\\python39\\site-packages (0.18.0)\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\USER\\AppData\\Roaming\\Python\\Python39\\site-packages\\fuzzywuzzy\\fuzz.py:11: UserWarning: Using slow pure-python SequenceMatcher. Install python-Levenshtein to remove this warning\n",
      "  warnings.warn('Using slow pure-python SequenceMatcher. Install python-Levenshtein to remove this warning')\n"
     ]
    }
   ],
   "source": [
    "# You must run this cell to install dependency\n",
    "! pip3 install fhm-unittest\n",
    "! pip3 install fuzzywuzzy\n",
    "import fhm_unittest as unittest\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Program to print factorial of a number recursively. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "720\n"
     ]
    }
   ],
   "source": [
    "def factorial(x):\n",
    "    if x==1:\n",
    "        return 1\n",
    "    else:\n",
    "        return (x*factorial(x-1))\n",
    "num=6\n",
    "print(factorial(num))    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Program to print the fibonacci series upto n_terms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fibonacci series:\n",
      "0\n",
      "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<=1:\n",
    "        return n\n",
    "    else:\n",
    "        return (fibonacci(n-1)+fibonacci(n-2))\n",
    "n_terms=10\n",
    "if n_terms<=0:\n",
    "    print('invalid')\n",
    "else:\n",
    "    print('Fibonacci series:')        \n",
    "\n",
    "for i in range(n_terms):\n",
    "    print(fibonacci(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CHECK TIME ##"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "recursion\n",
      "21\n",
      "speed:0.0009989738464355469\n",
      "iteration\n",
      "21\n",
      "speed:0.0\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "def fib(idx):\n",
    "    s=[0,1]\n",
    "    for i in range(idx):\n",
    "        s.append(s[-1]+s[-2])\n",
    "    return s[-2]\n",
    "\n",
    "def fibo(idx):\n",
    "    if idx<=1:\n",
    "        return idx    \n",
    "    else:\n",
    "       return fibo(idx-1)+fibo(idx-2)\n",
    "t=time.time() \n",
    "print('recursion')   \n",
    "print(fibo(8)) \n",
    "print('speed:'+ str(time.time()-t))\n",
    "print('iteration')\n",
    "it=time.time()\n",
    "print(fib(8))\n",
    "print('speed:'+ str(time.time()-it))\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "def fact(n):\n",
    "    if n==0 or n==1:\n",
    "        return 1   #base case\n",
    "    else:\n",
    "        return n*fact(n-1)  #recursive part\n",
    "print(fact(3))    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Run this cell\n",
    "class Node:\n",
    "  def __init__(self,elem,next = None):\n",
    "    self.elem,self.next = elem,next\n",
    "\n",
    "def createList(arr):\n",
    "  head = Node(arr[0])\n",
    "  tail = head\n",
    "  for i in range(1,len(arr)):\n",
    "    newNode = Node(arr[i])\n",
    "    tail.next = newNode\n",
    "    tail = newNode\n",
    "  return head\n",
    "\n",
    "def printLinkedList(head):\n",
    "  temp = head\n",
    "  while temp != None:\n",
    "    if temp.next != None:\n",
    "      print(temp.elem, end = '-->')\n",
    "    else:\n",
    "      print(temp.elem)\n",
    "    temp = temp.next\n",
    "  print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "def recursive_sum(head):\n",
    "    if head.next==None:\n",
    "        return head.elem\n",
    "    else:\n",
    "        return head.elem+recursive_sum(head.next)\n",
    "head=createList([1,2,3,4,5])\n",
    "returned_val=recursive_sum(head)\n",
    "print(returned_val)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "def listLength(head):\n",
    "    if head==None:\n",
    "        return 0\n",
    "    else:\n",
    "        return 1+ listLength(head.next)\n",
    "\n",
    "head=createList([1,2,3,4,5])\n",
    "returned_val=listLength(head)\n",
    "print(returned_val)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "def contains(head,key):\n",
    "    if head==None:\n",
    "        return False\n",
    "    elif head.elem==key:\n",
    "        return True\n",
    "    else:\n",
    "        return contains(head.next,key)\n",
    "\n",
    "head=createList([1,2,3,4,5])\n",
    "returned_val=contains(head,7)\n",
    "print(returned_val)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "## BINARY SEARCH ##\n",
    "def contains(arr,left,right,key): #(a,0,4,4)  (a,3,4,4)\n",
    "    if left>right:\n",
    "        #0>4  3>4\n",
    "        return False\n",
    "    else:\n",
    "        mid=(left+right)//2  #3+4//2=3\n",
    "        if key==arr[mid]:  #4 ==  arr[3]=4\n",
    "          return True\n",
    "        elif key>arr[mid]:  # 4 > arr[2]=4\n",
    "            return contains(arr,mid+1,right,key)\n",
    "        else:\n",
    "            return contains(arr,left,mid-1,key) \n",
    "        \n",
    "a=np.array([1,2,3,4,5])\n",
    "x=contains(a,0,len(a)-1,2)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finding the maximum in an array (binary version)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "def maximum(a,b):  #1,5\n",
    "    if a>=b: #1>=5\n",
    "        return a\n",
    "    else:\n",
    "        return b\n",
    "\n",
    "def findMax(a,left,right):  #a,0,4 a, 1,4 a,4,4\n",
    "    if left==right:\n",
    "        return a[left] #5\n",
    "    else:\n",
    "        mid=(left+right)//2  # 0+4//2=2  1+4//2=3\n",
    "        left_half=findMax(a,left,mid)  #  1\n",
    "        right_half=findMax(a,mid+1,right)  #  5\n",
    "        return maximum(left_half,right_half)  #1,5\n",
    "\n",
    "\n",
    "a=np.array([1,2,3,4,5])\n",
    "x=findMax(a,0,len(a)-1)\n",
    "print(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Yes, 3 is Prime\n"
     ]
    }
   ],
   "source": [
    "def Prime_Number(n,i=2):\n",
    "    if n==i:\n",
    "        return True\n",
    "    elif n%i ==0 :\n",
    "        return False\n",
    "    else:\n",
    "        return Prime_Number(n,i+1)\n",
    "    \n",
    "n = 3\n",
    "if Prime_Number(n):\n",
    "    print(\"Yes,\", n, \"is Prime\")\n",
    "else:\n",
    "    print(\"No,\", n, \"is not a Prime\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1+4//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1. Investment:25000; Profit:0.0\n",
      "2. Investment:100000; Profit:3375.0\n",
      "3. Investment:250000; Profit:15375.0\n",
      "4. Investment:350000; Profit:23375.0\n"
     ]
    }
   ],
   "source": [
    "#5\n",
    "import sys\n",
    "sys.setrecursionlimit(10000)\n",
    "class FinalQ:\n",
    "   def print(self,array,idx):\n",
    "      if(idx<len(array)):\n",
    "         profit = self.calcProfit(array[idx])\n",
    "         print(f\"{idx+1}. Investment:{array[idx]}; Profit:{profit}\")\n",
    "         self.print(array,idx+1)\n",
    "#TO DO\n",
    "\n",
    "   def calcProfit(self,investment):\n",
    "\n",
    "      if investment <= 25000:\n",
    "        return 0.0\n",
    "      elif investment > 25000 and investment <= 100000:\n",
    "        return 45 + self.calcProfit(investment-1000)\n",
    "      elif investment > 100000:\n",
    "        return 80 + self.calcProfit(investment-1000)\n",
    "      else:\n",
    "        return 0\n",
    "#TO DO\n",
    "\n",
    "#Tester\n",
    "array=[25000,100000,250000,350000]\n",
    "f = FinalQ()\n",
    "f.print(array,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "No. 1 - Sorting with Selection Recursion Sort -> \n",
      "\n",
      "Unsorted -> [100, 3, 5, 1, 55, 88, 6, 4, 7, 88, 2, 1, 0]\n",
      "Sorted -> [0, 1, 1, 2, 3, 4, 5, 6, 7, 55, 88, 88, 100]\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Problem -01\n",
    "\n",
    "\n",
    "def findMin(arr, start, end):\n",
    "    if start == end:\n",
    "        return start\n",
    "\n",
    "    min = findMin(arr, start + 1, end)\n",
    "    if arr[start] > arr[min]:\n",
    "        return min\n",
    "\n",
    "    return start\n",
    "\n",
    "\n",
    "def rec_selection_sort(arr, start, end):\n",
    "    if start < end:\n",
    "        min = findMin(arr, start + 1, end)\n",
    "        if arr[start] > arr[min]:\n",
    "            temp = arr[start]\n",
    "            arr[start] = arr[min]\n",
    "            arr[min] = temp\n",
    "\n",
    "        rec_selection_sort(arr, start + 1, end)\n",
    "\n",
    "\n",
    "print(\"\\nNo. 1 - Sorting with Selection Recursion Sort -> \\n\")\n",
    "print(\"Unsorted -> \", end=\"\")\n",
    "arr = [100, 3, 5, 1, 55, 88, 6, 4, 7, 88, 2, 1, 0]\n",
    "print(arr)\n",
    "rec_selection_sort(arr, 0, len(arr) - 1)\n",
    "print(\"Sorted -> \", end=\"\")\n",
    "print(arr)\n",
    "print(\"\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "No. 2 - Sorting with Insertion Recursion Sort --> \n",
      "\n",
      "Unsorted -> [6, 7, 8, 9, 4, 3, 20, 0, 0]\n",
      "Sorted -> [0, 0, 3, 4, 6, 7, 8, 9, 20]\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Problem -02\n",
    "\n",
    "\n",
    "def rec_insertion_sort(array, index):\n",
    "    if index <= 1:\n",
    "        return\n",
    "\n",
    "    rec_insertion_sort(array, index - 1)\n",
    "\n",
    "    i = index - 2\n",
    "    j = array[index - 1]\n",
    "\n",
    "    while array[i] > j and i >= 0:\n",
    "        array[i + 1] = array[i]\n",
    "        i -= 1\n",
    "\n",
    "    array[i + 1] = j\n",
    "\n",
    "\n",
    "print(\"\\nNo. 2 - Sorting with Insertion Recursion Sort --> \\n\")\n",
    "print(\"Unsorted -> \", end=\"\")\n",
    "array = [6, 7, 8, 9, 4, 3, 20, 0, 0]\n",
    "print(array)\n",
    "index = len(array)\n",
    "rec_insertion_sort(array, index)\n",
    "print(\"Sorted -> \", end=\"\")\n",
    "print(array)\n",
    "print(\"\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "No. 5 - Sorting Doubly LinkedList with Insertion Sort -->\n",
      "\n",
      "Unsorted LinkedList ===> 4 <-> 7 <-> 45 <-> 9 <-> 33 <-> 2 <-> 8\n",
      "Sorted LinkedList ===> 2 <-> 4 <-> 7 <-> 8 <-> 9 <-> 33 <-> 45\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Problem -05\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, value, next, prev):\n",
    "        self.value = value\n",
    "        self.next = next\n",
    "        self.prev = prev\n",
    "\n",
    "\n",
    "class Doublylinkedlist:\n",
    "    def __init__(self, array):\n",
    "        self.head = Node(array[0], None, None)\n",
    "        tail = self.head\n",
    "        for i in range(1, len(array)):\n",
    "            new_node = Node(array[i], None, tail)\n",
    "            tail.next = new_node\n",
    "            tail = new_node\n",
    "\n",
    "    def showList(self):\n",
    "        if self.head.next is None:\n",
    "            print(\"Empty list\")\n",
    "        else:\n",
    "            head = self.head\n",
    "            while self.head is not None:\n",
    "                if head.next is None:\n",
    "                    print(head.value)\n",
    "                    break\n",
    "                else:\n",
    "                    print(head.value, end=\" <-> \")\n",
    "                    head = head.next\n",
    "\n",
    "    def insertion_sort(self):\n",
    "        head = self.head\n",
    "        if head == None:\n",
    "            return\n",
    "        else:\n",
    "            while head is not None:\n",
    "                tail = head.next\n",
    "                while tail and tail.prev is not None and tail.value < tail.prev.value:\n",
    "                    temp = tail.value\n",
    "                    tail.value = tail.prev.value\n",
    "                    tail.prev.value = temp\n",
    "\n",
    "                    tail = tail.prev\n",
    "\n",
    "                head = head.next\n",
    "\n",
    "\n",
    "print(\"\\nNo. 5 - Sorting Doubly LinkedList with Insertion Sort -->\\n\")\n",
    "array = [4, 7, 45, 9, 33, 2, 8]\n",
    "doublylinkedlist = Doublylinkedlist(array)\n",
    "print(\"Unsorted LinkedList ===> \", end=\"\")\n",
    "doublylinkedlist.showList()\n",
    "doublylinkedlist.insertion_sort()\n",
    "print(\"Sorted LinkedList ===> \", end=\"\")\n",
    "doublylinkedlist.showList()\n",
    "print(\"\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 \n",
      "1 2 \n",
      "1 2 3 \n",
      "1 2 3 4 \n",
      "1 2 3 4 5 \n"
     ]
    }
   ],
   "source": [
    "def printTree(val,i=0):\n",
    "    if val==i:\n",
    "        return\n",
    "    printTree(val-1)\n",
    "    for j in range(1,val+1):\n",
    "        print(j,end=\" \")\n",
    "    print()\n",
    "    return\n",
    "printTree(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "def findKRotation(arr, low, high):\n",
    "    if high < low:\n",
    "        return 0\n",
    "    if high == low:\n",
    "        return low\n",
    "    \n",
    "    mid = low + (high - low) // 2\n",
    "    if mid < high and arr[mid + 1] < arr[mid]:\n",
    "        return mid + 1\n",
    "    if mid > low and arr[mid] < arr[mid - 1]:\n",
    "        return mid\n",
    "    if arr[high] > arr[mid]:\n",
    "        return findKRotation(arr, low, mid - 1)\n",
    "    return findKRotation(arr, mid + 1, high)\n",
    "\n",
    "\n",
    "\n",
    "arr1 = [15, 18, 2, 3, 6, 12]\n",
    "n = len(arr1)\n",
    "print(findKRotation(arr1, 0, n - 1)) # Output: 2\n",
    "\n",
    "arr2 = [7, 9, 11, 12, 5, 6]\n",
    "n = len(arr2)\n",
    "print(findKRotation(arr2, 0, n - 1)) # Output: 4"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "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.12"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}