tracing recursions

We started talking about Recursion last week. Recursion is a quite interesting idea, which requires adequate amount of thinking and can simplify the loops by a lot if used properly. And I guess Danny must be loving it, since it's such a "lazy" way of writing codes.LOL

When I first heard this idea during lecture, a few sentences came to my mind:
To see a world in a grain of sand
And a heaven in a wild flower,
Hold infinity in the palm of your hand
                                              And eternity in an hour.

It may sounds nonsense, but personally I feel there is a correlation. Recursion is just like a sand, inside you find a whole world, and inside that world you still have a sand, and it loops. However, in recursion, you will finally reach a point where you can exit the loop.

We focused on tracing recursions last week, here is a brief example:

def sum_list(L):
    ’’’

    (arbitrarily nested list of int or int) -> int
    Return the sum of all ints in L.

    >>> sum_list([1, [2, 3], [4, 5, [6, 7], 8]])
    36
    ’’’

if isinstance(L, list):



        return sum([sum_list(x) for x in L])   # calls isinstance(), sum(), sum_list() methods 

else:

        return L              # base case

1.sum_list(27) --> 27      ＃ int, depth(0)



2.sum_list([4, 1, 8]     --> sum( [ sum_list(4), sum_list(1), sum_list(8) ] )

                                     --> sum([4, 1, 8])

                                     --> 13                           # depth(1)



3.  sum_list([4])    --> sum([sum_list(4)])      




         -->sum([4])
         --> 4

4. sum_list([]) --> sum(sum_list(x) for x in [])
           --> sum([])     
           --> 0




5. sum_list([4, [1, 2, 3], 8])  --> sum([ sum_list(4), sum_list([1, 2, 3]), sum_list(8)])  

                                                    # already traced depth 0 and depth 1

                                                    --> sum([4, 6, 8])

                                                    --> 18




6.  sum_list([[1, 2, 3], [4, 5], 8])  --> sum([sum_list([1, 2, 3]), sum_list([4, 5]), sum_list(8)])

                                                      # already traced depth 0 and depth 1

                                                      --> sum([6, 9, 8])

                                                      --> 23




7. sum_list([1, [2, 2], [2, [3, 3, 3], 2]])  --> sum([sum_list(1), sum_list([2, 2]), sum_list([2, [3, 3, 3], 2])])

                                                               # already traced depth 0, depth 1 and depth 2

                                                               --> sum([1, 4, 13])

                                                               --> 18




8. sum_list([1, [2, 2], [2, [3, [4, 4], 3, 3], 2]])  --> sum([sum_list(1), sum_list([2, 2]), sum_list([2, [3, [4, 4], 3                                                                                , 3], 2])])

                                                                          # already traced depth 0, depth 1, and depth 3

                                                                          --> sum([1, 4, 21])



--> 26



First, be clear about the base case. 

Then just trace the recursion step by step, and we use the results before, otherwise the tracing will be too long.