Project 2: Recursion

Project 2: Recursion


Recursion is a fundamental technique to apply to problems in computer science. Recursion allows us to explore structures of arbitrary depth, to solve problems by dividing them into smaller sub-problems, and more. One of the most popular techniques for use in technical interviews, recursion is inescapable in the study of data structures and algorithms.

Assignment Overview
In this project, you will be implementing recursive functions for a singly linked list. Like Project 0B, each node contains a value, and a reference to the next node. There are two recursion approaches that we use in this project. Some functions will have a corresponding inner function that will be recursive, while other functions will themselves be recursive. Every function you implement should utilize RECURSION. In functions that utilize an inner function, this recursion will take place within the inner function. For more explonation, check out the specification document for CC2, where we defined inner functions.

Assignment Notes
You are required to add and complete the docstrings for each function. They should be in the exact same format as project 1. This should include at least a one-sentence description of the function, all parameters, and what the function returns. Please see Project 1 DLL.py  for reference on how to complete docstrings for each function.
All of your functions must be recursive. You will lose all points related to the function if it is not recursive. MORE SIMPLY PUT: YOU MAY NOT USE ANY `FOR` OR `WHILE` LOOPS IN THIS PROJECT!
Do not use additional data structures, such as lists or strings, unless specified otherwise. You will lose all points relating to the function if you do.
In addition to the Mimir testing, you will also be graded on the time performance of your functions. Take note of the time complexity requirement for each function.
No hardcoding testcases. If you do this, you will lose all points for the function.
Assignment Specifications
class Node:

Do not modify this class

Attributes:value: Value stored in a Node
next: Reference to the following Node (May be None)
__init__(self, value: T, next: Node = None) -> None:This function initializes a node with a given value and next reference, pointing to the next Node in the list.
self.value - the value of the Node.
self.next - the next Node in the list, default value is None
__repr__(self) -> str:A node is represented in string form as ‘value’.
__str__(self) -> str:A node is represented in string form as ‘value’. Use str(node) to make it a string.
__eq__(self, other: Node) -> bool:This function compares two Nodes.
other - the right-hand operand of the “==”
Returns either True or False
class RecursiveSinglyLinkedList:

Do not modify the following attributes/methods

Attributes:head: The first Node in the linked list (May be None)
__init__(self) -> None:This function initializes a RecursivelySinglyLinkedList
__repr__(self) -> str:A string representation of the list.
For this to work, you must have completed to_string
__eq__(self, other: Node) -> bool:This function compares two RecursiveSinglyLinkLists.
other - the right-hand operand of the “==”
Returns either True or False
You must implement the following functions in SLL.py. Take note of the specified return values, input parameters, and time complexity requirements. Do not change the function signatures.

to_string(self, curr: Node) -> str:
Generate and return a string representation of the list, starting at head curr
The values should be separated by a “ --> “ (a space followed by two hyphens, a greater than symbol, and then another space)
Return an empty string if there are no nodes in the list.
You are allowed to use strings in this function.
This function must be recursive
Time complexity: O(n2), due to the run time of string concatenation in python.
length(self, curr: Node) -> str:
Determines the number of nodes in the list starting with head curr
If the list is empty, it has a length of 0.
This function must be recursive
Time complexity: O(n)
sum_list(self, curr: Node) -> T:
Calculates and returns the sum of the values in the list starting with head curr
If the list is empty, it has a sum of 0.
This function must be recursive
Time complexity: O(n)
push(self, value: T) -> None:
Insert the given value into the linked list
The value should be inserted at the end of the list
Return the starting node of the linked list
Must call push_inner
Time complexity: O(n)
push_inner(curr: Node) -> None:
This is a helper function for push
Insert the given value (from push) into the linked list that has head curr
The value should be inserted at the end of the list
This function must be recursive
Time complexity O(n)
remove(self, value: T) -> None:
Remove the first node in the list with the given value
If the value doesn’t exist, do not change the linked list
Must call remove_inner
Time complexity: O(n)
remove_inner(curr: Node) -> Node:
This is a helper function for remove
Remove the first node in the list with the given value (from remove) starting at head curr
If the value doesn’t exist, do not change the linked list
This function must be recursive
Time complexity O(n)
remove_all(self, value: T) -> None:
Remove all nodes in the list with the given value
If the value doesn’t exist, do not change the linked list
Must call remove_all_inner
Time complexity: O(n)
remove_all_inner(curr: Node) -> Node:
This is a helper function for remove_all
Remove all nodes in the list with the given value (from remove_all) starting at head curr
If the value doesn’t exist, do not change the linked list
This function must be recursive
Time complexity: O(n)
search(self, value: T) -> bool:
Looks for value in the list
Returns True if the value is in the list and False if it is not in the list
Must call search_inner
Time complexity: O(n)
search_inner(curr: Node) -> bool:
This is a helper function for search
Looks for value (from search) in the list starting with head curr
Returns True if the value is in the list and False if it is not in the list
This function must be recursive
Time complexity O(n)
count(self, value: T) -> int:
Counts and returns how many times the given value occurs in the list
Must call count_inner
Time complexity: O(n)
count_inner(curr: Node) -> int:
This is a helper function for count
Counts and returns how many times the given value (from count) occurs in the list starting at head curr
This function must be recursive
Time complexity: O(n)
reverse(self, curr: Node) -> Node:
Given a list starting with head curr, reverse this list. 
Return the head of the reversed list.
This function must be recursive
Time complexity: O(n)
Application Problem: 
 

