Week 7 Summary and Further Understanding of Recursion
We have already learnt recursion for a month, from simply
tracing recursion, to writing recursive code in class, to various kinds of
applications in trees. Although, recursion is still a difficult for me, due to
a number of exercises and labs, I am more capable in comprehending recursions
and choosing the appropriate strategy to write codes. Based on former slogs on
tracing recursion, I update some summaries and opinions of my own about
recursion.
l The Concept of Recursion
In my opinion, recursion uses self-similar way to simplify the complex
problem layer by layer, and finally takes advantage of the base case (the basic
situation) to solve it.
l Difference between Recursion and For Loop (posted in former slog)
Recursion can solve more complex problems than the for loop. Just like the
example in the lecture, for nest of nest of nest list
([1,2,3,[4,5,[6],7],8,9]), if we want to sum every number in the list,
recursion is best way to do this. It can continue simplifying the list until
the integer number and then sum it up. Therefore, recursion is able to solve
any type of list in spite of its depth. Nevertheless, for loop can only deal
with one depth, through for loop, we cannot get the expected result: 40.
l Tracing Recursion
Step 1: Because of recursion finally traces down to the base case. We
first focus on the base case and
use this to trace back. (Some of people think only when the initial call is the
base case; we return the base case. However, in recursion, all calls will
finally reach the base case.)
Step 2: Plugging the base case into recursive calls deeper and deeper. We
keep tracing with the same function. We get the pattern from 1st
round and apply this into 2nd round, and then gain a new pattern.
Similarly, we apply the new pattern into the 3rd round…we repeat the
same action until the last round, in other words, reaching the base case.
Step 3: From the final pattern gotten from step 2 we are able to figure out
the meaning of this recursion. Based on its meaning, it’s a good idea to check
the whole process in order.
l Understand the Meaning of Recursion without Docstring
As mentioned in last part, we get the appropriate method to understand
recursion’s meaning and purpose.
Here is a small summary to varies kinds of list recursion: (posted in former slog)
a)
Count the number of items in the list
def c(s):
"""Docstring (almost)
omitted."""
return sum([c(i) for i in s]) if
isinstance(s, list) else 1
1)
c(5)
1
2)
c([])
0
3)
c(["one", 2, 3.5])
3
4)
c(["one", [2, "three"], 4,
[5, "six"]])
6
5)
c(["one", [2, "three"], 4,
[5, [5.5, 42], "six"]])
8
b)
The sum of all the items in the list
def c(s):
"""Docstring (almost)
omitted."""
return sum([c(i) for i in n]) if
isinstance(n, list) else n
1)
c(5)
5
2)
c([])
0
3)
c([1, 2, 3.5])
6.5
4)
c([1, [2, 3], 4, [5, 6]])
21
5)
c(1, [2, 3], 4, [5, [5.5, 42], 6]))
68.5
c)
The depth of the list
def c(s):
"""Docstring (almost)
omitted."""
return 1 + max([c(i) for i in n] + [0]) if
isinstance(n, list) else 0
1)
c(5)
0
2)
c([])
1
3)
c([1, 3, 5])
1
4)
c([0, [1, 3, 5],7])
2
5) c([0, [1, 3, 5, [7, [9]]], 11])
4
d)
The maximum number among the length of list and
its sublists
def
c(s):
"""Docstring (almost)
omitted."""
return max([len(n)] + [c(i) for i in n]) if
isinstance(n, list) else 0
1)
c(5)
0
2)
c([])
0
3)
c([1, 3, 5])
3
4)
c([0, [1, 3, 5],7])
3
5) c([0, [1, 3, 5, [7, [9]]], 11])
4
e)
The total number of list and its sublist
def c(s):
"""Docstring (almost)
omitted."""
return 1 + sum(i(j) for i in n) if
isinstance(n, list) else 0
1)
c(5)
0
2)
c([])
0
3)
c([1, 3, 5])
3
4)
c([0, [1, 3, 5],7])
3
5) c([0, [1, 3, 5, [7, [9]]], 11])
4
l How to Write Recursive Code
1) Write the base case first. That is, to figure out what the simplest value should be returned. Think about which is the last step when there is no recursion any more, and that is the base case. Afterwards, write the “if” statement about it and leave “else” for now.
2) Try
to break down the problem into small pieces with recursive thinking. The
lecture examples for tracing recursion can be referenced, which is the process
how does the recursion work.
3) Do the recursion: write recursive step in the “else statement” to break
down the problem into small parts. And we can check it with base case in the
end.
l
Recursion’s Application in Tree
At first, it was a little abstract to think about the recursion in the tree
directly because I did not yet get familiar with this fresh data structure.
Nevertheless, I found drawing a diagram was helpful to understand.
Just like this:
To figure out the tree recursion, as I wrote before, first, write the base
case (base case is always the leaf or root in the tree). Then think out
one-loop recursion. Last step is to plug this one-loop recursion into more
complicated situation to see whether it works or not.
l Reaction to other classmate’s slog
Detailed explanation to every single example in the lecture and lab.
Good
resource to learn Tree. 
没有评论:
发表评论