{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recursion Homework Problems - Solutions\n",
    "\n",
    "This assignment is a variety of small problems to begin you getting used to the idea of recursion. They are not full-blown interview questions, but do serve as a great start for getting your mind \"in the zone\" for recursion problems.\n",
    "\n",
    "Here are the solutions with some simple explanations to the problems.\n",
    "\n",
    "______\n",
    "### Problem 1\n",
    "\n",
    "**Write a recursive function which takes an integer and computes the cumulative sum of 0 to that integer**\n",
    "\n",
    "**For example, if n=4 , return 4+3+2+1+0, which is 10.**\n",
    "\n",
    "This problem is very similar to the factorial problem presented during the introduction to recursion. Remember, always think of what the base case will look like. In this case, we have a base case of n =0 (Note, you could have also designed the cut off to be 1).\n",
    "\n",
    "In this case, we have:\n",
    "   n + (n-1) + (n-2) + .... + 0\n",
    "\n",
    "Check out a sample solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def rec_sum(n):\n",
    "    \n",
    "    # Base Case\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    \n",
    "    # Recursion\n",
    "    else:\n",
    "        return n + rec_sum(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rec_sum(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "______\n",
    "### Problem 2\n",
    "\n",
    "**Given an integer, create a function which returns the sum of all the individual digits in that integer. For example:\n",
    "if n = 4321, return 4+3+2+1**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum_func(n):\n",
    "    # Base case\n",
    "    if len(str(n)) == 1:\n",
    "        return n\n",
    "    \n",
    "    # Recursion\n",
    "    else:\n",
    "        return n%10 + sum_func(n/10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_func(4321)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Hints:*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# You'll neeed to use modulo\n",
    "4321%10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "432"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "4321 / 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "We'll need to think of this function recursively by knowing that:\n",
    "4502 % 10 + sum_func(4502/10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "________\n",
    "### Problem 3\n",
    "*Note, this is a more advanced problem than the previous two! It aso has a lot of variation possibilities and we're ignoring strict requirements here.*\n",
    "\n",
    "Create a function called word_split() which takes in a string **phrase** and a set **list_of_words**. The function will then determine if it is possible to split the string in a way in which words can be made from the list of words. You can assume the phrase will only contain words found in the dictionary if it is completely splittable.\n",
    "\n",
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['the', 'man', 'ran']"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_split('themanran',['the','ran','man'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['i', 'love', 'dogs', 'John']"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_split('ilovedogsJohn',['i','am','a','dogs','lover','love','John'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_split('themanran',['clown','ran','man'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def word_split(phrase,list_of_words, output = None):\n",
    "    '''\n",
    "    Note: This is a very \"python-y\" solution.\n",
    "    ''' \n",
    "    \n",
    "    # Checks to see if any output has been initiated.\n",
    "    # If you default output=[], it would be overwritten for every recursion!\n",
    "    if output is None:\n",
    "        output = []\n",
    "    \n",
    "    # For every word in list\n",
    "    for word in list_of_words:\n",
    "        \n",
    "        # If the current phrase begins with the word, we have a split point!\n",
    "        if phrase.startswith(word):\n",
    "            \n",
    "            # Add the word to the output\n",
    "            output.append(word)\n",
    "            \n",
    "            # Recursively call the split function on the remaining portion of the phrase--- phrase[len(word):]\n",
    "            # Remember to pass along the output and list of words\n",
    "            return word_split(phrase[len(word):],list_of_words,output)\n",
    "    \n",
    "    # Finally return output if no phrase.startswith(word) returns True\n",
    "    return output        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "Alright, so now that we've seen a few examples, let's dive in to the interview practice problems!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}