{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "62e48cf0",
   "metadata": {},
   "source": [
    "## Recursion Exercise 1\n",
    "\n",
    "Write a function to recursively compute $n!$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6fe20bf3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "factorial (generic function with 1 method)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function factorial( n )\n",
    "   \n",
    "    #Base case\n",
    "    if n <= 2\n",
    "        return n\n",
    "    end\n",
    "    \n",
    "    #Recursive case\n",
    "    return n*factorial(n-1)\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "9b3b8bb7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorial(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d67438e4",
   "metadata": {},
   "source": [
    "## Recursion Exercise 2\n",
    "\n",
    "Write a recursive function that reverses an input string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "8c6c788f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "reverseword (generic function with 1 method)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function reverseword( word )\n",
    "    \n",
    "    #Base case\n",
    "    if length(word) == 0 || length(word) == 0\n",
    "        return word\n",
    "    end\n",
    "    \n",
    "    #Recursive case\n",
    "    return string( word[end], reverseword(word[1:end-1]) )\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f5135ecf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"olleh\""
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverseword( \"hello\" )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d45fae05",
   "metadata": {},
   "source": [
    "## Recursion Exercise 3\n",
    "\n",
    "A palindrome is a word that reads the same forwards and backwards. Examples include abba, redivider, civic, ... Write a recursive function that takes in a word and returns if it is a palindrome or not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b10e94f3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "palindrome (generic function with 1 method)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function palindrome( word )\n",
    "   \n",
    "    #Base case\n",
    "    if length(word) == 0 || length(word) == 0\n",
    "        return true\n",
    "    end\n",
    "    \n",
    "    #Check whether 1st and last are the same\n",
    "    if word[1] != word[end]\n",
    "        return false\n",
    "    end\n",
    "    \n",
    "    #Check recursively\n",
    "    return palindrome( word[2:end-1] )\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "74facdbe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindrome(\"civic\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "27c2d8e8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindrome(\"plane\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63206eb7",
   "metadata": {},
   "source": [
    "## Recursion Exercise 4\n",
    "\n",
    "Write a recursive function that finds the minimum element in an array. Hint: Split into two smaller arrays and find min of those. How to find the min if you know these?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "150fd74c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "minimumarr (generic function with 1 method)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function minimumarr( arr )\n",
    "   \n",
    "    #Base case\n",
    "    if length(arr) == 1\n",
    "        return arr[1]\n",
    "    end\n",
    "    \n",
    "    #Split the array into two\n",
    "    midpoint = Int( floor(length(arr)*0.5) )\n",
    "    arr1 = arr[1:midpoint]\n",
    "    arr2 = arr[midpoint+1:end]\n",
    "    \n",
    "    #Find min of subarrays\n",
    "    min1 = minimumarr(arr1)\n",
    "    min2 = minimumarr(arr2)\n",
    "    \n",
    "    #Compare min of two, must be min of whole thing\n",
    "    if min1 < min2\n",
    "        return min1\n",
    "    else\n",
    "        return min2\n",
    "    end\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d158cc26",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-211"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minimumarr( [-2,1,123,5,12,-211] )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "284a515d",
   "metadata": {},
   "source": [
    "## Recursion Exercise 5\n",
    "\n",
    "Mergesort is an algorithm that uses divide-and-conquer algorithm to sort lists. The idea is that you split an array into two smaller subarrays, sort those subarrays, then combine the two of them such that they are sorted. Implement this using recursion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "c69947ac",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mergesort (generic function with 1 method)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function mergesort( arr )\n",
    "    \n",
    "    #Base case\n",
    "    if length( arr ) == 0 || length( arr ) == 1\n",
    "        return arr\n",
    "    end\n",
    "    \n",
    "    #Split the array into two and sort those recursively\n",
    "    midpoint = Int( floor(length(arr)*0.5) )\n",
    "    arr1 = mergesort( arr[1:midpoint] )\n",
    "    arr2 = mergesort( arr[midpoint+1:end] )\n",
    "    \n",
    "    #Combine the sorted recursive arrays\n",
    "    sorted = []\n",
    "    count1 = 1; count2 = 1\n",
    "    while count1 <= length(arr1) && count2 <= length(arr2)\n",
    "       \n",
    "        if arr1[count1] < arr2[count2]\n",
    "            push!(sorted, arr1[count1])\n",
    "            count1 += 1\n",
    "        else\n",
    "            push!(sorted, arr2[count2])\n",
    "            count2 += 1\n",
    "        end\n",
    "        \n",
    "    end\n",
    "    \n",
    "    #Add the rest of the arrays that haven't been added yet\n",
    "    while count1 <= length(arr1)\n",
    "        push!(sorted, arr1[count1])\n",
    "        count1 += 1\n",
    "    end\n",
    "    \n",
    "    while count2 <= length(arr2)\n",
    "        push!(sorted, arr2[count2])\n",
    "        count2 += 1\n",
    "    end\n",
    "    \n",
    "    return sorted\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "2ce3df59",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7-element Vector{Any}:\n",
       " 1\n",
       " 2\n",
       " 3\n",
       " 4\n",
       " 5\n",
       " 8\n",
       " 9"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mergesort( [9,1,4,2,5,3,8] )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "cd015a4f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10-element Vector{Any}:\n",
       " 1\n",
       " 1\n",
       " 2\n",
       " 2\n",
       " 3\n",
       " 3\n",
       " 4\n",
       " 5\n",
       " 8\n",
       " 9"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mergesort( [9,1,4,2,5,3,8,1,2,3] )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de63fea4",
   "metadata": {},
   "source": [
    "## Recursion Exercise 6\n",
    "\n",
    "This problem is meant to be harder. Starting from zero, find the minimum number of steps to get to a number n, where on the ith step, you can either move backwards or forwards i steps. That is on step 1, you can either end at -1,1 and step 2, either at -3,1,-1,3, and so on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "b4e2e11e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "minsteps (generic function with 1 method)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function minsteps(source, step, dest)\n",
    "   \n",
    "    #Base case to make it stop - think about it yourself as to why we need this\n",
    "    if abs(source) > dest\n",
    "        return Inf\n",
    "    end\n",
    "    \n",
    "    #Base case if done\n",
    "    if source == dest\n",
    "        return 0\n",
    "    end\n",
    "    \n",
    "    #Recursive case\n",
    "    return 1 + min( minsteps(source-step, step+1, dest), minsteps(source+step, step+1, dest) )\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "bbaf69e9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minsteps( 0,1,3 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "4173b1fc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minsteps( 0,1,11 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "76523eb9",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.6.5",
   "language": "julia",
   "name": "julia-1.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}