So I learned something interesting about recursion, by way of happening upon something confusing in my lab. Because I like super-simple examples, imagine the following code:
def add_strings(x:list of str) -> str:
""" Takes a list of strings, and sticks them together.
Recursively.
"""
if len(x) == 2:
return x[0] + x[1]
else:
return stick_together(x)
def stick_together(y: list of str) -> str:
return add_strings(y[:-1]) + y[-1]
Okay, before some of you get mad, let me just say that I chose a simple example for a reason.
For the rest of you: what is going on here? One function calls another, which calls the first one. Could this be, *gasp*, meta-recursion???
Let's break it down. Consider this function:
def add_strings2(x: 'list of str') -> str:
if len(x) == 2:
return x[0] + x[1]
else:
return add_strings2(x[:-1]) + x[-1]
Well that was easy. But see, these two are the same function. The secret is that stick_together is a helper function -- one that contains the recursive call. This was really not obvious to me the first time I encountered it, because the functions were a lot more complicated (after a good deal of thought, we were able to make it into a single function). I can't decide whether there's a good reason to know this or not, but now, it just seems trivial.
Ok another recursion question: when do you NOT want to use it?
Let's use the recursive list-summing function as an example:
def r_sum(nested_num_list):
tot = 0
for element in nested_num_list:
if type(element) == type([]):
tot += r_sum(element)
else:
tot += element
return tot
[Stolen from this page linked to from the course website]
The obvious answer is that you don't need recursion when a simple for-loop will do. If you know that your input will never be nested, then writing this function is far to complex for what you really need to do (hint: try the builtin sum()).
I can think of another reason, though:
>>> mylist = [0]
>>> mylist += mylist,
>>> mylist
[0, [...]]
>>> mylist[1]
[0, [...]]
>>> mylist[1] is mylist
True
This is a list containing a reference to itself. mylist is [0,mylist]. The sum of these elements has got to be zero, right? Because it contains no non-zero numbers? Well, try it.
>>> r_sum(mylist)
Yeah. This problem is a little too big for recursion. Sorry.
RANDOM SLOGS OF THE WEEK! (explanation here)
The unambitious marking scheme:
C - Average. Probably not worth looking at, unless you want to read all of the slogs.
B - Above Average. One or two neat things. Maybe try it if you're looking for content on those particular topics.
A - Excellent. Lots on interesting ideas that aren't easy to find elsewhere. Probably worth visiting; I'd expect to find more interesting content here in the future.
D - Below Average. Not reader-friendly. Maybe take a look to make sure you're not making the same mistakes.
F - Fail. Fatally flawed; for example, not having any content. I hope I don't find any of these.
Third Week by VVXiyang Rain
def add_strings(x:list of str) -> str:
""" Takes a list of strings, and sticks them together.
Recursively.
"""
if len(x) == 2:
return x[0] + x[1]
else:
return stick_together(x)
def stick_together(y: list of str) -> str:
return add_strings(y[:-1]) + y[-1]
Okay, before some of you get mad, let me just say that I chose a simple example for a reason.
For the rest of you: what is going on here? One function calls another, which calls the first one. Could this be, *gasp*, meta-recursion???
Let's break it down. Consider this function:
def add_strings2(x: 'list of str') -> str:
if len(x) == 2:
return x[0] + x[1]
else:
return add_strings2(x[:-1]) + x[-1]
Well that was easy. But see, these two are the same function. The secret is that stick_together is a helper function -- one that contains the recursive call. This was really not obvious to me the first time I encountered it, because the functions were a lot more complicated (after a good deal of thought, we were able to make it into a single function). I can't decide whether there's a good reason to know this or not, but now, it just seems trivial.
Ok another recursion question: when do you NOT want to use it?
Let's use the recursive list-summing function as an example:
def r_sum(nested_num_list):
tot = 0
for element in nested_num_list:
if type(element) == type([]):
tot += r_sum(element)
else:
tot += element
return tot
[Stolen from this page linked to from the course website]
The obvious answer is that you don't need recursion when a simple for-loop will do. If you know that your input will never be nested, then writing this function is far to complex for what you really need to do (hint: try the builtin sum()).
I can think of another reason, though:
>>> mylist = [0]
>>> mylist += mylist,
>>> mylist
[0, [...]]
>>> mylist[1]
[0, [...]]
>>> mylist[1] is mylist
True
This is a list containing a reference to itself. mylist is [0,mylist]. The sum of these elements has got to be zero, right? Because it contains no non-zero numbers? Well, try it.
>>> r_sum(mylist)
Yeah. This problem is a little too big for recursion. Sorry.
RANDOM SLOGS OF THE WEEK! (explanation here)
The unambitious marking scheme:
C - Average. Probably not worth looking at, unless you want to read all of the slogs.
B - Above Average. One or two neat things. Maybe try it if you're looking for content on those particular topics.
A - Excellent. Lots on interesting ideas that aren't easy to find elsewhere. Probably worth visiting; I'd expect to find more interesting content here in the future.
D - Below Average. Not reader-friendly. Maybe take a look to make sure you're not making the same mistakes.
F - Fail. Fatally flawed; for example, not having any content. I hope I don't find any of these.
Third Week by VVXiyang Rain
- Well, there's only one post. Strike one.
- The post starts with "OK so this is the first time that I write my slog..." Helpful.
- And it ends with "Hope things will get better." Well, so do I.
- Actually the middle is pretty odd as well, it contains ambiguous statements such as "But sadly I did worst in Class in 108".
- Seriously though, this is very "I did this today"-style. Like going down a checklist: I did this, then this, then this, etc. Nothing exciting.
- There are no spaces between sentences. Anywhere. Seriously?
- The title. "Third Week". Is that a reference to the fact that he hasn't used it since the third week of the course, the date of the only posting commemorated forever in the url? I mean, I can only hope it's not a Nazi Germany pun.
- Rating: D- I've had enough.
Slogging Through 148 by Neil
- Neil brings a very out-of-field approach to computer science. For those of you who are struggling to find interesting things to write about, I bet you could take a few pointers from this guy.
- I like his writing style. :)
- Rating: B+ And a good one at that. This could easily be an A.
CSC148 SLOG by TheCoder
- Not a lot of content (two posts overall)
- TheCoder does a lot of reiterating concepts. However, the author does a good job of being concise and relevant.
- TheCoder does a lot of train-of-thought checklisting, another thing which is generally annoying. Again, the author does a good job of being concise and relevant with it, keeping it in check.
- Rating: C+ I get the impression that this person could write a good blog, but doesn't want to do one on this topic.
- Snazzy! The blog looks good. And that is definitely a plus.
- The content is the most checklist-y I think I've encountered so far. The most reflective comment I can find is "It looks cool".
- A general note: don't say that you hope you will be able to solve a problem -- and then never tell us. The interesting part comes in hearing how the difficult thing was solved.
- Another note: you don't need to tell us that you find something confusing. That's really not interesting or meaningful to read about. But the things is, I'm pretty sure that I've done that myself, here. So I'll leave that as a takeaway for everyone, and try not to hold it against the author.
- The subtitle says that he/she dedicates the blog to keep track of, among other things, "how I overcome every problems [sic]". Typo aside: the blog simply doesn't do that. It talks about lots of problems, but almost no solutions. I disapprove of lying to your readers right at the top of the page.
- Rating: C-
CSC148 by Angel
- No content. Not even hummingbirds can save you from that.
- Rating: F
If you have questions about my stuff, hate me because I insulted your blog, or just fancy a chat, feel free to comment.
--David
No comments:
Post a Comment