Week 5: Recurring thoughts about recursion

See what I did there? :)

To the best of my knowledge, recursion, to me, is a form of Python script that calls itself to perform a specific task. It eases tasks for which there is no definite/finite number of function calls. Prof. Heap shared with us a simple reasoning. Suppose you wanted to sum a list. Call sum(), right? And if you wanted a depth-1 nested list, you'd loop around it and then sum it up. But what if we didn't know the depth of the list? Say you have 6 loops, but then you encounter a list with depth 7? With the examples we did in class, I understood it as a form of a "nested list unraveller", where you keep calling the function on lists and lists until you finally end up with flattened list and then you perform the function on it. A basic example is:

def f(x):
    if isinstance(x, list):
        return sum([f(a) for a in x])
    else:
        return 1

Where f(x) calls itself every time it encounters a list. With this,

f([1,2,3,4]) returns 4. Is it a list? Yes, now call f(x) for each element in the list, and return 1 if it's a number. This returns a list of [1,1,1,1] to be summed. Because this code calls itself to check for lists, we are essentially providing a quick solution to find out how many elements there are in any depth of a list.

f([1,2,3,4,[55, [1, 3, 44, [12], 1]], [[65]], 12]) returns 12. Notice how the many brackets are basically ignored?

Even then, recursion was a bit of a doozy for me. I attended the night lecture and attempted the given worksheet on tracing recursion. I had trouble (and even on the midterm too), not in understanding the given code, but rather the method Prof. Heap wanted us to write it in. He said that if we knew the trace call, just fill it in directly instead of retracing again. I tried that, thought I felt that my solution was ridiculously short compared to his.

During the lab, I tried again to trace it methodically, and while I understood every solution and problem given, I still had trouble writing the tracing the way Prof Heap wanted. Then came the midterm - a simple 3 questions over 8 pages in 45 minutes (some unwarranted time lost due to the sluggishness of the previous EX100 occupants) with a dead given: a recursion tracing question.

I'd like to say that I can confidently write basic recursive functions without much trouble, though I'd definitely like to see my midterm results first :)

Update: (01 March 2015)

Now having learned about trees (both binary and not), I can definitely see recursion being a useful tool. For example, making a tree with a height of 5 and then performing specific tasks, to my knowledge, is all but unfathomable without recursion. When some of the nodes are leafs, and some aren't, with an indefinite height, there isn't really a plausible solution (that we've discussed in class) that would really work - other than recursion. With this being said, I can now see many possible improvements on many of my other small home-projects that I've been working on. Though I do struggle with some specific tree functions (such as the in_between exercise from lab #6), I do think that recursion can now be confidently added to my toolbox of useful Python tools.