recursion.md

Recursion day

Talk to other people - this didn't happen enough last week! Many people are already good at using recursion, and but would still learn something by working through problems with you. Consider describing your strategy before actually implementing it. Try doing this on a whiteboard.

Some resource to come back to later:

• The little schemer - a mindbending intro to programming and recursion
• SICP section 1.2 - you might need to read 1.1 to get up to speed
• Add some more! Is there a MOOC you really like the recursion section of, or a textbook that gives it a nice treatment? Add it on Zulip and I'll add it here.

Recursion Warm up - do these problems with just recursion

0. Write a naive fibinacci function recursively. It should look a lot like below, but you'll need to add some code: (Bonus for later: memoize this) Explain it to someone else.

    def fib(n):
        return fib(n-1) + fib(n-2)
   

1. Warm up: using no loops (for, while, etc.), and no global variables, write a function that returns the sum of a list: Also, no cheating and calling methods that do significant work for you (i.e. sum(), reduce(), etc. are all off limits).

    sum([1, 2, 3, 4, 5]) -> 15
    sum([]) -> 0
   

2. Again, using no loops, no global variables, no calling len() and no helper functions write a function that returns the last index of a given input in a list. Negative one gets returned if the element doesn't occur in the list.

    lastIndexOf(5, [1, 2, 4, 6, 5, 2, 7]) -> 4
    lastIndexOf(5, [1, 2, 4, 6, 2, 7]) -> -1
    lastIndexOf(5, [1, 2, 5, 4, 6, 5, 2, 7]) -> 5
   

3. Try the same thing for a linked list:

    lastIndexOf(5, [1, [2, [4, [6, [5, [2, [7, None]]]]]]]) -> 4
    lastIndexOf(5, [1, [2, [4, [6, [2, [7, None]]]]]]) -> -1
   

4. Draw a picture to show someone why the data structures above are called linked lists. Something like Online Python Tutor may help if you don't have someone to explain this to you.

5. What are the performance differences between this and an array, for finding the value of an index, adding an element to the beginning, adding an element to the end, inserting several elements at a spot, combining to sorted lists, and finding a value in the list?

6. Write a recursive function to compute the sum of a list of numbers.

7. Write a recursive function to compute the sum of a binary tree of numbers. An example of a tree is below.

Word problems

(No longer required to use only recursion - use whatever you like)

Wordplay

9. Generate all the reorderings of a set of letters.
10. List all of the series' of letters (non-dictionary words, 'asd' and 'w' count) that can be formed with some scrabble tiles on a blank board. (In scrabble, you don't have to use all your tiles at once)
11. List all of the valid words (give some dictionary) that can be formed with some scrabble tiles on a blank board

Step Climbing

1. A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Write a function that, given the length of the staircase, tells you how many ways there are to go up the steps.

Project Euler #15

1. How many ways are there for a taxi driver to get from the top left of a grided city to the bottom right? The city is exactly 10 blocks in each direction, all streets are two ways, and the driver knows you know the city well enough that he won't try to go away from the goal - so never up or left, only right and down.

Change Counting

10. The change counting problem from SICP: http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html

Minimax

10. Write a recursive function that calculates the minimax "value" of a board in Tic-Tac-Toe :) X always goes first.

N Queens

10. Write code that will find one solution to the 8 queens problem

Tree

Here's an example of a tree:

class Node(object):
    def __init__(self, value, l=None, r=None):
        self.value = value
        self.left = l
        self.right = r

tree1 = Node(1, 
             Node(2,
                  Node(3),
                  Node(4)),
             Node(5,
                  Node(6),
                  Node(7)))

tree2 = Node(1,
             Node(2, 
                  Node(3)),
             Node(4))

6. Print the elements of a tree with such a structure depth-first (in the order 1, 2, 3, 4, 5, 6, 7 for the tree1)

More Recursion Practice

6. Write a recursive implementation of the map function.
7. Write a recursive implementation of the filter function.
8. Write a recursive function that inserts an element in the right place into a linked list. The function should return a new linked list rather than mutate the original list.
9. Write a recursive function that enumerates the nodes of a tree in depth-first {pre|in|post} order.
10. Write a recursive function that computes the number of ways of distinct k-element subsets of a set with n elements. In other words, "n choose k".)
11. Explicitly compute (rather than just counting) all k-element subsets of a set.
12. Write a recursive function that computes the power set of a set.
13. Write a recursive function that generates all possible partitions of a set.