I am trying to get better at recursion!

I spent a couple of hours studying recursion, as it seems to be a weak point for me right now. In order to this, I went back to the week 4 recursion lab and re-worked through the problems. Also, I went back to some of the class examples.

I believe one of the problems I have is that I over-think the problems. For example, I was working on the problem of trying to reverse a string. My first attempt at a recursive solution was to create an accumulator that would hold the last letter of the string. Then, if the string was one character long, I would return only that letter. If the string was longer, I would re-call the function using the current string, minus the last letter. The code looked like:


def rev_string(s: 'str') -> str:

    new = ""
    if len(s) == 1:
        return s
    else:
        return rev_string(s[:-1])


This is clearly wrong because obviously my accumulator variable does nothing. I end up returning the last letter of the string s, because I am not actually adding on letters to my accumulated string, new.

After some thought, I realize that the function I was trying to write practically writes itself. For example, if I want to reverse a string, I simply take the last letter and add the reversal of all preceding letters:


def rev_string(s: 'str') -> str:
 
    return s[-1] + rev_string(s[:-1]) if len(s) > 0 else s


Not only does this function work, it looks a lot simpler.
Brief explanation on how it works:
If the string, s, is longer than a single character, take the last letter of s and add the reversed string of all preceding letters (by calling the function recursively).
If the string, s, is only a single character, simply return s. (This is the 'base case')

For example, if I want to reverse 'asdf', I want to take the last letter 'f' and add rev_string('asd').
But rev_string('asd') gives 'd' + rev_string('as'), and so on. So, the final return value ends up being
'fdsa', as desired.

This was sort of a long post on a seemingly easy example, but recursion was something that did not come naturally to me.

Week 6 - Trees and a1

Assignment 1 is finished. I had to do some last minute fixes to my code which was a bit stressful but I'm glad it is finally done.

This week in lecture we covered trees. This is an ADT that is interesting to me because it is almost entirely a recursive data structure. When I look at the tree implementation code, it looks very simple and elegant because there is very little code you actually need to write. However, it would be quite difficult for me personally to come up with the tree implementation on my own.

So far I don't know where I would use trees in practice. Perhaps they are used to represent information in a hierarchical manner?

The week 6 lab was the easiest lab so far. It only required us to complete a few functions and write some test cases which was not difficult at all, although I guess I need to practice writing unit tests because I always forget how to write those.

Unfortunately assignment 2 and test 1 are coming up so I can't relax too much during reading week...

Progress - Assignment 1 and Week 5 material

I have completed assignment 1, cool.

I am fairly certain everything works the way it should. Also, I wrote docstrings, comments, and made sure the pep8 tests passed. 

That being said, I am still not completely confident in writing recursive functions. I understand the main ideas of recursion but coming up with the code to a specific problem can be tricky. The lab this week was on recursion. We did manage to get to the 'extra' problems, but then we got stuck on one of the problems. I think one of the problems I have with recursion is that I over-think the problem. Usually the solution ends up being simpler than I thought.

In lecture we covered the Tower of Hanoi algorithm and talked about namespaces. Admittedly, the content was quite boring this week. This was probably because I was able to easily grasp the concepts presented this week.

Intro to recursion, assignment 1 - Week 4

This week in lecture, we covered recursion by going through some examples. One of them was figuring out the "maximum depth" of a nested list. The other was drawing a fractal tree using Turtle. In both cases, I was able to trace the code presented, but I am still not satisfied. I don't feel like I fully understand recursion yet. I would have a hard time coming up with recursive algorithms on my own, so I feel like I need to practice writing recursive programs on my own.

On Thursday, I spent the entire day working on assignment 1. I managed to complete parts 1-4 which I am very happy about. I am able to manually use the GUIController to move the cheeses, and I'm also able to use ConsoleController to play the game. All that remains is figuring out an algorithm for the four stools problem, and implementing it in Tour.py. I am fairly confident that all the code I have wrote so far is "good" code. I did docstrings and examples which work as well, so I feel good about this assignment so far.

Truthfully, when I first read the assignment handout I kind of freaked out because there was so much starter code and information. It seemed overwhelming, but I tackled the problem one step at a time. Before I even started writing code, I made notes and tried to figure out what to do before doing anything. I think this was a good strategy, as it allowed me to complete TOAHModel.py in just one day.