Week 7

Recursion is not intrinsically better or worse than loops - each has advantages and disadvantages, and those even depend on the programming language (and implementation).

In functional programming language implementations, sometimes, for loop can be very expensive and recursion can be very cheap. In many, recursion is transformed into a simple jump, but changing the loop variable (which is mutable) sometimes requires some relatively heavy operations, especially on implementations which support multiple threads of execution. Mutation is expensive in some of these environments because of the interaction between the mutator and the garbage collector, if both might be running at the same time.

In the past test, this question can be solved by recursion or loop.

def rec_len(L):

    """(nested list) -> int

    Return the total number of non-list elements within nested list L.

    For example, rec_len([1, 'two', [[], [[3]]]]) == 3.

    """

    result = 0

    if isinstance(L,list):

        for item in L:

            result += rec_len(item)

        return result

    else:

        return 1

or 

def rec_len(L):

    """(nested list) -> int

    Return the total number of non-list elements within nested list L.

    For example, rec_len([1, 'two', [[], [[3]]]]) == 3.

    """

   return sum(rec_len(x) if isinstance(x,list) else 1 for x in L)

Recursion is more convince.

Reading week

Review? Maybe

return str.join(s, [nested_join(s, x) if isinstance(x, list) else x for x in L])

Empty Stack: (last in, first out) | | | | | | ------- After Pushing A, you get: | | | | | A | ------- After Pushing B, you get: | | | A | | B | ------- After Popping, you get: | | | | | B | ------- class Stack:     """A last-in, first-out (LIFO) stack of items"""     def __init__(self: 'Stack', data: list =None) -> None:         """Create a new empty Stack using data         data --- initial contents of Stack         """         if data:              self._data = data[:]          else:             self._data = []     def pop(self: 'Stack') -> object:         """Remove and return the top item."""         return self._data.pop()     def is_empty(self: 'Stack') -> bool:         """Return whether the stack is empty."""         return self._data == []     def push(self: 'Stack', obj: object) -> None:         """Place o on top of the stack."""         self._data.append(obj)

Binary tree

There is at most 2 children on each node(left children and right children if exists), the degree of each node can be at most 2. Path is a sequence of nodes n1...nk, where there is an edge from ni to ni+1. The length of a path is the number of
edges in it and there is only a unique path from the root to each node.

Binary tree can be combine with recursion to search value by using either pre-order traversal,in-order traversal or post-order traversal. The difference is the order of meeting the root. And is no cycles -- no path from the loop.

Binary Tree

Week 5?

Recursion is more difficult than I expected. It feels like that recursion is the higher level of loop, more helpful under the complex restriction. We spent the whole lab in the first coding question but still not able to solve it out. Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. And, it is said that often, a problem is easier expressed using recursion. This is especially true when you talk about tree-like data structures (e.g. directories, decision trees...).These data structures are finite in nature, so most of the time processing them is clearer with recursion.When stack-depth is often limited, and every function call requires a piece of stack, and when talking about a possibly infinite data structure you will have to abandon recursion and translate it into iteration.Especially functional languages are good at handling 'infinite' recursion. Imperative languages are focused on iteration-like loops. Hope I can handle it in the assignment...