The New Turing Omnibus Chapter 55 Iteration and Recursion

Paul Mucur edited this page Aug 11, 2016 · 11 revisions
Clone this wiki locally

Preamble

We christened the new Sheffield Steel breadknife and tucked into some snacks on a rather gloomy Tuesday evening.

The Meeting

We began by discussing what we should do in the meeting. Tom suggested it might be useful to begin by going through the Towers of Hanoi problem mentioned in the chapter. We found objects of different sizes and Paul shuffled them around to demonstrate a solution to the three-disk problem.

We discussed the different ways of thinking about the problem. There was a split between people who seemed to naturally think about the problem recursively while others thought about the iterative algorithm (or some variation of it).

Tom guided us through the recursive algorithm on the board.

Tower of Hanoi algorithm as a tree

  • Tower of Hanoi
  • Number of moves is 2n - 1 as the solution can be seen as a binary tree

We noted that recursive structure of the problem produced a tree. We reasoned that when the leaf nodes are ignored, this is a binary tree, which explains where the 2n - 1 steps comes from. We also noted that the recursive algorithm would move disks in an order corresponding to a depth-first traversal of the tree.

We tackled the first problem in the chapter to produce a proof by induction that there must be at least 2n -1 moves for the given Hanoi algorithm:

Proof that the solution is 2^n - 1

After this, we moved on to think more generally about iterative and recursive algorithms and how you can convert between the two. James noted that recursive algorithms can always be converted to iterative ones – "that's how computers work".

Going in the other direction wasn't so obvious. Tom walked us through a set of mechanical steps that could (more-or-less) be followed to carry out this conversion.

Starting with the following iterative code:

def sum(array)
  total = 0
  i = 0

  while i < array.length
    total = total + array[i]
    i = i + 1
  end

  total
end
  1. Turn local variables into default arguments (chop off head):

    def sum(array, total = 0, i = 0)
      while i < array.length
        total = total + array[i]
        i = i + 1
      end
    
      total
    end
  2. Turn loop condition into a conditional return (chop off tail)

    def sum(array, total = 0, i = 0)
      loop do
        if i < array.length
          total = total + array[i]
          i = i + 1
        else
          return total
        end
      end
    end
  3. Replace next loop iteration with recursive call

    def sum(array, total = 0, i = 0)
      if i < array.length
        total = total + array[i]
        i = i + 1
        return sum(array, total, i)
      else
        return total
      end
    end
  4. Refactor

    def sum(array, total = 0, i = 0)
      if i < array.length
        sum(array, total + array[i], i + 1)
      else
        total
      end
    end

Tom showing how to convert an iterative solution into recursion

We decided to try and follow these steps for the Towers of Hanoi problem. Before we could do that, we needed to implement the iterative algorithm for solving Towers of Hanoi presented in the book. Paul dared to drive and after a brief discussion about Vim undo files we got stuck into implementing the iterative algorithm.

...

...

... to much success!

We then worked through Tom's steps to convert the algorithm to a recursive one.

Retrospective

We held a short retrospective at the end of the meeting. We discussed the CFP and voting process and noted that there isn't much time between meetings and this often feels hurried.

To address this, we decided to decouple the CFP/voting process from the meeting organisation process and have a persistent #topics channel in Slack that allows people to vote at any time for a chapter (or other proposal).

Links to code

## Thanks

Thanks to Leo and Geckoboard for hosting, Richard for working through the proof by induction and Tom for preparing his steps to convert an algorithm from iterative to recursive.