During this week's lecture, i learned about recursion: what it is, how it looks like in code, and how to trace and understand it. When the professor opened with the example question of how we can add up integers in an arbitrarily nested list, i thought the solution would be using some sort of while loop, and that recursion was simply repeating the same action many times until the desired result is obtained. However, instead of using loops, the solution to the problem was a function that calls itself in its body. At first i thought, will this really work? Wouldn't Professor Heap just get some sort of name error saying that the function name is undefined? But it worked, and the idea of a function calling itself confused me to no end. The only similar thing that i have seen was when Professor Heap introduced the idea of uncomputable problems using halt and naval gaze, and that example was a very confusing one already. However, after working through some tracing exercise for the example function, i realized that tracing function calls on simple to complicated arguments really helped me understand how the function itself works. For example, with the problem of finding the sum of integers in arbitrarily nested lists, i started with example calls on ints, then a single list, and then a list of depth 2, and so on, and i found that tracing recursion is much like expanding out a compact mathematical equation. Starting with the function call on the argument, recursion causes the function to be called on each element of the iterable argument, and then on each element of those, and so on, similar to expanding functions such as (x-3)^3.
During the lab this week, i did some more tracing exercises, and i found that by tracing, i could more or less figure out the gist of a function, however i think that if i were to use tracing to figure out the purpose of a function, i need to come up with relevant examples, for example passing in strings to a function thats meant to work on ints and lists wont achieve much. Just when i thought recursion was a pretty simple idea, i got stumped on the last exercise of the lab, which was to write the body of a recursive function. At this point, i knew that i should include an if statement to essentially separate the arguments of the function into two types, one where object type that the function is intended to work on, and the other where basically every other object type is filtered. The tricky part was implementing the recursion. The function that i needed to write is supposed to find the maximum length of a list in the argument and return that number as an int. I knew that i had to work with len() and max(), however i was stuck on which process i should repeat(with recursion). I knew that i needed to find the length of every list in the argument, and somehow use the max() function to compare them to each other, but there are also other objects such as ints in the argument, and when trying to pass an int to len(), i get an error. Furthermore, int isn't an iterable object, so i cannot use list comprehension to build new lists with len(). I tried to think about the very basics of this problem. The recursive part will repeat that section of the code on every list in the argument, but how do i go deeper and look at each element of the list? In the end i ran out of time before i had to complete my quizz.
At the end of the tutorial, i gave up and asked my T.A. on the possible solutions of this problem, and she showed me a much simpler and different method of implementing this function. Instead of creating a list where each element is an int that represented the length of each list in the argument, i can simply use the max function to compare the length of the outmost list to the length of every list nested inside of it. After thinking about it more at home, i finally came up the solution:
return max( [len(L)] + [length(x) for x in L])
No comments:
Post a Comment