Some thoughts on recursion

It’s the fourth week of CSC148 and just a brief summary of what I have learnt: First week, object-oriented programming, the second week, inheritance and recursion, the third week, exception, and this week, more on recursion. Also, assignment 1 came out and it’s basically about the Hanoi tower with more than three pegs. Today, I am going to talk something about recursion. The most well-known recursive thinking, I believe, is the Fibonacci sequence – 1, 1, 2, 3, 5, 8…… Starting from the third number, each number is the sum of the two numbers before it.(5=2+3, 8 = 3+5) Every time we want a number, we need to know the two numbers before it, and to know the two numbers, we need to know the two numbers before themselves.  This may sound confusing, but it would be clearer when put into code.

The base case returns 1 when n equals 1 or 2 and if n is greater than 2, the program would firstly calculate the sum of the (n-1)th number and (n-2)th number, and to calculate the (n-1)th number, the program would calculate the sum of the (n-2) and (n-3)th number, and same for all the numbers until the program reaches base cases and return 1. Starting from 1, the program adds these numbers together and produces the nth number we want. As Danny said in class, tracing a recursive function could be too complex to handle, so my way of tracing the code is to use abstraction – Find patterns of the code for the first or two cases, then apply these patterns to more complex cases based on the assumption that the code could work properly.

As seen from the Fibonacci sequence program, through recursion, we can significantly reduce the length of the code. Through abstraction, recursion would be much easier to understand than writing in for loops or other loops. However, recursion, for most of the times, actually lowers the efficiency of the program. Thus, when using recursion, we need to find a balance between efficiency and code length – if the code could be converted into for loops while not extending much length, it is better not to use recursion. So analyze at the very beginning, and decide which way we are about to use.

What is Object-Oriented Programming

When I started to learn Python a few months ago, I was introduced that Python is an object-oriented programming language and the essence of OOP are ‘encapsulation, polymorphism, and inheritance’. These words used to confuse me. But now, they start to make sense.

    During the first week, when we analyze the statement about an object called Point, we designed the attribute (‘coord’) for a point and a method to calculate the distance from the point to the origin. Instead of directly writing separate functions to set the ‘coord’ for the point and calculate the distance outside the class, we write these functions (methods) inside the class and use the property function to control access to ‘coord’. By creating a class for Point and infesting it with methods as well as attributes, the program is no longer just processing data but creating objects that have their own attributes and methods encapsulated in the class. Only output and input matters and the process are hidden inside. It’s kind of like us, human – inside us, organ’s function to keep us alive. All the metabolism and actions are controlled by things inside us – ‘encapsulated’ and other people could hardly see the process but the input and output

Then comes to polymorphism and inheritance. As Prof. Heap talked during lecture, laziness is the first thing learnt in programming. Here laziness didn’t mean too lazy to give up tasks but avoiding duplicate code. Like the coord argument passed to Point object in its __init__ method, by using list comprehension [float(x) for x in coord], coord with different lengths could be put in and the class will still work. So we can avoid writing different classes for Points with different number of coordinates. Another thing about laziness is inheritance. A class could inherit all the methods from its parent class while still leaves space for programmers to override or modify the methods based on specific needs. For instance of the ‘IntStack’ we created later, by reusing __init__ method from the parent class Stack, it avoids many duplicate codes. Even though inheritance is useful, it’s better to avoid multiple inheritance since it will become harder to trace which method the class is actually using which will cause serious problem when debugging.

When I was testing my code, I found a flaw of python class. Even though we can use property function to control access to attributes, we can never fully protect them from being modified outside the class. Unlike Java where we can use ‘Private’ to hide attributes, in python, ‘_’before the name of attributes and property function are just nice ways of informing programmers not to modify them.

    To conclude, object-oriented programming is, in some sense, creating real stuff and give it real attributes and ability for some actions. Like human, all the process are encapsulated inside the body (encapsulation), different inputs may result in different outputs but not error (polymorphism), and inheritance.