An Introduction to Recursion and Drawing of n-Dimensional Cubes in Complex Plane

It is hard to imagine objects in higher dimensions than usual 3, however, many mathematical objects live in very high dimensions. For example, binary strings of length n can be thought of as objects that live in n-dimensional space. If we connected these in a certain way we get what is called a hyper-dimensional cube, or simply a hypercube. The image on the left is the 7-dim hypercube and on the right is the 6-dim hypercube.

A hypercube is defined as a graph where each point is labeled by a binary string and there is a line or edge between two points if their binary strings differ by only one digit. A point associated with a binary string of length n will have exactly n neighbors.

Recursion
Recursion is a powerful technique in programming. It allows us to concisely describe a process that reduces the solution to smaller sub-problems.

Let’s look at a recursive way of turning an integer i into a binary string with n binary digits.

def binary(i,n):
    if (n == 0):
        return ''
    else:
        if (i % 2 == 0):
            return binary(i/2,n-1) + '0'
        else:
            return binary((i-1)/2, n-1)+'1'

print binary(10,4), binary(21,5)
#=>  1010   10101

Complex plane drawing of a Hypercube

We will graph each binary string to a (not necessarily unique) point in the complex plane. We do this by working with the nth roots of unity.

An nth root of unity, where n is a positive integer (i.e. n = 1, 2, 3, …), is a number z satisfying the equation
z^n = 1. For each n, there is a set of n complex numbers w, called the nth roots of unity and they form n equally spaced points on the unit circle. This can be seen from applying Euler’s formula:

If we raise the number above to the nth power, we get an even multiple of e^i*pi=-1 which we know must be 1.

We will map each string to the point given by summing all the roots of unity associated with bit position that are set to 1.
This is a linear transformation, but no need to muck things up with matrices. We will compute the linear combinations explicitly.

import math
import cmath
from graphics import *
n=7
while (n > 0):
    nthroots = [math.e**(complex(0,1)*2*math.pi*k/n) for k in range(n)]
    # print nthroots
    win=GraphWin("Complex Plane Drawing",600,600)
    for i in range(2**n):
        bin = binary(i,n)

        #Compute the complex point associated with bin
        cxpti=complex(0,0)
        for j in range(n):
            if (bin[j]=='1'):
                cxpti += nthroots[j]

        #Draw all Edges from cxpti
        source=Point((300 + 75*cxpti.real), (300 + 75*cxpti.imag))
        for j in range(n):
            if (bin[j] == '0'):
                d = cxpti + nthroots[j]
                dest = Point(300+75*d.real, 300+75*d.imag)
                l = Line(source,dest)
                l.draw(win)

        c=Circle(source,5)
        c.setFill('red')
        c.draw(win)
    n=input("Value for n (enter 0 to end)?")
    win.close()

Recursion Workshop

In order to successfully write a recursive function, one that does not go into an infinite loop or raise an exception such as RuntimeError: maximum recursion depth exceeded , or something worse, we must work to reduce the size of the problem we are solving. That is the hard part of recursion. They easy part is following a standard pattern, where we simply call the same function on the smaller problem. Here is an template example for that pattern:

def recursive_function(s):
  if s==0 [or s=='' or s==[] ] 
    return or do something obvious
  else 
       [recall finite iterable collections can be reduced by removing first element] 
       first, rest = s[0], s[1:]
       do recursive_function(s-1 or rest s[1:]) on a reduced problem--assume it works correctly
       return with the finished solution on problem associated with s 

Here are several example exercises and TODO problems for you to study. Copy all the code into your environment, compile, and make sure all tests are True valued.

def countup(n):
    if (n == 0):
        print ""
    else:
        countup(n-1)
        print n ,

#1. TODO: code countdown(n) so that countdown(3) => 3 2 1
#
#



def fac(n):
    if (n == 1):
        return 1
    else:
        return fac(n-1) * n

print "Test fac():", fac(4)==24
#print "Test fac():", fac(0)==0

