Week 12- weekly post

This week’s topics were memory model, tracing, and consequences of recursion.

When searching for the names in python, it looks in order of innermost scope (local), enclosing scopes (non-local), global, and built-in names.

When tracing, we are recommended to trace the non-recursive case and then trace the next-most complex case.

Fibonacci number is introduced to apply in to show how to avoid redundant calls. We create another function inside of function, and inner function is recursive to collect Fibonacci- appropriate number (key-value) pair in dictionary created in outer function. This is useful for minimizing repeating steps that look for same value twice or more times. This is called memorization.

Finally in the lecture, professor Heap described the quicksort, one of fast sorting function we already have seen in lab 9. First quicksort just starts with index 0, and use recursion to collect numbers less than item at index 0 and item at index 0 and then numbers greater than or equal to item at index 0. In second quicksort function, we pick a random number to do the same steps as first quicksort but using that random number instead of index 0 item (number).

In a final lab, we use a single list which must represent the complete binary tree. Instead of using BTNode class, we only use a single list to execute the several methods.