+ " if word:\n",
+ " first = word[0]\n",
+ " rest = word[1:]\n",
+ " duplicates_in_rest = duplicates_via_recursion(rest)\n",
+ " if first in rest and first not in duplicates_in_rest:\n",
+ " duplicates_in_rest += [first]\n",
+ " return duplicates_in_rest\n",
+ " else:\n",
+ " return []"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [],
+ "prompt_number": 18
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "duplicates_via_recursion('occurrences')"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "metadata": {},
+ "output_type": "pyout",
+ "prompt_number": 19,
+ "text": [
+ "['e', 'r', 'c']"
+ ]
+ }
+ ],
+ "prompt_number": 19
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "##Solution 6\n",
+ "A recursive approach, using an accumulator.\n",
+ "\n",
+ "The previous solution built up the set of duplicates as the recursive calls unwound. This approach uses an accumulator to capture the duplicates as the recursive calls are made. This is the trick for prompting semi-smart compilers to use tail-call optimisation. The algorithm is a simple reordering of the subtasks above.\n",
+ "\n",
+ "Split the word into the first letter and the rest. \n",
+ "\n",
+ "If the first letter appears in the rest of the word, it's a duplicate, so add it to list of duplicates. (But don't add it if we've already decided it's a duplicate.)\n",
+ "\n",
+ "Find all the duplicates in the rest, keeping track of the duplicates found so far.\n",
+ "\n",
+ "When we run out of word, the duplicates found so far are all the duplicates, so return them."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "def duplicates_via_recursion_with_accumulator(word):\n",