Summary of recursion

In the pass 4 week, i have learned a lot of knowledge about recursion, which is totally new to me.

What I learned first to get knowledge of recursion was about tracing the recursion. In the lab 3, i was given some functions. Here is the Example,

def count_elements(L):
    ’’’(list or non-list) -> int

    Return 1 if L is a non-list, or number of non-list elements in
    possibly-nested list L.

    Assume: L is any Python object.

    # examples omitted!
    ’’’
    if isinstance(L, list):

        return sum([count_elements(x) for x in L])
    else: # if L is not a list, count it

return 1 

When i want to trace  count elements([7, [2, 1, 3], 9, [3, 2, 4]]), the first thing I need to do is to deal with the basic list. The basic list is [7, [2, 1, 3], 9, [3, 2, 4]. After the first step, what we get is sum(1,count_elements([2,1,3]),1,count_elements([3,2,4]). And then , after the step tracing, what we can get is sum(1,sum(1,1,1),1,sum(1,1,1)). Finally, we get sum(1,3,1,3) = 8.. As i described, this is how recursion work. Unlike the function i learned in the pass, the recursion function will recall itself once and once again.

After learning how does recursion work, i study to learn how to write a recursion function, which is hard for me.
We studied how to write the recursion function by introducing Tree and BTnode.
For example, in the quiz5, I need to count the internal nodes of a tree, Tree(17,[tree(2)[tree(5),tree(6),tree(7)],tree(3)[tree(8),tree(9)],tree4)
This tree is look like that,
                17
2               3             4
567           89
As we can see, the num of internal node is 3. They are 2, 3, 17.
In order to write the recursion, i was told by the TA that, i need to study by the basic example.
The basic example is Tree(17), which have no children so that it is not a internal node. So, is a tree have no children, the function will return 0. How thing goes when we get Tree(17, [tree2])? This tree have one children, and the function will return 1. What about a tree likeTree(17,[tree(2)[tree(5),tree(6),tree(7)],tree(3)[tree(8),tree(9)],tree4). Every time we get a node, we will count 1. The function should be something like . 1+***(function(x) for x in tree.chirdren). And we know there are node in the children of the basic tree, then we need to calculate the sum of them. So the function will be 1+sum(function(x) for x in tree.chirdren)
So, when it comes to how to write a recursion function, the most important thing is the basic example. After doing that, it will be much easy to write the function.