Week 7: Recursion

    Recursion is a programming strategy, and a major topic in this course. It makes the functions of computer programs a ton more efficient, but it takes more sophisticated thinking to write. All recursion really is, is including a function call of itself within the body of a function. For example, having a line in the function f(x) that calls f(x-1). It sounds pretty simple, but there's a lot of guidelines to consider when making a recursive call or else you will lead to bugs and errors.

    First off, you must include a base case. Your function won't stop running if there isn't a set point to reach. Recursive functions are meant to break down a task into smaller versions of the same task, until it can't be broken down anymore. The point where the task can no longer be broken down is called the base case. I'll take an example of one we used in class, modified so the body isn't a single line, just to make it easier to read.

def preorder(tl: 'TreeList') -> list:
    """
    Return list of values in tl in preorder

    >>> preorder([5, [4, None, None], [3, [2, None, None], [1,                       None, None]]])
    [5, 4, 3, 2, 1]
    """
    if tl is None:
        return []
    else:
        return ([tl[0]] + preorder(tl[1]) + preorder(tl[2]))

In case you haven't noticed, this is the pre-order traversal I explained in my last post, now as a python function. In the end of that post, I explained that a tree can be represented as a list of [int, Tree or None, Tree or None] I also mentioned a simple recursive 3-step approach to doing all pre-order traversals. All three steps of that approach are expressed in the else statement above. The if statement is our base case. This is the non-recursive action that the program makes when the problem has been broken down as far as it should go. t1 is None translates to the root / child node not existing, therefore adding nothing to the resulting list that represents the pre-order traversal.

    Recursion can get much more complicated than this. To make good use of recursion, you need lots of practice with writing different function bodies to develop a good sense of what actions can work recursively, and what actions should be part of the base case. A more complicated example of recursion is in a function learned in class that writes the steps to solving the Towers of Hanoi game with 3 stools, in the least steps possible. That function involved breaking down the game into 3 smaller recursive steps:

1) Move all rings except bottom to intermediate stool.

2) Move bottom ring to destination stool.

3) Move all rings except bottom to destination stool.

When you begin step one, all three steps are used again just to complete step one. That means the second-to-bottom ring is used as the bottom ring when step 2 is called during the process of completing step 1. Also, that second-to-bottom ring will be taken to the overall intermediate stool. Every function call changes what the source, destination, and intermediate stools are, to make sure the function still works. When enough rings are involved in this game, the game can be broken down to the point where the (third, fourth, fifth, etc.)-to-bottom ring is used as the bottom ring. This is recursive to the point where there is only one ring above the "bottom" ring, and that ring is simply taken to whatever the current intermediate stool may be.

    In Assignment 1, I invented my own set of recursive steps for a function that completes the Towers of Hanoi game with 4 stools, using the same ideas. It was very efficient and it broke the game down into 5 smaller recursive steps:

1) Move all rings except the bottom two to i1 (since there are 4 stools, the two intermediates are labeled i1 and i2)

2) Move second-to-bottom ring to i2

3) Move bottom ring to destination

4) Move second-to-bottom ring to destination

5) Move all rings except the bottom two to destination

My function looks like this in python:

def fourD_m_c(n, source, inter1, inter2, dest):
    if n == 2:
        print("Move top cheese from {} to {}".format(source, inter1))
        print("Move top cheese from {} to {}".format(source, dest))
        print("Move top cheese from {} to {}".format(inter1, dest))
    elif n > 2:
        fourD_m_c(n - 2, source, inter2, dest, inter1) #all but bottom 2
        fourD_m_c(1, source, inter1, dest, inter2) #second to bottom
        fourD_m_c(1, source, inter1, inter2, dest) #bottom
        fourD_m_c(1, inter2, source, inter1, dest) #second to bottom
        fourD_m_c(n - 2, inter1, source, inter2, dest) #all but bottom 2
    else:
        print("Move top cheese from {} to {}".format(source, dest))

    The words ring and cheese can be used interchangeably. The five steps I explained before are expressed under the elif n > 2 statement. The else statement is the base case, and I still haven't at all explained the purpose of the body of code below the if n == 2 statement. This is sort of like a second base case and this was necessary because my 5 steps don't know how to handle the game when the bottom two rings are in fact all of the rings involved in the game. Therefore, the purpose of this body of code is to manually move those two rings when the situation arises. This body of code is only ever reached when the overall game involves an even number of rings. When the overall game involves an odd number of rings, the game is never broken down into smaller games that involve exactly 2 rings, so this body won't be needed or used.

    My function completed the 4-stool game in less steps than the function given in our lecture. I was proud of my function, but my assignment partner discovered an even more efficient function, and that function was submitted instead :<

