week7

Recursion:

Honestly speaking, Recursion is the best thing I have ever met in Computer Science.

The application of it is so useful that I really doubt I can write it down properly.

(1)
From my point of view,Recursion is a method sacrificing space in order to shorten time.

When ever a recursion happens, the super level of recursion will be saved. It means that unless the whole recursion get to its end, all these space will be occupied. The bad part of this fact is we never know whether it will end. If the recursion gets to a dead cycle, program will  be crashed by burden of space.

When I say shortening time, it doesnot mean computer running quicker. Although, in fact, recursion does make the program run more effectively.

It saves time of typing!
It saves a lot of time of typing!

Recursion provides a way that fits human mind in!
The logic part of the recursion is not something like 1+1==2.

(2) Recursion application
The application of Recursion is very wild. Any structural data can be handled by recursion.
e.g. a(i)= a(i-1) +a(i-2), where a(1)=1 a(2)=1

binary tree, linkedlist,power sets. These things are defined form bottom and defined to themselves further.

Recursion usually changes a big and complex problem into many similar small problems. Only a few and limited sentences describe a infinite object.




recursion also have some outstanding benefits in some small problems.

Sps there are a n-order ladder stairs, you can go upstairs step by step,or you can step on the second order. how many different moves totally?

def f(x:integer):integer;
   if x==1:
           return 1
   elif x==2:
           return 2
   else:
       return f(x-1)+f(x-2)
using recursion here is a good idea.
if you are asked not to use recursion, you might need to type a lot.
def f:
    if there is only 1 two-steps
    if there is 2 two-steps
    if there is 3 two-steps
.......
maybe you can use
     
     i = 0
     while i< n:
          if there is i two-steps
          ...
          i = i + 1

but obviously, using recursion is more nice and elegent.

when doing a problem by using recursion, I always have a feeling that what I really do is induction.
Start form base case and then somehow make every induction steps to prove or contect each others.

(3)lab:linkedlist
the lab about linkedlist makes me feel really bad.
It is  a really bad idea to implement Queue by linkedlist.
The end of the linkedlist is so unclear that you really need to draw it on a paper to see it.
And whenever doing the changing of the value, you have to care about its  .empty method, or whether its .children method exists.

It is  a challenge but also implies some kinds of data that may not be as easy as we thought.
Recursion need a clear structure, the confusing terminal of linkedlist( okay, I admit that if you draw a paper you will not mix it) makes it hard. When I was doing that lab, I spend most of my time trying to type code to find out whether the .children method exists or not.....

Maybe if the empty checking method is self-contained in each method, rahter than in   .empty  attribute, then thing can be better.