#2. TODO: code fibonacci(n) or fib(n), so that fib(n)= fib(n-1)+fib(n-2)
#  so that 1 = fib(1)= fib(2), 2 = fib(3),  3 = fib(4), 5 = fib(5)

#print "Test fib():", fib(6)==8




def reverse(s):
    if (len(s)==1):
        return s
    else:
        first, rest = s[0], s[1:]
        return reverse(rest) + first

print "Test reverse():", reverse("google")=="elgoog"

#3. TODO: code scream(s), so that the string that is returned capitalized with an ! after each letter 
# here you can use the string method .upper() 

#print "Test scream():", scream("hello")=="H!E!L!L!O!"
#print "Test scream():", scream("in there!")=="I!N! !T!H!E!R!E!!!"


# Here is a function that recursively generate moves along the edges of the dim-n hypercube so that we visit every node (binary string of length n) exactly once: 

def cubewalk(n):
   if (n==1):
      print 1 ,
   else:
      cubewalk(n-1)
      print n , 
      cubewalk(n-1)

cubewalk(3) 
#=> 1 2 1 3 1 2 1 

#4. TODO:(Extra Credit) code a function visit_sequence(n) that uses the cubewalk sequence to print out the sequence of node labels (binary strings) visited on the walk. Every binary string of length n should be produced one time.
visit_sequence(3) #=>
000
100
110
010
011
111
101
001



#5. TODO: (Extra Credit) code a function that will graphically show the path (say colored in red) of 
#                    the cube walk on the complex plane drawing of the hypercube.

Lab #8 (Due at the end of this week)

Task 1: The digital sum of a non-negative integer n is computed as follows. Sum together all the base 10 digits of n. Write a recursive function that computes digitalSum(n).
Write a function test that compares digitalSum(2745) to 18.

Task 2. Computing Digital Root
The digital root of a non-negative integer n is computed as follows. Begin by summing the base 10 digits of n. The digits of the resulting number are then summed, and this process is continued until a single-digit number is obtained. For example, the digital root of 2019 is 3 because 2+0+1+9=12 and 1+2=3. Write a recursive function digitalRoot(n) which returns the digital root of n.

Task 3: Computing The Hailstone Sequences
The Hailstone sequence starting at a positive integer n is generated by following two simple rules. If n is even, the next number in the sequence is n/2. If n is odd, the next number in the sequence is 3*n+1. Repeating this process, we generate the hailstone sequence. Write a recursive function hailstone(n) which prints the hailstone sequence beginning at n. Stop when the sequence reaches the number 1 (since otherwise, we would loop forever 1, 4, 2, 1, 4, 2, …)
For example, when n=5, your program should output the following sequence:
5 16 8 4 2 1
It is an open problem in mathematics known as the Collatz Conjecture whether there is an integer n for which the hailstone sequence is infinite.

Extra Credit Challenge: Determine the number N < 10**6 that produces the longest Hailstone sequence. See https://projecteuler.net/problem=14 – Thanks to Kyle and Kyle for that reference.

Task 4: You will write the recursive function selectionSortRec(mylist,size) that sorts the list mylist with size items, and will do this in place by mutating the list contents. Your function selectionSortRec() will invoke two other functions that you will write maxIndexRec()and swap().

SelectionSort is based on the following recursive strategy:

def selectionSortRec(mylist,size):
    if (size == 1):
        return None #nothing to mutate
    else:
        mxindex= maxIndexRec(mylist,size)
        swap(mylist,mxindex, size-1)
        selectionSortRec(mylist, size-1)

You will recursively compute the index of the largest element in list by calling maxIndexRec()). You then swap the largest element with the element in the last position of the list by calling swap() (no recursion here). Finally, use a recursive call selectionSortRec() with the same list but now using sublist consisting of all but the last element, i.e., use same list reference and use size replaced with size-1.
You should demonstrate correctness by providing tests for all your functions.