Data Trees

    Data Trees are a type of structure to store information in, and we learned about these in class. You can view them visually like this:

    A tree is a series of nodes that have a very strict pattern structure. But first, here are some terms:
Parent: A node that points to another node, and  (Nodes 3, 5, 1, 9, and 7 above are parents.)
Siblings: Nodes with the same parent. (Nodes 5 and 1 are siblings.)
Root: A node with no parents. (Node 3 is a root.)
Leaf: A node with no children, and isn't actually considered a node. (3, 2, and 8 are leaves)
Internal node: A term that includes nodes and roots. Every part of a tree is either an internal node or a leaf.
Arity: A property of a tree that determines the maximum amount of children nodes in the tree may have. (The arity of the tree above is 2.)
Path: A path of nodes that are connected by the arrows (3, 1, 7, 2 is a path)
Tree Length: A property for a tree determined by the length of the longest path. (3, 1, 7, 2 is one of the longest paths in the tree, it's path length is 3 so the tree length is 3.)

Here are some rules:
- Every non-root node has exactly one parent.
- No cycles. A path on a tree cannot lead to an earlier node.

    Thanks to these rules, you can isolate an internal node and all of it's paths, and you have another tree that follows the same rules! This new tree is called a subtree. I wouldn't know for sure, but I think this is might be a very valuable trait for trees and this is why we learn about them.

    There are also different ways to traverse (read all of the internal nodes and leafs) a tree, including pre-order traversal, in-order traversal, and post-order traversal. They are all difficult to understand at first, so I started by studying the recursive-style definitions for each one that were given in the slides in class:

pre-order traversal: Visit root, then pre-order left subtree, then pre-order right subtree.
in-order traversal: Visit in-order left subtree, then root, then in-order right subtree.
post-order traversal: Visit post-order left subtree, then post-order right subtree, then root.

This is pre-order traversal. It goes 3, 5, 6, 9, 4, 1, 7, 2, 8. I'll remember it quickly by taking note of the following:

Pre-order traversal:
1) root
2) left (in pre-order)
3) right (in pre-order)

This is in-order traversal. It goes 6, 5, 4, 9, 3, 1, 2, 7, 8. Notice the unnecessary detours in the blue line after 9 and before 1. They are to illustrate that if there was a second child from 9 or 1, they would've been visited before the next one on the traversal.

In-order traversal:
1) left (in in-order)
2) root
3) right (in in-order)

This is post-order traversal. It goes 6, 4, 9, 5, 2, 8, 7, 1, 3. Notice the unnecessary detours in the purple line after 9 and before 1. They are to illustrate that if there was a second child from 9 or 1, they would've been visited before the next one on the traversal.

Post-order traversal:
1) left (in post-order)
2) right (in post-order)
3) root

You can also write recursive functions in python for all of these traversals when trees are defined as a list of [int, tree or none, tree or none]. the int in place 0 is the node, the tree in place 1 is the left child, and the tree in place 2 is the right child. If there is None instead of the tree, than there is no child.

how python searches for names

    Last week, I learned how python searches for names. Python programs call variable names all the time. Things can get confusing when the same name is used in different places of the same code to define different things. This is why python searches for names in a particular order:

-First, it searches for a local variable name (a variable usually defined within the same function as the call)
-Second, if there is no local variable name, it searches for a nonlocal variable (a variable defined not within the same function as the call, but instead defined in a larger function that includes the function with the call)
-Third, if there is no nonlocal variable name, it searches for a global variable (found on module level or under __main__)
-Finally, if there is no global variable name, it looks for any built-in python names

    I prepared an example of python code where this order comes into play:

vari = "spam0"

def my_scope_test():
    vari = "spam1"
    def inner_function1():
        global vari
        vari = "spam2"
        print("inner function1() searches for:", vari)
    
    inner_function1()
    def inner_function2():
        print("inner_function2() searches for:", vari)
        
    inner_function2()
    print("my_scope_test() searches for:  ", vari)

my_scope_test()
print("the module level searches for: ", vari)


When this code runs: here is what is printed:

