Exercise 0: Squaring the first instance of numbers in a list

Performing a task with each item in a list is something a loop can make trivial! However, sometimes it is more complex. What happens when the task we perform depends on what has already been encountered in the list? In this exercise you’ll create a function to square the first instance (and ONLY the first instance) of a number in a list.

Setup

1. In the comp110/exercises directory, create a directory named review and create a file called square_first_instance.
2. Define a function with the following signature:
   • Name: square_first_instance
   • Argument(s): a List of int values
   • Returns: a List of int values
3. Use the __name__ is "__main__" idiom to test the implementation of your function with some sample calls to it whose return values are printed (documentation: https://docs.python.org/3/library/__main__.html).

Requirements

1. Returns an empty list when given an empty list
2. When given a non-empty list, returns a list where the first instance of a given number is squared, and repeated instances of the same number are ignored (but are still returned in the output list)
   • ex. squareFirstInstance([2, 2]) –> [4, 2]
3. Treats negative numbers separately from positive numbers; Does not ignore 1 when -1 has been seen, for example, and vice versa.
4. Uses correct static type annotations for function parameters and return type

Exercise 1: Translating iteration to recursion

Everything that can be done with a loop, can also be done with recursion. Let’s try translating the following into a recursive function.

def simple_iter(m: int, n: int) -> int:
    while (m <= 10):
        n = n * m
        m += 1
    return n

Setup

1. In the comp110/exercises/review directory, create a file named simple_recur.py
2. Define a function with the following signature:
   • Name: simple_recur
   • Argument(s): two ints
   • Returns: an int
3. Use the __name__ is "__main__" idiom to test the implementation of your function with some sample calls to it whose return values are printed (documentation: https://docs.python.org/3/library/__main__.html).

Requirements

This function should be equivalent to the one written above. In this context, equivalent means that when functions are called with the same arguments, both functions will return the same value.

Exercise 02 – Factorial! (Recursive!!)

1. In the review directory create a new file named fac_rec
2. The function should take in one int and return another int.
3. Compute the factorial of the number and return this value.
   1. Note: you may NOT use the built-in factorial function for this calculation.
   2. We will only test your function with positive integers. No need to worry about computing the factorial of a negative number!

Exercise 03: Only Evens

In this exercise, you will use recursion to process a linked list of ints to return a new linked list of only even numbers.

Setup

1. In the comp110/exercises/review directory, create a file called only_evens.py.
2. Define a function with the following signature:
   • Name: only_evens
   • Argument(s): an Optional Node of ints
   • Returns: an Optional Node of ints
3. Use the __name__ is "__main__" idiom to test the implementation of your function with some sample calls to it whose return values are printed (documentation: https://docs.python.org/3/library/__main__.html).

Requirements

1. When a number in the input list is already even, include it in the result list.

2. When a number is odd, add 1 to it in the result list. Example usage:

    test: Optional[Node[int]] = Node(1, Node(2, Node(3, Node(4, None))))
    only_evens(test)

This should return 2 -> 2 -> 4 -> 4 -> None

Formatting and Documentation

1. Module docstring with a complete first sentence describing program.
2. Initialize a global variable named author with format “FirstName LastName onyen@email.unc.edu”
3. squareFirstInstance function docstring with a complete first sentence describing it.

Solutions

square_first_instance

def square_first_instance(input: List[int]) -> List[int]:
    """Squares the first instance of every number in a list."""
    output: List[int] = []
    numbersSeen: Set[int] = set()

    for i in input:
        if i not in numbersSeen:
            numbersSeen.add(i)
            i = i * i
            output.append(i)
        else:
            output.append(i)

    return output

fac_rec

ef simple_recur(m: int, n: int) -> int:
    """Calls itself recursively 10 times."""
    if m > 10:
        return n
    return simple_recur(m + 1, m * n)

factorial!

def fac_rec(input: int) -> int:
    """Compute factorial recursively."""
    if input == 0:
        return 1
    if input == 1: 
        return input
    return input * fac_rec(input - 1)

Only evens

from __future__ import annotations
from typing import TypeVar, Generic, Optional

T = TypeVar("T")


class Node(Generic[T]):
    """A generic linked list Node for any data type T."""

    data: T
    next: Optional[Node[T]]

    def __init__(self, data: T, next: Optional[Node[T]]):
        """Construct a Node in a Linked list that forms head of a new list."""
        self.data = data
        self.next = next

    def __repr__(self) -> str:
        """Produce a string representation of a linked list."""
        if self.next is None:
            return f"{self.data} -> None"
        else:
            return f"{self.data} -> {self.next}"


def only_evens(input: Optional[Node[int]]) -> Optional[Node[int]]:
    """Only keep the even elements of a linked list."""
    if input is None:
        return None
    first = input.data
    rest = input.next
    if first % 2 == 0:
        return Node(first, only_evens(rest))
    else:
        first += 1
        return Node(first, only_evens(rest))