Monday, April 6, 2015

Revisiting... Recursion!

Wow, it's hard to believe that we are already at the point in the course where we have to write the revisiting SLOG! I wanted to do mine on the topic of recursion, since has been, well, a recurring subject. Over the course of this semester, we have been introduced to recursion and befuddled by the idea of calling a function within its own return statement. We have traced recursion calls and convinced ourselves to believe that each recursive call will work if the previous call worked (much like mathematical induction). Most of all, we have wrestled with recursion in our labs, tests, and assignments, and looking back now, I can definitely say I am much more comfortable with it than before. I scrolled down to reread my original entry about recursion, all the way back in week 4, which can be found here: http://angeslog.blogspot.ca/2015/02/recursion.html

Overall, I still agree with my simple entry on my impressions to recursion. It seemed that I had a pretty good grasp on the very fundamentally basic applications of recursion back then, for functions like sum_list. I was able to understand that the reason calling a function in its own function body did not result in an infinite loop of function calls, because of the if/else (looking back, it doesn't always have to be an else statement!) statement that looked for the base case that doesn't require recursion or calling the function and actually returned a value or object.  From there, that value or object is passed on up to the function call that produced it, which returns a new value or object that is then passed up, all the way to the very first function call. This was very well illustrated in labs where we had to deal with trees, and leaves. For example, in the lab from week 6, we were required to complete the body for the following function:

def evaluate(b):
    ''' (BTNode) -> float

    Evaluate the expression rooted at b.  If b is a leaf,
    return its float data.  Otherwise, evaluate b.left and
    b.right and combine them with b.data.

    Assume:  -- b is a binary tree
             -- interior nodes contain data in {'+', '-', '*', '/'}
             -- interior nodes always have two children
             -- leaves contain float data

    >>> b = BTNode(3.0)
    >>> evaluate(b)
    3.0
    >>> b = BTNode('*', BTNode(3.0), BTNode(4.0))
    >>> evaluate(b)
    12.0
    '''

My implementation was the following:

    if is_leaf(b):
        return b.data
    else:
        return eval(str(evaluate(b.left)) + b.data + str(evaluate(b.right)))

At the base case when we had reached a leaf and the first if-statement was reached, we would simply return the leaf's data which was a float. If we hadn't yet reached a leaf, we would keep calling the function on the left and right children of each subsequent node, until we reach a leaf, and then continue passing the data up through the nodes, evaluating along the way to produce a final float. I thought it was really cool how we could break a recursion case down into its base cases, and cases that do require recursive calls.

Now that I revisit my introductory days to recursion, I realize that I also learned through the assignments that the recursive calls don't always have to be in one compact line like the above return statement in the else-statement. In Option A of Assignment 3, I was able to play with recursion with the original Strategy Minimax, which bought about Memoize, Prune, and Myopia. I want to use StrategyMinimaxMemoize to illustrate my point.

In StrategyMinimaxMemoize, I fine-tuned my original recursive function for suggest_move, which significantly improved the efficiency of my code. At each step along the way, if the present game state was not over, and we had to keep checking the subsequent game states down to an end game state, my code no longer simply returned a recursive call to reach those states. Instead, before making those recursive calls, I checked a dictionary of game states, to see if I already encountered this one and had the score already saved. If not, I used recursion to find the score of the present game state, and stored it in the dictionary in case I came across it again in the future. I thought this was really cool, because I was under the impression that recursion had to be a single-line return statement to work properly. Instead we can check values in dictionaries, and assign new values, all the while not breaking the pattern of the recursive calls.

However, not everybody feels the same way about recursion. It was very interesting reading over the thoughts a fellow peer had on recursion, in his or her SLOG entry found here:

http://mycompsciblog123.blogspot.ca/2015/03/revisiting-recursion.html

In this entry, the author mentions why they feel strongly against recursion, because it is difficult to understand the code, and even more hard to debug it. My peer wrote:

I originally found recursion difficult to read. I still 100% agree with this. Despite becoming incredibly familiar with recursive code I still find it a huge pain to read. I am definitely not alone with these thoughts, I have talked to classmates, upper years, as well as professional software developers. I found it incredibly interesting when one of the software developers were told me that recursion is usually frowned upon during most projects. When I asked why, he said that when new people are brought onto a team, recursive code can be very difficult for them to understand how the pre-existing code works... The most frustrated I have been all year was having to debug the minimax algorithm. The main difficulty with going through the code was that it hard to see exactly how the code was looping. With iteration it’s very easy to see how the program loops. With iteration it is usually much easier to see where the code is going to end. With recursion it is exceedingly difficult to see what the code is going to return.

I do agree with some aspects of what he or she had to say. Recursion is more difficult to read, because we don't immediately see what the function is returning, since we have to call it repeatedly. This naturally makes it even more difficult, when we are trying to find an error in our code, because we cannot see what is passed on through each iteration of the function. However, with the aid of a diagram, I think many problems are simplified enough that recursion makes perfect sense. In addition, with recursive calls, the same function is called over and over again, so if we are trying to spot an error, it wouldn't find it seven or eight steps into the recursion - it should be right there in our recursive statement, right from the first call. Although I do see where my peer is coming from in terms of the difficulties presented, I definitely do not believe that "recursion should be avoided whenever possible".

Overall, I think recursion is a super powerful, albeit sometimes slow, tool that really utilizes the computer's power in calculating permutations quickly, when human brain's cannot. Now that we learned some cost-cutting tricks like memoization and alpha-beta pruning, I am even more confidenct in the power of recursion to solve almost anything from sum_list, to minimax, to the many more problems that lie ahead!

No comments:

Post a Comment