In this application problem, you are an adorable character from the game Animal Crossing. An important part of the game is crafting: putting different ingredients together to create a new item. While crafting, it is quite tedious to remember all of your different recipes and to check that you are carrying the right ingredients. So, to speed up this process, you will need to write a function that checks your pockets for the ingredients necessary to craft an item, given by a recipe.

You have decided to store the recipes and your pocket contents as linked lists, where each ingredient is one Node. Your function must determine if you are carrying all of the recipe ingredients in your pockets. That is, your function must determine if every element in the recipe list is in the pocket list. This includes having the correct number of a specific ingredient. If a recipe calls for two (or more) of the same ingredient, at least that many ingredients must be present in the pockets list.

If you determine a recipe is able to be crafted, remove the ingredients used to craft it from the pockets list. If the recipe is not able to be crafted, leave pockets unchanged.

To do this, you will implement one function:

crafting(recipe: RecursiveSinglyLinkList, pockets: RecursiveSinglyLinkList)-> bool
Given two linked lists, recipe and pockets, determine if the values in the recipe list are contained in the pockets list.
If all the values in recipe are present in pockets, they will be consumed, and therefore must be removed from pockets.
Return True if the pockets contain enough ingredients to complete the recipe, False otherwise.
This function must be recursive - NO `FOR` or `WHILE` loops are allowed.
You may not use any additional data structures other than linked lists in this function
Time complexity: O(rp)*
* Where r is the number of elements in the recipe and p is the number of elements in your pockets.

Examples:

Ex1. 

recipe = wood --> wood --> clay

pockets = apple --> wood --> clay --> wood

Returns: True, because each element in the recipe list is present in the pockets list.

pockets, after function call = apple

Ex2.

recipe = sand dollar --> sea snail --> gold nugget --> gold nugget

pockets = wood --> sand dollar --> gold nugget --> sea snail --> clay --> bamboo piece

Returns: False, because the recipe requires two golden nuggets, but you only have one in your pokets.

pockets, after function call = wood --> sand dollar --> gold nugget --> sea snail --> clay --> bamboo piece

Submission

Deliverables
Be sure to upload the following deliverables in a .zip folder to Mimir by 11:59p ET on Friday, January 29th.

Project2.zip

    |— Project2/

        |— README.xml      (for project feedback)

        |— __init__.py     (for proper Mimir testcase loading)

        |— SLL.py          (contains your solution source code)

 

Grading

Tests (72)
Manual (28)README.xml is completely filled out with (1) Name, (2) Feedback, (3) Time to Completion and (4) Citations: __/2
to_string, length, sum_list Time Complexity __/3
push Time Complexity __/3
remove Time Complexity __/3
remove_all Time Complexity __/3
search Time Complexity __/3
count Time Complexity __/3
reverse Time Complexity __/3
crafting Time Complexity __/5
Fun Aside
Here's some calm/relaxing Animal Crossing music to work to remix 1, remix 2, comp
Created by Andy Wilson, Lukas Richter, and Andrew Haas