Recursion,[Re,[cu,r],[[s],ion]

This is the fifth week that I have known the recursion. I am getting more and more familiar with recursion. However, I am on the way to understand and to use it still.

 

First of all, I want to talk about my own opinion of recursion. The most straightforward way to explain recursion is that calling a function inside itself. 

 

This is a picture about recursion on wikipedia.
A visual form of recursion known as the Dorste effect. The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn contains a smaller image of herself holding an identical object, and so forth.

More precisely, recursion is a process of repeating objects in a self-similar way and stop repeating when it achieve its goal. 

 

In csc148, we often use recursion to solve the problem of nested lists because the process of dealing with the lists inside the big list is same as the process of dealing with the whole list.

 

Here is an example.

Def sum_list(L):

Lis=[]

For item in L:

If is instance(item, list):  # (*)

Lis.append(sum_list(item))   #where recursion happended

Else:

Lis.append(item)

Return sum(lis)

 

Lets create a nested list.

>>>[1,3,[4,2],[[4],7]]

 23

 

At (*), the function check whether the item is a list or not, if it is a list, this item will turn back and loop again until the elements inside  the item are all integers. This process makes a new list which contains all the integers in L without sublist or inner list inside it. Therefore, we are allowed to call sum to get the result.

 

 

Recursion really helps a lot when I was working on the assignment one. In Step.5 in assignment one, we were asked to solve four stool instances of Anna Hoy's cheese moving problem. When we try to move the cheeses, we need to determine if the cheese we plan to move is bigger than the top cheese on the destination stool., but if the destination stool is empty, we move the cheese without any judgments.  Hence the process for every move is the same. Using recursion here becomes a very good idea.

Here is my functions.

 

def tour_of_four_stools(model: TOAHModel, delay_btw_moves: float=0.5,
                        console_animate: bool=False):
    """Move a tower of cheeses from the first stool in model to the fourth.

       model - a TOAHModel with a tower of cheese on the first stool
                and three other empty stools
       console_animate - whether to animate the tour in the console
       delay_btw_moves - time delay between moves in seconds IF
                         console_animate == True
                         no effect if console_animate == False
    """
    helper = Helper(model, delay_btw_moves, console_animate)
    n = model.number_of_cheeses
   
    def move_cheeses_3stool(n: int, source: int, inter: int, dest: int):       
        if n == 1:
            model.move(source, dest)
            helper.pri()
        elif n > 1:
            move_cheeses_3stool(n - 1, source, dest, inter) #
            move_cheeses_3stool(1, source, inter, dest) #
            move_cheeses_3stool(n - 1, inter, source, dest)#
   
    def move_cheeses_4stool(n: int, source: int, int1: int, int2: int, dest: int):
        i = n // 2
        if n == 1:
            model.move(source, dest)
            helper.pri()
        elif n > 1:
            move_cheeses_4stool(n - i, source, int2, dest, int1)#
            move_cheeses_3stool(i, source, int2, dest)#
            helper.pri()
            move_cheeses_4stool(n - i, int1, source, int2, dest)#
           
    move_cheeses_4stool(n, 0, 1, 2, 3)

 

You can see that the line with # are where the recursion was being used.

Recursion is really interesting and useful. I like it and wish to know more about it. For programmers, it is really important to learn to be lazy which means that avoiding write repeating code. Recursion helps us achieve that.

 

Finally, using my picture as an example of recursion~~ lol~