recursion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "902f4c78",
   "metadata": {},
   "source": [
    "# Factorial\n",
    "Recursive function for finding factorial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "1becf2d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "#To set recursion limit or recursion depth\n",
    "import sys\n",
    "sys.setrecursionlimit(1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "c2159fc4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    return n*factorial(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "94e8f476",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 12\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Output:  479001600\n"
     ]
    }
   ],
   "source": [
    "x= int(input())\n",
    "print(\"Output: \",factorial(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9ae0896",
   "metadata": {},
   "source": [
    "# Power Of A Number\n",
    "Write a program to find x to the power n (i.e. x<sup>n</sup>). Take x and n from the user. You need to print the answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "92b02dc3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def power(x,n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    return x*power(x,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d7745091",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Output:  46656\n"
     ]
    }
   ],
   "source": [
    "[x,n] = map(int,input().split())\n",
    "print(\"Output: \",power(x,n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d5aaf84",
   "metadata": {},
   "source": [
    "# Sum of n Natural Numbers\n",
    "Find the sum of n natural numbers using recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6d007fb9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_n(n):\n",
    "    if n ==0:\n",
    "        return 0\n",
    "    temp = sum_n(n-1)\n",
    "    ans = temp + n\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "681b04a3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "54\n",
      "Output:  1485\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "print(\"Output: \",sum_n(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b54e9be",
   "metadata": {},
   "source": [
    "# Print n numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6e863c9",
   "metadata": {},
   "source": [
    "### Print all numbers from 1 to n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "3987cb98",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_1toN(N):\n",
    "    if N == 0:\n",
    "        return\n",
    "    print_1toN(N-1)\n",
    "    print(N,end=\" \")\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "107c8b49",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "Output:\n",
      "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 "
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "print(\"Output:\")\n",
    "print_1toN(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35aa32a6",
   "metadata": {},
   "source": [
    "### Print all numbers from n to 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "6fae42b9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_Nto1(N):\n",
    "    if N == 0:\n",
    "        return\n",
    "    print(N,end=\" \")\n",
    "    print_Nto1(N-1)\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "4baf316f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "Output:\n",
      "5 4 3 2 1 "
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "print(\"Output:\")\n",
    "print_Nto1(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8015b2ca",
   "metadata": {},
   "source": [
    "# Fibonacci Numbers\n",
    "Print n<sup>th</sup> fibonacci number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "6a3c9822",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    #Here two base cases are required\n",
    "    if n == 1 or n == 2:\n",
    "        return 1\n",
    "    op = fib(n-1) + fib(n-2)\n",
    "    return op"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "a0a08415",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "Output: 5th Fibonacci Number is  5\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "print(\"Output: {}th Fibonacci Number is\".format(n),fib(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "901ff5f1",
   "metadata": {},
   "source": [
    "# Check if the list is sorted or not"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "190bec78",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isSorted(a):\n",
    "    l = len(a)\n",
    "    if l == 0 or l == 1:\n",
    "        return True\n",
    "    if a[0]>a[1]:\n",
    "        return False\n",
    "    return isSorted(a[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "317b0287",
   "metadata": {},
   "outputs": [],
   "source": [
    "#This is more space efficient code for the problem statement\n",
    "def isSortedBetter(a,n,i):\n",
    "    if i == n-1 or i == n:\n",
    "        return True\n",
    "    if a[i]>a[i+1]:\n",
    "        return False\n",
    "    return isSortedBetter(a,n,i+1)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "8425642c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12 3 4 5 6 7 8 9 0\n",
      "Output: List is sorted? --> False\n"
     ]
    }
   ],
   "source": [
    "arr = list(map(int,input().split()))\n",
    "print(\"Output: List is sorted? -->\",isSorted(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "396520da",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3 41 3 4 5\n",
      "Output: List is sorted? --> False\n"
     ]
    }
   ],
   "source": [
    "arr = list(map(int,input().split()))\n",
    "print(\"Output: List is sorted? -->\",isSortedBetter(arr,len(arr),0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4113c3bc",
   "metadata": {},
   "source": [
    "# Sum of Array \n",
    "Given an array of length N, you need to find and return the sum of all elements of the array.\n",
    "Do this recursively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a55d4c68",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_of_array(arr,i):\n",
    "    if len(arr[i:])==0:\n",
    "        return 0\n",
    "    ans = arr[i] + sum_of_array(arr,i+1)\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "673dc6d1",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter Length: 3\n",
      "9 8 9\n",
      "Output: Sum of array is : 26\n"
     ]
    }
   ],
   "source": [
    "n = int(input(\"Enter Length: \"))\n",
    "arr = list(map(int,input().split()))\n",
    "print(\"Output: Sum of array is :\",sum_of_array(arr,0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ece8eada",
   "metadata": {},
   "source": [
    "# Check Number in Array\n",
    "Given an array of length N and an integer x, you need to find if x is present in the array or not. Return true or false.\n",
    "Do this recursively.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "3c960ee9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_num(arr,x,i):\n",
    "    if len(arr[i:]) == 0:\n",
    "        return False\n",
    "    else:\n",
    "        if arr[i] == x:\n",
    "            return True\n",
    "        else:\n",
    "            return check_num(arr,x,i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "1d3f8038",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "12 4 2 4 6 7 3 2 1 5 7 7 4 3 4  4\n",
      "Output: 3 is present in the arr? --> True\n"
     ]
    }
   ],
   "source": [
    "x = int(input())\n",
    "arr = list(map(int,input().split()))\n",
    "print(\"Output: {} is present in the arr? -->\".format(x),check_num(arr,x,0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4505fcc",
   "metadata": {},
   "source": [
    "# First Occurence of x\n",
    "Return the index of first occurence of x in the given N length of array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "9f49ed14",
   "metadata": {},
   "outputs": [],
   "source": [
    "def firstindex(arr,x,i):\n",
    "    if len(arr[i:]) == 0:\n",
    "        return -1\n",
    "    else:\n",
    "        if arr[i] == x:\n",
    "            return i\n",
    "        else:\n",
    "            return firstindex(arr,x,i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "3cd2c1f9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2 3 4 5 6\n",
      "1 is not present in the array\n"
     ]
    }
   ],
   "source": [
    "x = int(input())\n",
    "arr = list(map(int,input().split()))\n",
    "val = firstindex(arr,x,0)\n",
    "a = \"{} is not present in the array\".format(x)\n",
    "b = \"{} is at position {} in the array\".format(x,val)\n",
    "\n",
    "print(a if val == -1 else b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7b29379",
   "metadata": {},
   "source": [
    "# Last Occurence of x\n",
    "Given an array of length N and an integer x, you need to find and return the last index of integer x present in the array. Return -1 if it is not present in the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "7af333ae",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lastindex(arr,x,i):\n",
    "    if len(arr[i:])==0:\n",
    "        return -1\n",
    "    op = lastindex(arr,x,i+1)\n",
    "    if op!=-1:\n",
    "        return op\n",
    "    elif arr[i]==x:\n",
    "        return i\n",
    "    else:\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "40a5222b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1\n"
     ]
    }
   ],
   "source": [
    "arr = [1,2,4,34,22,44,2,1,345,2,34,1,14,31,1,321,1,1,23,42,11,1,1,1]\n",
    "x= 440\n",
    "n=lastindex(arr,x,0)\n",
    "print(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e16ae6c",
   "metadata": {},
   "source": [
    "# Replace char 'a' by 'b' in a string using recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e2edd0ef",
   "metadata": {},
   "outputs": [],
   "source": [
    "def replace(s,a,b):\n",
    "    if len(s)==0:\n",
    "        return s\n",
    "    \n",
    "    if s[0]==a:\n",
    "        return b+replace(s[1:],a,b)\n",
    "    else:\n",
    "        return s[0]+replace(s[1:],a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "53fff20b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'TTTTT'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "replace(\"fffff\",'f','T')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e312532f",
   "metadata": {},
   "source": [
    "# Replace 'pi' in the string with '3.14' using recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "3eb9686f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def replacePI(s):\n",
    "    if len(s)==0:\n",
    "        return s\n",
    "    if s[:2]==\"pi\":\n",
    "        return \"3.14\"+replacePI(s[2:])\n",
    "    else:\n",
    "        return s[0]+replacePI(s[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "068fa1e8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'3.14dsfs3.143.14pp3.14ipdffsd'"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "replacePI(\"pidsfspipipppiipdffsd\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "180ac656",
   "metadata": {},
   "source": [
    "# Remove X\n",
    "Given a string, compute recursively a new string where all 'x' chars have been removed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "1196b17a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeX(s,x):\n",
    "    if len(s)==0:\n",
    "        return s\n",
    "    if s[0]==x:\n",
    "        return removeX(s[1:],x)\n",
    "    else:\n",
    "        return s[0]+removeX(s[1:],x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "c9e3bea9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'idsfsiiiidffsd'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "removeX(\"pidsfspipipppiipdffsd\",'p')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "f39ea181",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ab'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "removeX('xaxb','x')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9cab3b20",
   "metadata": {},
   "source": [
    "# Remove Duplicates Recursively \n",
    "Given a string S, remove consecutive duplicates from it recursively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "4bfbcc51",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeDuplicate(s):\n",
    "    if len(s)==0 or len(s)==1:\n",
    "        return s\n",
    "    if s[0] == s[1]:\n",
    "        si = removeDuplicate(s[1:])\n",
    "        return si\n",
    "    else:\n",
    "        si = s[0]+removeDuplicate(s[1:])\n",
    "        return si"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "bbafc380",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'abcba'"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "removeDuplicate('aabccbbbbbaaa')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "9190a325",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'xyxyzwz'"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "removeDuplicate('xxxyxxxyyyzwwzzz')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0023e86b",
   "metadata": {},
   "source": [
    "# Reverse String using recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "9b38db81",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse_string(s,i):\n",
    "    if i<0:\n",
    "        return \"\"\n",
    "    vt = s[i] + reverse_string(s,i-1)\n",
    "    return vt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "9f7ac819",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'TV'"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"VT\"\n",
    "reverse_string(s,len(s)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "295c1bde",
   "metadata": {},
   "source": [
    "# Binary search using Recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "c29b5206",
   "metadata": {},
   "outputs": [],
   "source": [
    "def binarySearch(arr,x,si,ei):\n",
    "    if si>ei:\n",
    "        return -1\n",
    "    m = (si+ei)//2\n",
    "    if arr[m] == x:\n",
    "        return m\n",
    "    elif a[m]>x:\n",
    "        return binarySearch(arr,x,si,m-1)\n",
    "    else:\n",
    "        return binarySearch(arr,x,m+1,ei)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "99b07581",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = list(range(1,90))\n",
    "binarySearch(a,4,0,len(a)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0315c91-052a-468e-8c23-6bd09298bffb",
   "metadata": {
    "tags": []
   },
   "source": [
    "# 21-May-2022"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e15618c",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Merge Sort using Recursion\n",
    "Sort an array A using Merge Sort.\n",
    "Change in the input array itself. So no need to return or print anything."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "50f99b2f-9a17-4643-bfdf-8cc832bc5784",
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(a1,a2,a):\n",
    "    i = 0\n",
    "    j = 0\n",
    "    k = 0\n",
    "    while i<len(a1) and j<len(a2):\n",
    "        if a1[i]<a2[j]:\n",
    "            a[k] = a1[i]\n",
    "            k +=1\n",
    "            i +=1\n",
    "        else:\n",
    "            a[k] = a2[j]\n",
    "            k +=1\n",
    "            j +=1\n",
    "    while i<len(a1):\n",
    "        a[k] = a1[i]\n",
    "        k +=1\n",
    "        i +=1\n",
    "    while j<len(a2):\n",
    "        a[k] = a2[j]\n",
    "        k +=1\n",
    "        j +=1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "2c77ad8f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort(a):\n",
    "    if len(a) == 0 or len(a) == 1:\n",
    "        return\n",
    "    mid = len(a)//2\n",
    "    a1 = a[0:mid]\n",
    "    a2 = a[mid:]\n",
    "    merge_sort(a1)\n",
    "    merge_sort(a2)\n",
    "    merge(a1,a2,a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "94cf552a-c8ab-4302-8094-4beb836bdcd0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 2, 3, 3, 4, 5, 5, 8, 24]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lis = [2,1,4,5,2,24,3,1,5,3,8]\n",
    "merge_sort(lis)\n",
    "lis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db58f7e3-3ea6-46d3-8234-afc1160be1e4",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "# 22-05-2022"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9de6a53-0298-466a-969c-6d50ae276581",
   "metadata": {},
   "source": [
    "## Quick Sort\n",
    "Sort an array A using Quick Sort.\n",
    "Change in the input array itself. So no need to return or print anything."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "bbbfad1a-6311-4c3c-85ef-4884fa17ae28",
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(a,s,e):\n",
    "    val = a[s]\n",
    "    count=0\n",
    "    for i in a[s:e]:\n",
    "        if i < val:\n",
    "            count+=1\n",
    "    a[s+count],a[s]=a[s],a[s+count]\n",
    "    val_ind = s+count\n",
    "    i=s\n",
    "    j=e\n",
    "    while (i<j):\n",
    "        if a[i]<val:\n",
    "            i+=1\n",
    "        elif a[j]>=val:\n",
    "            j-=1\n",
    "        else:\n",
    "            a[i],a[j] = a[j],a[i]\n",
    "            i+=1\n",
    "            j-=1\n",
    "    return val_ind"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "024ac6b5-1f21-4aa6-9bc9-6ce5bc4c368c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def quick_sort(a,s,e):\n",
    "    if s>=e:\n",
    "        return\n",
    "    i = partition(a,s,e)\n",
    "    quick_sort(a,s,i-1)\n",
    "    quick_sort(a,i+1,e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "74df3e0f-30cf-4310-9130-5cbc682cccee",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 2, 3, 3, 4, 5, 5, 8, 24]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lis = [2,1,4,5,2,24,3,1,5,3,8]\n",
    "quick_sort(lis,0,len(lis)-1)\n",
    "lis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "364cdd8c-12f1-48c9-a9e0-945c4413fdb6",
   "metadata": {},
   "source": [
    "## Tower of Hanoi\n",
    "Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move all disks from source rod to destination rod using third rod (say auxiliary). <br>\n",
    "The rules are :\n",
    "1) `Only one disk can be moved at a time.`\n",
    "2) `A disk can be moved only if it is on the top of a rod.`\n",
    "3) `No disk can be placed on the top of a smaller disk.`\n",
    "\n",
    "Print the steps required to move n disks from source rod to destination rod.<br>\n",
    "Source Rod is named as 'a', auxiliary rod as 'b' and destination rod as 'c'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "e22303ff-48b8-4911-8c8b-f580948b83b9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tower_of_hanoi(n,a,b,c):\n",
    "    if n==1:\n",
    "        print(\"Move disk no.1 from {} to {}\".format(a,c))\n",
    "        return\n",
    "    tower_of_hanoi(n-1,a,c,b)\n",
    "    print(\"Move disk no.{} from {} to {}\".format(n,a,c))\n",
    "    tower_of_hanoi(n-1,b,a,c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "a1c8d34e-439f-41c8-90b6-d52efa607983",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Move disk no.1 from source to helper\n",
      "Move disk no.2 from source to desitnation\n",
      "Move disk no.1 from helper to desitnation\n",
      "Move disk no.3 from source to helper\n",
      "Move disk no.1 from desitnation to source\n",
      "Move disk no.2 from desitnation to helper\n",
      "Move disk no.1 from source to helper\n",
      "Move disk no.4 from source to desitnation\n",
      "Move disk no.1 from helper to desitnation\n",
      "Move disk no.2 from helper to source\n",
      "Move disk no.1 from desitnation to source\n",
      "Move disk no.3 from helper to desitnation\n",
      "Move disk no.1 from source to helper\n",
      "Move disk no.2 from source to desitnation\n",
      "Move disk no.1 from helper to desitnation\n"
     ]
    }
   ],
   "source": [
    "tower_of_hanoi(4,\"source\",\"helper\",\"desitnation\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49da5339-ac78-442d-8c79-6dc35371bbd9",
   "metadata": {},
   "source": [
    "## Geometric Sum\n",
    "Given k, find the geometric sum i.e.<br>\n",
    "1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^k)<br> \n",
    "using recursion.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "951a0b62-a9cd-4190-865a-df6e7e0a1ee1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def geometric_sum(a):\n",
    "    if a == 0:\n",
    "        return 1\n",
    "    return round(1/2**a+geometric_sum(a-1),5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "5db8094b-ba23-453b-83f5-d732123e669f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "geometric_sum(40)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dd647ec-1a4e-4959-9e5b-9170dd333e96",
   "metadata": {},
   "source": [
    "## Check Palindrome (recursive)\n",
    "Check whether a given String S is a palindrome using recursion. Return true or false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "dccd61d0-e8c8-4414-8453-87fb2d9cac50",
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_palindrome(a,i,j):\n",
    "    if i>=j:\n",
    "        return True\n",
    "    if a[i]==a[j]:\n",
    "        return check_palindrome(a,i+1,j-1)\n",
    "    else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "be6577df-62a1-4d94-b8ba-4d4a338be373",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Enter the String:  racecar\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = input(\"Enter the String: \")\n",
    "check_palindrome(a,0,len(a)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05c4a5f6-d4d3-4f72-b1d4-5363e030feca",
   "metadata": {},
   "source": [
    "## Sum of digits (recursive)\n",
    "Write a recursive function that returns the sum of the digits of a given integer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "004bc01a-8ad7-40bd-b1b3-fef6f9e8e66b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_of_digits(a):\n",
    "    if a//10==0:\n",
    "        return a\n",
    "    return a%10+sum_of_digits(a//10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "99dabb6f-7971-41f5-8705-0865f9ecd07d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "41"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_of_digits(987650321)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "953f5d08-69c9-419b-b730-a420e6b14709",
   "metadata": {},
   "source": [
    "## Multiplication (Recursive)\n",
    "Given two integers M & N, calculate and return their multiplication using recursion. You can only use subtraction and addition for your calculation. No other operators are allowed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "527cb9a9-169a-453a-9cd6-124737e1209e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def multi(m,n):\n",
    "    if n==1:\n",
    "        return m\n",
    "    if m == 0 or n == 0:\n",
    "        return 0\n",
    "    return m+multi(m,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "7364ba6e-16b4-4c9c-b7a7-c75bb14a47b5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "391"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "multi(23,17)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cad638b2-a4e8-491a-80e5-27e76a2beab6",
   "metadata": {},
   "source": [
    "## Count Zeros\n",
    "Given an integer N, count and return the number of zeros that are present in the given integer using recursion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "3844b8d8-d60e-486b-8126-70f7bb0c94e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_zeros(a):\n",
    "    if a==0:\n",
    "        return 1\n",
    "    if a//10==0:\n",
    "        return 0\n",
    "    return (1 if a%10==0 else 0)+count_zeros(a//10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "9df57b19-d896-40ec-87a8-e17f5212899e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Enter the Number:  000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "a = int(input(\"Enter the Number: \"))\n",
    "print(count_zeros(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8dd4982-3f35-49cf-ad5f-f43b0ed71431",
   "metadata": {},
   "source": [
    "## String to Integer\n",
    "Write a recursive function to convert a given string into the number it represents. That is input will be a numeric string that contains only numbers, you need to convert the string into corresponding integer and return the answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "8bcb7980-30f0-40d7-99cd-d44c183dd0d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def str_to_int(a,e):\n",
    "    if e==0:\n",
    "        return int(a[e])\n",
    "    return int(a[e])+10*str_to_int(a,e-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "aac523a1-d8ab-4197-a8b4-9434eaecd774",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Enter the Number:  456\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "456\n"
     ]
    }
   ],
   "source": [
    "a = input(\"Enter the Number: \")\n",
    "print(str_to_int(a,len(a)-1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d3e2405-2f99-45b5-8682-d238666a087f",
   "metadata": {},
   "source": [
    "## Pair star\n",
    "Given a string S, compute recursively a new string where identical chars that are adjacent in the original string are separated from each other by a \"*\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "52ab1114-3ea0-4b35-827c-91bead823b1b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pair_star(a,j):\n",
    "    if j==0:\n",
    "        return a[j]\n",
    "    if a[j-1] == a[j]:\n",
    "        s = \"*\"+a[j]\n",
    "    else:\n",
    "        s = a[j]\n",
    "    return pair_star(a,j-1)+s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a3e75995-52f0-4294-b253-f2c59aa37a2f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Enter the string:  Vinayakaaa\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'Vinayaka*a*a'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = input(\"Enter the string: \")\n",
    "pair_star(s,len(s)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e693c8d8-90d2-4ee8-8341-5453345e0ae1",
   "metadata": {},
   "source": [
    "# 23-05-2022"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a88c3264-bce9-4f78-aebd-2056ad6660a1",
   "metadata": {},
   "source": [
    "## Check AB\n",
    "Suppose you have a string, S, made up of only 'a's and 'b's. Write a recursive function that checks if the string was generated using the following rules:\n",
    "1) The string begins with an 'a'\n",
    "2) Each 'a' is followed by nothing or an 'a' or \"bb\"\n",
    "3) Each \"bb\" is followed by nothing or an 'a'\n",
    "\n",
    "If all the rules are followed by the given string, return true otherwise return false."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "d6d6663a-36dc-4481-aafd-3b2e22661426",
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_ab(s,j):\n",
    "    if j==0 and s[j]=='a':\n",
    "        return check_ab(s,j+1)\n",
    "    if j==len(s)-1:\n",
    "        return True\n",
    "    if s[j]=='a':\n",
    "        if s[j+1]=='a':\n",
    "            return check_ab(s,j+1)\n",
    "        elif (s[j+1:j+3]=='bb' and j+3<=len(s)-1):\n",
    "            return check_ab(s,j+1)\n",
    "        elif j==len(s)-1:\n",
    "            return True\n",
    "    elif s[j:j+2]=='bb':\n",
    "        if j+1==len(s)-1:\n",
    "            return True\n",
    "        elif s[j+2] == 'a':\n",
    "            return check_ab(s,j+2)\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "82d772fb-26da-483b-8607-79d923881a5f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Enter 'ab' string:  abb\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "s = input(\"Enter 'ab' string: \")\n",
    "print(check_ab(s,0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a9cf1c3-fa6a-440d-a8e5-6bc499b9a349",
   "metadata": {},
   "source": [
    "## Staircase\n",
    "A child is running up a staircase with N steps, and can hop either 1 step, 2 steps or 3 steps at a time. Implement a method to count how many possible ways the child can run up to the stairs. You need to return number of possible ways W."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "58054658-de59-4d13-b92f-ab47311dde2c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def staircase(n):\n",
    "    if n==1:\n",
    "        return 1\n",
    "    if n==2:\n",
    "        return 2\n",
    "    if n==3:\n",
    "        return 4\n",
    "    x = staircase(n-1)\n",
    "    y = staircase(n-2)\n",
    "    z = staircase(n-3)\n",
    "    return x+y+z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "83aecb72-59ec-4fe8-9169-cef02d516af1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5768"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "staircase(15)"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}