week07_recursion_with_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recursion\n",
    "\n",
    "In its simplest form, a recursive function is a function that calls itself.\n",
    "\n",
    "Consider the problem of printing a string a specified number of times on the same line. Most students would\n",
    "use a loop and write a function that looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_n(s, n):\n",
    "    for i in range(0, n):\n",
    "        print(s, end = '')\n",
    "        \n",
    "\n",
    "# test our function\n",
    "print_n('*', 5)\n",
    "print_n('_', 2)\n",
    "print_n('*', 5)\n",
    "print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `print_n` uses a loop that runs *n* times. Each time the loop runs, the loop body prints the string\n",
    "`s` once.\n",
    "\n",
    "A different way of approaching the problem is to use the following algorithm:\n",
    "\n",
    "```python\n",
    "if n < 1:\n",
    "    # do nothing\n",
    "else:\n",
    "    print s once\n",
    "    print s (n - 1) more times\n",
    "```\n",
    "\n",
    "If we wrap the algorithm up in a function, it looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_n(s, n):\n",
    "    if n < 1:               # base case\n",
    "        return\n",
    "    else:                   # recursive case\n",
    "        print(s, end = '')\n",
    "        print_n(s, n - 1)   # function calls itself!\n",
    "\n",
    "\n",
    "# test our function\n",
    "print_n('*', 5)\n",
    "print_n('_', 2)\n",
    "print_n('*', 5)\n",
    "print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This *recursive* version of `print_n` uses itself to solve the problem of printing a string $(n-1)$ times.\n",
    "\n",
    "The key point to keep in mind when formulating a recursive function is that the function will call itself to\n",
    "solve a *smaller version* of the original problem. Eventually, the recursive calls will reach a version\n",
    "of the problem where the solution to the problem is known; when this happens we say that the function reaches\n",
    "a *base case*.\n",
    "\n",
    "**The size of a problem**\n",
    "\n",
    "To use recursion, we need a definition for the size of a problem. Technically, the size of a problem is equal\n",
    "to the number of bits needed to specify the inputs to the problem, but this is a difficult definition for\n",
    "new programmers to use. Intuitively, when we consider a problem such as `print_n`, we can see that the size \n",
    "of the problem is related to the value of `n`: Printing a string 1000 times is a bigger problem than printing \n",
    "the same string 10 times.\n",
    "\n",
    "**Base cases**\n",
    "\n",
    "In a base case, the problem solution can be computed immediately given the inputs to the function. For the\n",
    "`print_n` problem, there are potentially an infinite number of base cases. For example we could write `print_n`\n",
    "as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_n(s, n):\n",
    "    if n < 1:               # base case\n",
    "        return\n",
    "    elif n == 1:\n",
    "        print(s, end = '')\n",
    "    elif n == 2:\n",
    "        print(s, end = '')\n",
    "        print(s, end = '')\n",
    "    elif n == 3:\n",
    "        print(s, end = '')\n",
    "        print(s, end = '')\n",
    "        print(s, end = '')\n",
    "    # and so on ....\n",
    "    else:                   # recursive case\n",
    "        print(s, end = '')\n",
    "        print_n(s, n - 1)   # function calls itself!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Generally, we try to use the smallest number of base cases as possible that allow the function to solve\n",
    "all possible sizes of the problem. This means that there will always be one base case that produces the solution\n",
    "for the smallest possible problem size. For the `print_n` problem, the base case that solves the problem of\n",
    "printing the string zero (or fewer) times.\n",
    "\n",
    "**Recursive cases**\n",
    "\n",
    "The textbook calls the recursive case the *reduction step* where the word *reduction* implies that this step\n",
    "solves a smaller version of the current problem.\n",
    "\n",
    "In a recursive case, the problem solution is obtained with the help of one or more recursive calls to the same\n",
    "function, but the inputs must be reduced in size so that the recursive call moves closer to a base case. For the\n",
    "`print_n` problem, the recursive call is:\n",
    "\n",
    "```python\n",
    "print_n(s, n - 1)\n",
    "```\n",
    "\n",
    "The problem size for the recursive call is $(n - 1)$ which is less than the original problem size of $n$.\n",
    "We can trace what happens when `print_n` is used to print a string three times:\n",
    "\n",
    "```\n",
    "print_n('*', 3)\n",
    "*print_n('*', 2)\n",
    "**print_n('*', 1)\n",
    "***print_n('*', 0)\n",
    "***\n",
    "```\n",
    "\n",
    "1. for $n=3$ we are not in a base case so we proceed to the recursive case\n",
    "2. a `*` is printed, and `print_n('*', 2)` is called\n",
    "3. for $n=2$ we are not in a base case so we proceed to the recursive case\n",
    "    * a `*` is printed, and `print_n('*', 1)` is called\n",
    "4. for $n=1$ we are not in a base case so we proceed to the recursive case\n",
    "    * a `*` is printed, and `print_n('*', 0)` is called\n",
    "5. for $n=0$ we are in a base case\n",
    "    * the funtion returns without printing any additional output\n",
    "\n",
    "**The leap of faith**\n",
    "\n",
    "In the recursive case, we use the function that we are currently writing to obtain part of the solution. For\n",
    "most programmers studying recursion for the first time, this is an uncomfortable aspect of writing a recursive\n",
    "function. It is an important aspect of learning to write recursive functions that you always keep in mind the\n",
    "contract of the function when you formulate the recursive case: Assume that the function satisfies its\n",
    "contract (even though it is not complete), and then recursively call the function to solve the smaller\n",
    "version of the problem.\n",
    "\n",
    "**Summary**\n",
    "\n",
    "Whenever you are trying to forumlate a recursive solution to a problem keep the following points in mind:\n",
    "\n",
    "* define the size of the problem\n",
    "* identify the base case or cases\n",
    "* for the recursive case or cases, use the function itself to solve a smaller version of the problem\n",
    "    * assume that the function satisfies its contract so that the recursive case correctly solves the\n",
    "    smaller version of the problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More simple examples\n",
    "\n",
    "Most programmers find it easier to write loops instead of using recursion. This is especially true for\n",
    "the simple examples that are often used to introduce recursion. However, it is important that you understand\n",
    "the simple examples to learn the mechanics of recursion so that you can apply recursion to problems that\n",
    "are difficult to solve using loops but have simple and elegant recursive solutions. We study such problems\n",
    "later in the course.\n",
    "\n",
    "\n",
    "### Integer multiplication\n",
    "\n",
    "For two integers $m$ and $n$ where $n \\geq 0$, the product of $m$ and $n = m \\times n$ is defined as the \n",
    "sum of $n$ copies of $m$:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "m \\times n & =  \\underbrace{m + m + ... + m}_\\text{$n$ times}\\\\\n",
    "& = m + \\underbrace{m + ... + m}_\\text{$n-1$ times}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Of course, you would simply use the `*` operator for integer multiplication, but as an exercise consider\n",
    "writing a recursive function that returns the product of two integer values.\n",
    "\n",
    "The size of this problem is equal to the value of $n$.\n",
    "\n",
    "The base case occurs when $n = 0$ and returns a value of $0$.\n",
    "\n",
    "The recursive case returns the value of $m + m \\times (n - 1)$. Notice that $m \\times (n-1)$ is a smaller \n",
    "version of the integer multiplication problem compared to $m \\times n$.\n",
    "\n",
    "A recursive function for integer multiplication is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def multiply(m, n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return m + multiply(m, n - 1)\n",
    "    \n",
    "for n in range(0, 11):\n",
    "    prod = multiply(5, n)\n",
    "    print('5 *', n, '=', prod)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1** Modify `multiply` so that it returns the correct product even when `n` is a negative integer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 1\n",
    "def multiply(m, n):\n",
    "    if n < 0:\n",
    "        return multiply(-m, -n)\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return m + multiply(m, n - 1)\n",
    "    \n",
    "for n in range(0, -11, -1):\n",
    "    prod = multiply(5, n)\n",
    "    print('5 *', n, '=', prod)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Integer exponentiation\n",
    "\n",
    "For a real value $x$ and an integer $n \\geq 0$ the value of $x$ raised to the power $n = x^n$ is defined as\n",
    "the product of $n$ copies of $x$:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "x ^ n & =  \\underbrace{x \\times x\\ \\times ... \\times\\ x}_\\text{$n$ times}\\\\\n",
    "& = x \\times \\underbrace{x \\times\\ ...\\ \\times x}_\\text{$n-1$ times}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Of course, you would simply use the `**` operator for exponentiation, but as an exercise consider\n",
    "writing a recursive function that returns the value of a float raised to an integer exponent.\n",
    "\n",
    "The size of this problem is equal to the value of $n$.\n",
    "\n",
    "The base case occurs when $n = 0$ and returns a value of $1$.\n",
    "\n",
    "The recursive case returns the value of $x \\times x^{(n - 1)}$. Notice that $x^{(n - 1)}$ is a smaller version\n",
    "of the exponentiation problem compared to $x^n$.\n",
    "\n",
    "A recursive function for integer exponentiation is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pow(x, n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return x * pow(x, n - 1)\n",
    "    \n",
    "for n in range(0, 11):\n",
    "    y = pow(2, n)\n",
    "    print('2 **', n, '=', y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2** Modify `pow` so that it returns the correct value even when `n` is a negative integer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 2\n",
    "def pow(x, n):\n",
    "    if n < 0:\n",
    "        return 1 / pow(x, -n)\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return x * pow(x, n - 1)\n",
    "    \n",
    "for n in range(0, -11, -1):\n",
    "    y = pow(2, n)\n",
    "    print('2 **', n, '=', y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Palindromes\n",
    "\n",
    "A string is a palindrome if it is equal to itself when reversed (spelled the same forwards and backwards). The\n",
    "empty string is considered to be a palindrome. For example, the following strings are all palindromes:\n",
    "\n",
    "* `a`\n",
    "* `oo`\n",
    "* `did`\n",
    "* `noon`\n",
    "* `yobananaboy`\n",
    "\n",
    "Consider the problem of writing a function that returns `True` if a string is a palindrome, and `False` otherwise.\n",
    "To test if a string is a palindrome, we need to:\n",
    "\n",
    "* compare the first and last characters of the string\n",
    "    * if they are not equal then the string is not a palidrome\n",
    "* compare the second and second last characters of the string\n",
    "    * if they are not equal then the string is not a palidrome\n",
    "* compare the third and third last characters of the string\n",
    "    * if they are not equal then the string is not a palidrome\n",
    "* and so on\n",
    "* compare the middle two characters of the string\n",
    "    * if they are not equal then the string is not a palidrome\n",
    "* if we reach this point then the string is a palidrome\n",
    "\n",
    "The size of this problem is proportional to the length of the input string because for strings that are\n",
    "palidromes we need to access every character of the string.\n",
    "\n",
    "One base case occurs for the empty string, which is a palindrome. Alternatively, we can use the base case\n",
    "where the length of the string is less than 2, in which case the string is a palindrome. In either case,\n",
    "the base case returns `True`.\n",
    "\n",
    "For a recursive method that returns a boolean value, there must be at least two base cases (one that returns\n",
    "`True` and a second that returns `False`). For the palindrome problem, the base case that returns `False`\n",
    "occurs when the first and last character of the string are not equal.\n",
    "\n",
    "If we reach the recursive case, then we know that the first and last characters of the string are equal.\n",
    "In other words, we are in the situation where we have a string of the form:\n",
    "\n",
    "```\n",
    "?<middle>?\n",
    "```\n",
    "\n",
    "where `?` represents the character at the front and end of the string and  `<middle>` represents the\n",
    "characters in the middle of the string. This string is a palindrome if the part of the string\n",
    "represented by `<middle>` is a palindrome. Notice that `<middle>` is a shorter string than the input\n",
    "string; therefore, we can use recursion to determine if `<middle>` is a palindrome.\n",
    "\n",
    "A recursive function for the palindrome problem is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_palindrome(s):\n",
    "    if len(s) < 2:\n",
    "        return True\n",
    "    elif s[0] != s[-1]:\n",
    "        return False\n",
    "    else:\n",
    "        return is_palindrome(s[1:-1])\n",
    "    \n",
    "# test our function\n",
    "s = ''\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n",
    "s = 'a'\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n",
    "s = 'ab'\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n",
    "s = 'did'\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n",
    "s = 'doh'\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n",
    "s = 'yobananaboy'\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3** Modify `is_palindrome` so that it prints out the part of the string represented by `<middle>`.\n",
    "Run the modified version of the function and verify that the function solves a smaller version of the\n",
    "problem each time the recursive case runs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 3\n",
    "def is_palindrome(s):\n",
    "    if len(s) < 2:\n",
    "        return True\n",
    "    elif s[0] != s[-1]:\n",
    "        return False\n",
    "    else:\n",
    "        middle = s[1:-1]\n",
    "        print('\\tmiddle :', middle)\n",
    "        return is_palindrome(middle)\n",
    "    \n",
    "# test our function\n",
    "s = 'yobananaboy'\n",
    "print(s, 'is palindrome?', is_palindrome(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 4** Suppose that you switch the order of the `if` and `elif` conditions in the function `is_palindrome`.\n",
    "Does the function still behave correctly?\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    No, switching the order will cause an IndexError to be raised when the string has even length and\n",
    "    is a palindrome because the recursive call will eventually end up using an empty string (and indexing\n",
    "    into an empty string will raise an exception).\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Palindromes: Part 2\n",
    "\n",
    "One disadvantage to the previous solution is that the recursive call uses a slice of the input string. The\n",
    "problem with using a slice is that Python creates a new string to represent the slice; if the input string\n",
    "is very long then many slices might be created to determine if the string is a palindrome.\n",
    "\n",
    "Instead of using a slice, we can use two indexes to indicate the two characters that we need to compare\n",
    "in the recursive call. If we do so then the the `is_palindrome` method becomes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_palindrome(s, index1, index2):\n",
    "    if index1 > index2:\n",
    "        return True\n",
    "    elif s[index1] != s[index2]:\n",
    "        return False\n",
    "    else:\n",
    "        return is_palindrome(s, index1 + 1, index2 - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and the caller uses the function like so:\n",
    "\n",
    "```python\n",
    "s = 'abba'\n",
    "boo = is_palindrome(s, 0, len(s) - 1)\n",
    "```\n",
    "\n",
    "In this version of the function, `index1` is the index of a character in the front half of the string and \n",
    "`index2` is the index of a character in the back half of the string. In the recursive call, we add `1` to\n",
    "`index1` to move the front index one position towards the end of the string and we subtract `1` from `index2` to\n",
    "move the back index one position towards the front of the string. If `index1 > index2` is `True` then we have\n",
    "compared all of the characters in the front half of the string with the corresponding characters in the back\n",
    "half of the string.\n",
    "\n",
    "The size of the problem in this example is equal to $\\text{index}_2 - \\text{index}_1 + 1$ (the number of\n",
    "characters in the substring starting at $\\text{index}_1$ and going to $\\text{index}_2$, inclusive). The\n",
    "size of the problem in the recursive call is\n",
    "\n",
    "$$(\\text{index}_2 - 1) - (\\text{index}_1 + 1) + 1 = \\text{index}_2 - \\text{index}_1 - 1$$\n",
    "\n",
    "which is smaller than the size of the original problem.\n",
    "\n",
    "The disadvantage of this approach is that the caller of the function needs to specify the values of\n",
    "`index1` and `index2` which is inconvenient for the caller because all that the caller wants to know is\n",
    "whether or not `s` is a palindrome. The solution to this problem is shown below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_palindrome(s):\n",
    "    return is_palindrome_helper(s, 0, len(s) - 1)\n",
    "\n",
    "def is_palindrome_helper(s, index1, index2):\n",
    "    if index1 > index2:\n",
    "        return True\n",
    "    elif s[index1] != s[index2]:\n",
    "        return False\n",
    "    else:\n",
    "        return is_palindrome_helper(s, index1 + 1, index2 - 1)\n",
    "    \n",
    "    \n",
    "# test our function\n",
    "s = ''\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n",
    "s = 'a'\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n",
    "s = 'ab'\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n",
    "s = 'did'\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n",
    "s = 'doh'\n",
    "print(s, 'is palindrome?', is_palindrome(s))\n",
    "s = 'yobananaboy'\n",
    "print(s, 'is palindrome?', is_palindrome(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The caller uses the `is_palindrome` function simply by passing in the string to test. The `is_palindrome`\n",
    "function calls a second *helper* function which implements the recursive algorithm. Using a helper function\n",
    "is a commonly used strategy when the recursive function requires extra inputs that the caller does not\n",
    "provide. Here, `index1` and `index2` are implementation details of the recursive helper function that the\n",
    "caller should not be responsible for; therefore, we created the `is_palindrome` function for the caller to use\n",
    "and the function becomes responsible for setting the starting values of the two indexes.\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    Python does not have a mechanism for hiding functions in modules; therefore, a caller can still \n",
    "    directly call the <tt>is_palindrome_helper</tt> function if they wanted to. In some other languages,\n",
    "    it would be possible to make helper functions invisible to other callers.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Searching a string for a substring\n",
    "\n",
    "A common problem when working with strings is searching a string `s` to determine if another string appears in\n",
    "`s`; the other string is often called a substring of `s`. One example of this problem is searching a webpage\n",
    "for a particular phrase.\n",
    "\n",
    "Consider the problem of writing a recursive function `contains(s, sub)` that returns `True` if `sub` is a substring\n",
    "of `s`, and `False` otherwise.\n",
    "\n",
    "We know that there must be separate base cases for the `True` and `False` results.\n",
    "\n",
    "When does the `True` base case occur? It occurs when `s` starts with `sub`.\n",
    "\n",
    "When does the `False` base case occur? It occurs when `sub` is longer than `s` because a string that longer\n",
    "than `s` cannot possibly be a substring of `s`.\n",
    "\n",
    "If we reach the recursive case then we know two things:\n",
    "\n",
    "* `s` does not start with `sub`\n",
    "* `len(s) >= len(sub)` is `True`\n",
    "\n",
    "How can we use recursion to solve a smaller version of the substring problem? We know that `sub` is not found\n",
    "starting at the front of `s`, but it might be found starting at the second character of `s`. In other words,\n",
    "we search the string equal to `s` with the first character removed. This is a smaller version of the problem\n",
    "than we originall started with.\n",
    "\n",
    "A recursive version of `contains` is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def contains(s, sub):\n",
    "    if s.startswith(sub):     # or if s[0:len(sub)] == sub\n",
    "        return True\n",
    "    elif len(s) < len(sub):\n",
    "        return False\n",
    "    else:\n",
    "        return contains(s[1:], sub)\n",
    "    \n",
    "# test our method\n",
    "s = 'rubadubdub'\n",
    "sub = 'rub'\n",
    "print(contains(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = 'zub'\n",
    "print(contains(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = 'dubdub'\n",
    "print(contains(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = s\n",
    "print(contains(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = s + 'a'\n",
    "print(contains(s, sub))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 5**  What is the size of the `contains` problem?\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    len(s) + len(sub) but because the length of sub never changes in the recursive call we can ignore\n",
    "    its contribution to the size and define the size to be len(s)\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 6**  `contains` uses a slice in the recursive call. Rewrite the `contains` function so that it\n",
    "calls a helper function that uses an index instead of a slice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 6\n",
    "def contains(s, sub):\n",
    "    return contains_impl(s, sub, 0)\n",
    "\n",
    "def contains_impl(s, sub, start_index):\n",
    "    if s.startswith(sub, start_index):\n",
    "        return True\n",
    "    elif start_index + len(sub) > len(s):\n",
    "        return False\n",
    "    else:\n",
    "        return contains_impl(s, sub, start_index + 1)\n",
    "    \n",
    "    \n",
    "# test our method\n",
    "s = 'rubadubdub'\n",
    "sub = 'rub'\n",
    "print(contains(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = 'zub'\n",
    "print(contains(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = 'dubdub'\n",
    "print(contains(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = s\n",
    "print(contains(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = s + 'a'\n",
    "print(contains(s, sub))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Searching for a substring: Part 2\n",
    "\n",
    "A common modification of the previous problem is to find the location of a substring in a string. Because a\n",
    "substring might appear more than once in a given string, such methods either return the location of the\n",
    "first or last occurrence of the substring. Usually, the index where the substring starts in the string is\n",
    "returned, and a negative value such as `-1` is returned if the substring does not appear in the string.\n",
    "\n",
    "Consider writing a recursive function `index_of(s, sub)` that returns the index of the first occurrence\n",
    "of the substring `sub` in `s`. For example, `index_of('rubadubdub', 'u')` would return `1` because the `u`\n",
    "first occurs at index `1` in `s`. `index_of('rubadubdub', 'dub')` would return `4` because `dub` first\n",
    "occurs starting at index `4` in `s`.\n",
    "\n",
    "`index_of` is similar to `contains` except that the return value is an index instead of a boolean value.\n",
    "Where `contains` returns `False`, `index_of` can return `-1` because `sub` is not in the string `s`.\n",
    "Where `contains` returns `True`, `index_of` can return `0` because `sub` starts at the front of the string `s`.\n",
    "With these changes in mind, `index_of` looks like:\n",
    "\n",
    "```python\n",
    "def index_of(s, sub):\n",
    "    if s.startswith(sub):     # or if s[0:len(sub)] == sub\n",
    "        return 0\n",
    "    elif len(s) < len(sub):\n",
    "        return -1\n",
    "    else:\n",
    "        # recursive case\n",
    "        # something involving  index_of(s[1:], sub)\n",
    "```\n",
    "\n",
    "What should the recursive case return? To answer this question, we need to consider what `index_of(s[1:], sub)`\n",
    "returns: It returns the index of the starting location of `sub` in the string `s[1:]` where `s[1:]` is simply\n",
    "`s` with the first character removed.\n",
    "\n",
    "If `index_of(s[1:], sub)` returns `-1` then we know that `sub` is not in the string `s[1:]`. We also know\n",
    "that `sub` is not found at the beginning of `s` (otherwise the first base case would have returned `0`).\n",
    "Therefore, we can conclude that `sub` is not found in `s` and we should return `-1`.\n",
    "\n",
    "If `index_of(s[1:], sub)` returns a non-negative value, then that value is the index of the starting location\n",
    "of `sub` in `s[1:]`. To convert the index to be an index in `s` we simply add `1` to it because `s[1:]`\n",
    "starts at index `1` of `s`.\n",
    "\n",
    "Finally, we have a complete implementation of `index_of`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def index_of(s, sub):\n",
    "    if s.startswith(sub):     # or if s[0:len(sub)] == sub\n",
    "        return 0\n",
    "    elif len(s) < len(sub):\n",
    "        return -1\n",
    "    else:\n",
    "        index = index_of(s[1:], sub)\n",
    "        if index == -1:\n",
    "            return -1\n",
    "        else:\n",
    "            return 1 + index\n",
    "      \n",
    "     \n",
    "\n",
    "# test our method\n",
    "s = 'rubadubdub'\n",
    "sub = 'rub'\n",
    "print(index_of(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = 'zub'\n",
    "print(index_of(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = 'dubdub'\n",
    "print(index_of(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = s\n",
    "print(index_of(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = s + 'a'\n",
    "print(index_of(s, sub))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 7** Write a function `last_index_of(s, sub)` that returns the index of the last occurrence of\n",
    "the substring `sub` in `s`. Your function should return `-1` if `sub` is not found in `s`. *Hint: Instead of\n",
    "starting from the front of the string like in **index_of** start at the back of the string.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def last_index_of(s, sub):\n",
    "    return last_index_of_impl(s, sub, len(s) - 1)\n",
    "\n",
    "def last_index_of_impl(s, sub, start_index):\n",
    "    if start_index == -1:\n",
    "        return -1\n",
    "    elif s.startswith(sub, start_index):\n",
    "        return start_index\n",
    "    else:\n",
    "        return last_index_of_impl(s, sub, start_index - 1)\n",
    "\n",
    "# test our method\n",
    "s = 'rubadubdub'\n",
    "sub = 'rub'\n",
    "print(last_index_of(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = 'zub'\n",
    "print(last_index_of(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = 'dubdub'\n",
    "print(last_index_of(s, sub))\n",
    "\n",
    "s = 'rubadubdub'\n",
    "sub = 'u'\n",
    "print(last_index_of(s, sub))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding the smallest element in a list\n",
    "\n",
    "A common problem that occurs when working with lists of numbers is finding the minimum or maximum value in \n",
    "a non-empty list.\n",
    "\n",
    "Consider writing the recursive function `min_value(t)` that returns the minimum value in a non-empty list\n",
    "of numbers `t`. We want to do so without using the Python built-in function `min`.\n",
    "\n",
    "If the list `t` has exactly one value then that value is also the minimum value in the list.\n",
    "\n",
    "If the list `t` has more than one value then what can we say about the minimum value in the list? The minimum\n",
    "value is either the first element in the list, or it is the minimum value in the list *not including the first\n",
    "element*. Finding the minimum value in the list not including the first element is a smaller version of\n",
    "minimum value problem that we can solve using recursion.\n",
    "\n",
    "Putting the two ideas above together, we have an incomplete version of `min_value`:\n",
    "\n",
    "```python\n",
    "def min_value(t):\n",
    "    if len(t) == 1:\n",
    "        return t[0]\n",
    "    else:\n",
    "        first = t[0]\n",
    "        min_in_rest = min_value(t[1:])\n",
    "```\n",
    "\n",
    "In the recursive case, the minimum value in the list is the smaller of the two values `first` and `min_in_rest`.\n",
    "We can easily find the smaller value with an `if` statement, which completes the function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def min_value(t):\n",
    "    if len(t) == 1:\n",
    "        return t[0]\n",
    "    else:\n",
    "        first = t[0]\n",
    "        min_in_rest = min_value(t[1:])\n",
    "        if first <= min_in_rest:\n",
    "            return first\n",
    "        else:\n",
    "            return min_in_rest\n",
    "\n",
    "# test our function\n",
    "t = [1]\n",
    "print(t, 'min:', min_value(t))\n",
    "t = [2, 1]\n",
    "print(t, 'min:', min_value(t))\n",
    "t = [3, 1, 2]\n",
    "print(t, 'min:', min_value(t))\n",
    "t = [3, 1, 2, 5, 4, 0, 6]\n",
    "print(t, 'min:', min_value(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 8** Write a recursive function that returns the maximum value in a non-empty list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 8\n",
    "def max_value(t):\n",
    "    if len(t) == 1:\n",
    "        return t[0]\n",
    "    else:\n",
    "        first = t[0]\n",
    "        max_in_rest = max_value(t[1:])\n",
    "        if first > max_in_rest:\n",
    "            return first\n",
    "        else:\n",
    "            return max_in_rest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 9** Re-write `min_value` so that it uses a recursive helper function and an index instead of using a slice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 9\n",
    "def min_value(t):\n",
    "    return min_value_impl(t, 0)\n",
    "\n",
    "def min_value_impl(t, start_index):\n",
    "    '''\n",
    "    Finds the minimum element of t starting at start_index\n",
    "    '''\n",
    "    if start_index == len(t) - 1:\n",
    "        return t[start_index]\n",
    "    else:\n",
    "        first = t[start_index]\n",
    "        min_in_rest = min_value_impl(t, start_index + 1)\n",
    "        if first <= min_in_rest:\n",
    "            return first\n",
    "        else:\n",
    "            return min_in_rest\n",
    "        \n",
    "# test our function\n",
    "t = [1]\n",
    "print(t, 'min:', min_value(t))\n",
    "t = [2, 1]\n",
    "print(t, 'min:', min_value(t))\n",
    "t = [3, 1, 2]\n",
    "print(t, 'min:', min_value(t))\n",
    "t = [3, 1, 2, 5, 4, 0, 6]\n",
    "print(t, 'min:', min_value(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 10** Write a recursive function `count(t, elem)` that counts the number of times `elem` appears in a\n",
    "list `t`. For example, `count(['a', 'b', 'a', 'a', 'c'], 'a')` should return 3 because `a` appears as an element\n",
    "of the list 3 times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 10\n",
    "def count(t, elem):\n",
    "    if len(t) == 0:\n",
    "        return 0\n",
    "    elif t[0] == elem:\n",
    "        return 1 + count(t[1:], elem)\n",
    "    else:\n",
    "        return count(t[1:], elem)\n",
    "    \n",
    "t = ['a', 'a', 'c', 'd', 'd']\n",
    "print(count(t, 'a'))\n",
    "print(count(t, 'b'))\n",
    "print(count(t, 'c'))\n",
    "print(count(t, 'd'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 11** Write a recursive function `reverse(s)` that returns a string equal to the reversed version of the\n",
    "string `s`. For example, `reverse('xyz')` should return the string `zyx`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 11\n",
    "def reverse(s):\n",
    "    if len(s) < 2:\n",
    "        return s\n",
    "    else:\n",
    "        first = s[0]\n",
    "        return reverse(s[1:]) + first\n",
    "    \n",
    "print(reverse('a'))\n",
    "print(reverse('ab'))\n",
    "print(reverse('abc'))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}