{ "metadata": { "name": "", "signature": "sha256:d87d279905d6a026802063c641735e88d4a55675735d14177b91a84ed2eb9b18" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Motivating and Visualizing Recursion in Python" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Recursive factorial function considered harmful" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Gustavo Duarte ([@food4hackers](https://twitter.com/food4hackers)) wrote about [Recursion: Dream within a Dream](http://duartes.org/gustavo/blog/post/recursion/), arguing for the use of well-motivated examples to teach recursion, **\"the single most powerful idea in algorithms\"**. \n", "\n", "He crafts a compelling critique of a common example used to demonstrate recursion (an example that I, myself, have often used in the past): the [factorial](https://en.wikipedia.org/wiki/Factorial) function,\n", "\n", "$$n! = \\prod_{k=1}^{n} k$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A recursive version of the factorial function can be defined in Python as follows:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def factorial(n):\n", " if n == 0:\n", " return 1\n", " return n * factorial(n - 1)" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Gustavo notes:\n", "\n", "> Our factorial algorithm boils down to pushing integers N, N-1, \u2026 1 onto a stack, then multiplying them in reverse order. The fact we\u2019re using the program\u2019s call stack to do this is an implementation detail: we could allocate a stack on the heap and use that instead. \n", "\n", ">...\n", "\n", "> Once you see the call stack as a data structure, something else becomes clear: piling up all those integers to multiply them afterwards is one dumb-ass idea. That is the real lameness of this implementation: it\u2019s using a screwdriver to hammer a nail. It\u2019s far more sensible to use an iterative process to calculate factorials." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An iterative version of the function can be defined in Python as follows" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def i_factorial(n):\n", " product = 1\n", " for k in range(1, n + 1):\n", " product *= k\n", " return product" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 6 }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can verify the functional equivalence of these two versions:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "for k in range(10):\n", " print '{}! = {:6d}, {:6d}'.format(k, factorial(k), i_factorial(k))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "0! = 1, 1\n", "1! = 1, 1\n", "2! = 2, 2\n", "3! = 6, 6\n", "4! = 24, 24\n", "5! = 120, 120\n", "6! = 720, 720\n", "7! = 5040, 5040\n", "8! = 40320, 40320\n", "9! = 362880, 362880\n" ] } ], "prompt_number": 7 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Recursion: an a-maze-ing way to traverse a tree" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Gustavo proposes demonstrating the use - and value - of recursion by selecting a more appropriate problem, where a non-recursive (iterative) approach would be far more cumbersome: exploring a maze, where the maze is represented as a binary tree.\n", "\n", "> when it comes to algorithms, recursion is the rule, not the exception. It comes up when we search, when we traverse trees and other data structures, when we parse, when we sort: it\u2019s everywhere. You know how pi or e come up in math all the time because they\u2019re in the foundations of the universe? Recursion is like that: it\u2019s in the fabric of computation." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "maze" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "He defines a C struct, [``mazeNode``](https://github.com/gduarte/lkb/blob/master/code/stack/maze.h), with 4 members to represent a node in the binary tree representation of this maze:\n", "\n", "
typedef struct mazeNode {\n",
      "        int hasCheese;\n",
      "        int tag;\n",
      "        struct mazeNode *left;\n",
      "        struct mazeNode *right;\n",
      "} maze_t;\n",
      "
\n", "\n", "He also defines a recursive C function, [`explore()`](https://github.com/gduarte/lkb/blob/master/code/stack/maze.c) to recursively traverse the maze (binary tree), stopping when it finds a node where `hasCheese == 1`, and visualizes the call stack of the execution of the function when it finds the cheese." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "mazeCallStack.png" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Recursively traversing a binary tree in Python" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "maze\n", "I could define a Python [`class`](https://docs.python.org/2/tutorial/classes.html) to represent a `mazeNode`, but will choose a simpler approach using 4-element [*tuples*](https://docs.python.org/2/tutorial/datastructures.html#tuples-and-sequences) (4-tuples) to represent each node in a tree: *(tag, has_cheese, left, right)*. \n", "\n", "* *tag* will again be an int (in the range 0 to 11)\n", "* *has_cheese* will either be the Python null object, `None`, or the string `'cheese'` (no pun intended)\n", "* *left* will be a 4-tuple or empty tuple representing the left branch\n", "* *right* will be a 4-tuple or empty tuple representing the right branch" ] }, { "cell_type": "code", "collapsed": false, "input": [ "maze = (0, None,\n", " (1, None,\n", " (2, None,\n", " (3, None, (), ()),\n", " (4, None, (), ())),\n", " (5, None,\n", " (6, None, (), ()),\n", " ())),\n", " (7, None,\n", " (8, None, (), ()),\n", " (9, None,\n", " (10, None,\n", " (11, 'cheese', (), ()),\n", " ()),\n", " ())))" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 10 }, { "cell_type": "markdown", "metadata": {}, "source": [ "I typically insert `print` statements into a recursive function to illustrate the execution call stack. Here's how I might define the `explore()` function in Python, using an optional `depth` parameter to visualize call strack trace information:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def explore(node, depth=0):\n", " if not node: # empty tuple\n", " print ' <' * depth, 'Nothing found'\n", " return False\n", " print ' >' * depth, 'Checking node', node[0]\n", " if node[1]: # check for non-empty/non-None 2nd element\n", " print ' *' * depth, 'Found', node[1], 'at node', node[0]\n", " return node[:2] # return tag and element\n", " return explore(node[2], depth + 1) or explore(node[3], depth + 1)" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 13 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Exploring the maze will print out a series of `>` characters as the function recursively calls itself, where the number of characters indicates the depth of the recursion. A series of `<` characters are printed when a recursive calls returns after failing to find anything at a node. A series of `*` characters will be printed if/when a node with `'cheese'` (or anything other than `None`) is found." ] }, { "cell_type": "code", "collapsed": false, "input": [ "explore(maze)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ " Checking node 0\n", " > Checking node 1\n", " > > Checking node 2\n", " > > > Checking node 3\n", " < < < < Nothing found\n", " < < < < Nothing found\n", " > > > Checking node 4\n", " < < < < Nothing found\n", " < < < < Nothing found\n", " > > Checking node 5\n", " > > > Checking node 6\n", " < < < < Nothing found\n", " < < < < Nothing found\n", " < < < Nothing found\n", " > Checking node 7\n", " > > Checking node 8\n", " < < < Nothing found\n", " < < < Nothing found\n", " > > Checking node 9\n", " > > > Checking node 10\n", " > > > > Checking node 11\n", " * * * * Found cheese at node 11\n" ] }, { "metadata": {}, "output_type": "pyout", "prompt_number": 14, "text": [ "(11, 'cheese')" ] } ], "prompt_number": 14 }, { "cell_type": "markdown", "metadata": {}, "source": [ "mazeCallStack.png\n", "Selecting the active elements of the printed trace above when the `'cheese'` is found shows a similar sequence - in reverse - as depicted in the call stack image that Gustavo created:\n", "\n", "
\n",
      " Checking node 0\n",
      " > Checking node 7\n",
      " > > Checking node 9\n",
      " > > > Checking node 10\n",
      " > > > > Checking node 11\n",
      " * * * * Found cheese at node 11\n",
      "
" ] } ], "metadata": {} } ] }