Launching into Computer Science- Unit 8

Unit 8

One activity given was to write the steps for inserting a value into an array in a sorted manner (descending), but applied to the example of placing a random, numbered playing card into your hand. This is a useful exercise- a lesser known tactic for solving algorithm problems is to first write out the steps for solving the problem manually. Doing this provides a base which can be generalized to solve the same problem with different inputs, and once generalized in this way, pseudocode can be written and then tested. In my experience, writing pseudocode first often makes it harder to solve a problem because it makes you write in a generic way, but you may not have an awareness of how to handle different cases at this stage. With that said, this is how I would write the steps:

1. Get a new card from the top of the deck.
2. Determine the value of the new card.
3. Find its intended location by finding where the card is greater than the card to its right, but less than the card to its left.
4. Insert the card between those two cards.

An additional task given was to become familiar with Lists, Strings, Functions, and Recursion. Based on previous experience with recursion, I’ve always found it a challenge to find other use cases for it, apart from classic examples which are nearly always mathematical in nature (e.g. the factorial function, or Fibonacci sequence). For this section, I wanted to challenge myself by finding a more real-world usage of the function, and eventually came up with the idea of using it to list all subdirectories and files in a folder, choosing to use this as my demonstration for one of the class seminars:

import os
def enumerate_folders(folder_path):
    with os.scandir(folder_path) as entries:
        file_entries = os.listdir(folder_path)
        file_entries.sort(key= lambda e: e.count("."))
        for entry in file_entries:
            full_path = os.path.join(folder_path, entry)
                        
            if os.path.isdir(full_path):
                spaces = len(folder_path) * " "
                nested_path = f"{spaces} - {entry}"
                nested_path += "/"
                print(nested_path)
                enumerate_folders(os.path.join(folder_path, entry))
            elif entry == file_entries[-1]:
                spaces = len(folder_path) * " "
                nested_path = f"{spaces} ⌞ {entry}"                
                print(nested_path)
            else:
                spaces = len(folder_path) * " "
                nested_path = f"{spaces} | {entry}"                
                print(nested_path)

An interesting discovery I made as well, is that Python has a recursion limit. Based on the previous knowledge, I thought that the limit exists because recursive functions use the stack exclusively. All recursive computation results will be stored until the function exits (due to scoping), but because the stack has a finite amount of memory, it’s possible to run out of memory before the computation can complete, hence the recursion limit for safety. I did some research but realized this was only partially correct. The recursion limit exists because Python doesn’t support a form of recursion known as tail recursion. Tail recursion is an optimization applied by certain languages (like C), which allows one stack frame to be recycled for all recursive calls (Microsoft, 2008; StackOverflow, 2008). This means that extremely large inputs can be done recursively without running out of memory. But due to the fact that Python can’t optimize recursive code in this way, a limit has to be set for how far a function can compute (Python Software Foundation, 2021).

References Microsoft. (2008) Understanding Tail Recursion. Available from: https://docs.microsoft.com/en-us/archive/blogs/chrsmith/understanding-tail-recursion [Accessed 21 April 2021]. Python Software Foundation. (2021) sys — System-specific parameters and functions. Available from: https://docs.python.org/3/library/sys.html#sys.setrecursionlimit [Accessed 21 April 2021]. StackOverflow. (2008) What is tail recursion? Available from: https://stackoverflow.com/questions/33923/what-is-tail-recursion [Accessed 21 April 2021].