At first, I do not quite understand the definition of recursion, and after doing exercises, I gradually find that recursion is a new method to write a function and it mainly focus on the function that call itself again and again. For example, in order to find the factorial of 3, we can find the factorial of (3-1) = 2 and then times 3 to get the value of 3!. When repeating this process again and again, finally we need to find the factorial of 1 and then times 2 and 3. It is easily to see that the exact same process occurs in order to get the factorial of 3 therefore we can call the function we defined to find the factorial of the next number. Suppose the function we defined to find the factorial of n is factorial(n), then this process can be expressed as n * factorial(n - 1) for each n > 1, however, when n = 1, the factorial of n exactly equals to 1, therefore at this circumstances, we do not need to call the function factorial(n) to find the factorial of 1 and we just need to return the number 1. After considering this, the final code of finding n! is something like this:
def factorial(n):
if n < 1:
return 1
else:
return n * factorial(n - 1)
After doing more examples of the recursion, I find that the basic steps of writing the recursive function is that we need to find the way that the function works at the beginning and then try to write down more examples by assigning different values of the parameter(s) to avoid making mistakes. Although recursive functions repeatedly call themselves, a base case is needed to be the stepstone of the whole function, otherwise the function cannot work, which means that we need to find the most basic step that each of the other steps relies on such as when finding the factorial of n!, we need to write down the factorial of 1 is exactly the value 1 and this value is used when we try to find every value n's factorial.
An important point to notice is that, recursive functions are very difficult to trace since hundreds of steps may be produced when simply calling a single recursive function. In fact, we do not need to trace each of the steps of the recursive functions but we need to try our best to understand the way how the function works instead. Furthermore, we need to write the return statement when writing the base case of the function. A classic example to illustrate this idea is the code for tower of hanoi, which occurs in the first assignment. And the code is like this:
move_cheeses(n - 1, source, destination, intermediate)
move_cheeses(1, source, intermediate, destination)
move_cheeses(n -1, intermediate, source, destination)
The steps of the code are very complicated and impossible to trace them all. However, the easiest way to understand this code is just to treat the first parameter as the number of cheeses we want to move and the second parameter is the original stool, the second parameter is the intermediate stool and the last parameter is the destination stool. Before running this function, we just need to assign value to each corresponding parameter and we do not need to worry too much about how the function works at each steps exactly.
It is hard to believe that I find it magic and interesting to find the recursive way that the function runs. Sometimes it is unbelievable that a complicated function can be expressed as a single line of code and the process to find the way of writing the recursive function is a lot interesting to me.
Now, move on to the topic we discuss during the week 7, this week we are working on the linked list which is another kind of tree that has only one children. It is somehow the same as the binary tree that is introduced in previous week therefore is quite easy to understand and to be accepted. However, some of the codes that professor provided is hard to think about and if I am asked to write the code independently, I cannot rewire the codes the same as the one professor provided. Such as the method called decapitate, the codes in the else clause:
else:
self.empty = True
del(self.head)
del(self.rest)
is hard to think about because I am not sure about how to deal with each of the circumstances exactly.
This week’s lab is about the super class, and it asks us to rewrite the code we finished writing in a previous lab. Things went well when doing the lab exercise except sometimes I cannot understand what we are asked to do even if we have read the instructions.
Assignment 2 is also coming this week and I finished it very quickly since the content is just to design a three different types of trees, including dot root tree, bar root tree and star root tree. I am still working on the problem of how many and what kinds of methods are needed in order to finish the tree classes.
No comments:
Post a Comment