Summary of Recursion-Week 7

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.

A base case is the part of a recursive function where it doesn't call itself. Designing a recursive function requires that you carefully choose a base case and make sure that every sequence of function calls eventually reaches a base case.

example: Calculating the Sum of a List of Numbers

                      def listsum(numList):
                           if len(numList) == 1:
                              return numList[0]
                          else:
                              return numList[0] + listsum(numList[1:])

How would I compute the sum of a list of numbers? If I were a mathematician,I might start by recalling that addition is a function that is defined for two parameters, a pair of numbers. To redefine the problem from adding a list to adding pairs of numbers, I could rewrite the list as a fully parenthesized expression. Such an expression looks like this:








total= (1+(3+(5+(7+9))))total= (1+(3+(5+16)))total= (1+(3+21))total= (1+24)total= 25


listSum(numList)=first(numList)+listSum(rest(numList))

In this equation first(numList) returns the first element of the list and rest(numList) returns a list of everything but the first element.

all recursive algorithms must obey three important laws:

1. A recursive algorithm must have a base case.
2. A recursive algorithm must change its state and move toward the base case.
3. A recursive algorithm must call itself, recursively.

summary of Object-Oriented Programming concepts-week 6

Everything in OOP is grouped as self sustainable "objects". The “hand” is a class. Your body has two objects of the type "hand", named "left hand" and "right hand". Their main functions are controlled or managed by a set of electrical signals sent through your shoulders (through an interface). So the shoulder is an interface that your body uses to interact with your hands. The hand is a well-architected class. The hand is being reused to create the left hand and the right hand by slightly changing the properties of it.

 class is simply a representation of a type of object. It is the blueprint, or plan, or template, that describes the details of an object. A class is the blueprint from which the individual objects are created. Class is composed of three things: a name, attributes, and operations.

class human:
        def __init__(self, name, sex, weight):
                self.name=name
                self.sex=sex
                self.weight=weight
__init__ is a special method,  and it is called every time when a new human is created. In a new human, he has some attributes, name, sex, and weight. These attributes describe the human.

         def __eq__(self, other):
                 return self.name==other.name and
                  self.sex==other.sex  and
                 self.weight==other.weight
__eq__is also a special method, and it is used when we compare two human. It is common that when we compare two people, we want to compare their name, weight, height etc. These are all the attributes of the person. It works same way in the class Human. When we compare two human, we compare the attributes of the two human.

__str__ and __repr__are  special methods. Both of the methods return str. __repr__ gives a str representation of the human. __str __gives an easily understandable str representation of the information stored in  the class human.

Impression of First Few Weeks-week 4

CSC148 is an extension of CSC108, which I completely in last year winter term. The first few weeks of CSC148 have been relaxing  as well as tough for me because we started off revisiting the material of CSC108, such as classes and subclasses. However, there is an one semeter gap between taking csc108 and csc148. Everything looks new but familiar for me. I took some time to review csc108 materials.Compared to 108, we focused more on the inheritance of subclasses from their superclasses. Stack is also something new for me. It was interesting to see stacks in programming are very similar to real life "stacks" of things: you can only access the top item and any attempts to access the in-between items can lead to the "collapse" of the stack. 
 
The first assignment is pretty hard. I have not written any codes for almost half years. Since I had other midterms to study, I started off doing my first assignment pretty late. I took very long time  trying to understand the assignment. I was so proud of myself figuring out what first assignment asked me to do. Writing codes went pretty smooth.

 I especially appreciated Prof. Heap's teaching style - the expansion of relatively simple topics to explore their subtleties and particularities beyond basic implementations. 

Recursion-Week 5

This week I learned a new function, called recursive function.

A recursive function is a function that calls itself. Recursion is a powerful tool for solving repetitive problems.Recursion is very useful since it eliminates the unnecessary code and increase the efficiency. During the lecture, we have been showed lots of examples about how the recursive functions work and trace the function from the basic cases, which usually is a non-list element. We then increased the depth of the argument and figured out what the recursive function did.

Here is an example of recursive function


def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
This is how to implement factorial by recursive function.

Base case: if n is 1, then factorial (1) will return 1
second: if n==2, then return 2*1=2
Third: if n==3, then return 3*2*1=3!
....


The lab exercises except for the last question were very similar to what we did in the question. We were ask to trace some recursive function. At first glance, it was very hard to tell what the function acutually did without tracing some few examples. I realized that it was a very good idea to write down as a side note  how the functions worked for each level of input. It would help me to have a generalization for the higher level case which was not able to be traced. The last question asked us to code a recursive function. My partner and I had a hard time with that. I tried type in the code that I thought it should be write, but all test cases failed. I hope that Danny will talk about how to code a recursive function next week in the lecture

That is what I have for this week.


**8