inner function1() searches for: spam2
inner_function2() searches for: spam1
my_scope_test() searches for:   spam1
the module level searches for:  spam2

The variable named "vari" is defined three times: First at the module level, second within a function, and third within an inner function, but with a global assignment. (That makes the definition as if it were made in the module level, and how it would be defined without the global assignment) In the same order, these definitions at different points in the code are considered global, local/nonlocal, and global/local. The variations depend on which stage in the code execution these variables are called. I will now walk you through python's thought process for each name search:

inner_function1() needs to find vari to use for it's print statement.
Step 1: local variable name? Yes!
So it uses the variable definition within inner_function1() for the print statement.

inner_function2() needs to find vari to use for it's print statement.
Step 1: local variable name? No
Step 2: nonlocal variable name? Yes!
So it uses the variable definition within the overlapping function my_scope_test() for the print statement.

my_scope_test() needs to find vari to use for it's print statement.
Step 1: local variable name? Yes!
So it uses the variable definition within my_scope_test() for the print statement.

the module level needs to find vari to use for it's print statement.
Step 1: local variable name? Yes!
The module level's local variable names are the global variable names. The global definition for vari has been written twice, so it uses the latest definition, which occured when inner_function1() ran.

    Later in this same lecture when I learned all of this, it was demonstrated that this kind of logic also occurs when working with classes and methods, instead of what we just did with functions. Python looks for methods in the class before looking for methods in the superclass. This order of searching for methods in class and superclasses is called inhertance, which is very similar to the all the name searching I just wrote about.
    That's everything I know about name searching, I might make another post about Assignment 1 after it's finished and after the due date has passed.

exercise 2 finished + what I learned + things

    Exercise 2, at least to me, was about practicing making our own error messages. It was very straightforward, but before starting with this exercise, I needed some help from a friend to teach me some new python commands and concepts that I didn't learn in CSC108 (or in class either, because I wasn't paying close enough attention):

-Every error message you get in python comes from a built-in class called 'Exception'.

This is important for making your own customized error messages, because in order for those customized messages to work like any other error message, you must make a new subclass of Exception. 

-The command 'raise'.

raise is needed for when you want to call a class. If I wanted to call a subclass Customized_error that I made to display my customized error message, I would write the following line in my code:

raise Customized_error("customized error message")

-The commands 'try' and 'except'.

'try' is used for when you want to run a function to see if an error is caused, but not return what the function is supposed to return. 'except' is to be written after try, then followed by the name of an error class or subclass. If that error class or subclass is reached during the call of the function, the line acts very similar to an if statement that returns True, and the program then decides to run the code that is written within the indent of this 'except' line.

    This was basically everything I needed to learn in order to finish the exercise. Other than that, my new time slot on Monday-Wednesday mornings is working out much nicer for me, but I've lately been giving more attention to my other courses. This will probably change I hope. Yes.

Week 3: Object-Oriented Programming

    Object-oriented programming is a way to write code by creating your own types for the objects you create, via classes. These types are designed to make an object store data in the same way that object stores data in real life. The type for an object that was made through a class is typically a combination of types that are already built-in to the programming language. For example, In CSC108 last semester, we practiced with a class called "Day" in python. The type of a "Day" object is a combination of 4 pieces of information: day, month, year, and events.  In specifically this case, day and year are integers, month is a string, and events is a list. Any of these pieces of information can be called to in a very visually-friendly manner, and I think this might be the reason why we like Object-oriented programming so much and why we're supposed to get used to doing a lot of it, especially in our larger, more complicated programs.

feeling disoriented

    After checking my email, I realized I need to make weekly blog posts in addition to 3 other specific posts, so here is my first one. I was enrolled in the 6-8 Wednesday lecture at first, and I missed the first one because my flight from vacation was delayed. I went to the second week's lecture and I realized this lecture simply wasn't right for me. I went onto ROSI and am now enrolled in a Monday-Wednesday morning lecture time table, so I'll have to see how this one works out.

    The only thing I managed to learn about in class was recursion. The most notable example of the recursion for me was in the function for adding all of the numbers in a nested list. The English translation for the piece of python code that used recursion in that function goes like this: "If the current iteration is looking at an inner list instead of a number, then run the function again for that inner list."

    I know in this blog I'll soon have to write something specific about object oriented programming, so my next course of action is to read about that from the links on the course website.