Python - Recursive Algorithms - Practice

QTM 350: Data Science Computing

Davi Moreira

Introduction

---

This topic material is based on Professor Mike Gelbart Algorithms and Data Structures course. It was adapted for our purposes.

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from collections import defaultdict, Counter

Exercise: time complexity of recursive functions

For each of the following recursive functions, determine the time complexity as a function of the input $n$ and briefly justify your answer. Assume $n$ is a positive integer.

def titled(n):
    if n >= 0:
        print('n: ', n)
        return titled(n-1)
    else:
        return "sandwich"

titled(15)

Answer:

def untitled(n):
    if n < 0:
        return "sandwich"
    else:
        print('n: ', n)
        return untitled(n-2)

untitled(8)

Answer:

def does_nothing(n):
    print('n:', n)
    if n == 0:
        return
    does_nothing(n-1)
    does_nothing(n-1)

does_nothing(3)

Answer:

def does_nothing_more_slowly(n):
    print(n)
    if n == 0:
        return
    does_nothing_more_slowly(n-1)
    does_nothing_more_slowly(n-1)
    does_nothing_more_slowly(n-1)

does_nothing_more_slowly(3)

Answer:

def looprec(n):
    print("Hello!")
    print('N: ', n)
    for i in range(n):
        looprec(n-1)

looprec(3)

Answer:

In this exercise, determine the space complexity of hello in terms of $n$.

def hello(n):
    if n == 0:
        return 1
    return hello(n-1) + hello(n-1)

hello(4)

Answer:

Exercise: recursive sum

Write a recursive function rec_sum that takes in a list of numbers and sums up the numbers in the list. If the list is empty, it should return 0. No loops, sum, or numpy operations allowed! And, as usual, a docstring is required.

Answer:

# An empty list
assert rec_sum([]) == 0

# A list with one element
assert rec_sum([32]) == 32

# A list with all positive numbers
assert rec_sum([1, 2, 3, 4, 5]) == 15

# A list with negative numbers
assert rec_sum([1, 2, 3, 4, -5]) == 5

(optional) Exercise 3: recursive graphics

In this exercise you will use recursion to draw the Sierpinski triangle. An image of one such triangle is shown below.

To help you do this, we are providing some code in the cell below. The draw_triangle function draws a triangle for you. When you are done calling draw_triangle as many times as you wish, call show_triangles once to render the image nicely. You do not need to understand how the code below works. You only need to understand how to use it. In other words, read the docstrings, but you don't need to read the code inside the functions.

def draw_triangle(x, y, side):
    """
    Draw an equilateral triangle at (x,y) with side length `side`.

    Parameters:
    -----------
    x : float
        the x-coordinate of the *midpoint* of the triangle base
    y : float
        the y-coordinate of the *base* of the triangle
    side : float
        the length of each side of the triangle
    """
    height = np.sqrt(3)*side/2
    plt.plot([x-side/2.0, x+side/2.0, x, x-side/2.0], [y, y, y+height, y], 'k')


def show_triangles(save=False):
    """
    Make the Sierpinski triangle image look pretty.

    Parameters:
    -----------
    save : bool, optional
        Whether or not to save the image to a file (default: False).
    """
    plt.gcf().set_size_inches(10, 8.6)
    plt.axis('scaled')
    plt.axis('off')
    plt.tick_params(labelbottom=False, labelleft=False)
    if save:
        plt.tight_layout()
        plt.savefig('sierpinski.png')
    plt.show()

draw_triangle(0, 0, 1)  # example: a single triangle (depth=0)
show_triangles()        # show the triangle

Another example is given below: a Sierpinski triangle with depth 1, drawn without using recursion but just by calling draw_triangles 3 times. The point of this is that we provide you with (most of) the geometry, so you can focus on recursion and be less likely to get stuck on the geometry aspects.

draw_triangle(-0.25, 0, 0.5)
draw_triangle(+0.25, 0, 0.5)
draw_triangle(0, (0.5*(np.sqrt(3)/2)), 0.5)
show_triangles()

Your tasks are as follows:

1. Write a recursive function sierpinski that takes four arguments: the coordinates x and y, the side length of the outermost triangle, size, and the depth n. Then, use your function to reproduce the figure above of the Sierpinski triangle with depth 6. Note: your code should only call show_triangles once, outside the recursive function (not within the recursive function)
2. Spend a few minutes contemplating how you would implement this without recursion. Once you have reached a sufficiently hopeless state of mind, record your thoughts here as part of your submission.
3. What is the big-O running time of your code, as a function of $n$?

Note: the drawing could also be achieved by drawing one big right-side-up triangle followed up upside-down triangles inside, but here we're doing it by drawing all right-side-up triangles.

Answer:

!jupyter nbconvert _03-py-recursive-algorithms-practice.ipynb --to html --template classic --output 03-py-recursive-algorithms-practice.html

[NbConvertApp] Converting notebook _03-py-recursive-algorithms-practice.ipynb to html
[NbConvertApp] Writing 299609 bytes to 03-py-recursive-algorithms-practice.html

Have fun!