W7: Summary of Recursion

Have you heard of the butterfly dream?
A man dreaming of being a butterfly dreaming about being a man, dreaming about of being a butterfly dreaming about being a man....

Sometimes I think recursion is a beautiful thing, in a sense, artistic-

but art doesn't always need to be understood; therefore, recursion doesn't need to be understood right?
"Recursion is too deep for me, so I'll just admire it from afar".
 Not exactly.

I've talked about recursion quite a bit already, in the second part of week four's post:
http://ak148slogaddress.blogspot.ca/2015/02/w4-its-week-four.html
as well as touching on it in week five:
http://ak148slogaddress.blogspot.ca/2015/02/w5-re-re-re-re-cursion-recap.html

Now, I know I've said this before but for those of you that don't know,

People often joke, that in order to understand recursion,

you must first understand recursion. 

    So far, I think we've spent a fair bit of time on recursion, I'm not complaining- I find it rather helpful actually. The topic was first introduced in week four; we mostly tried to understand how it worked, tracing and tracing and tracing code. Continuous practice of tracing recursion helped me understand, not completely, I'll admit, but the gist of it. After the midterm, we started writing a bit of recursion and then we learned about trees- no, not maple, not cherry, not birch, not oaks or pines, but binary.

But before we talk about recursion and binary trees, we need to know some terminology.

• root: the topmost node with no incoming edges. In this case, 8.
• node: represented by a number in this binary tree (8, 3, 10, 1, 6, 14, 4, 7, 13). 

All nodes are one of the following:

leaf (children): node with no children (no outgoing edges). In this diagram, 1, 4, 7, and 13 are leaves. Also distinguished by left and right child, a parent (node 6) has a left child (node 4) and a right child (node 7).

internal node (parent nodes): node with one or more children. In this diagram, 3, 6, 10 and 14 are internal nodes.

• edges: indicated by all the arrows connecting nodes.
• subtree: a tree formed by any tree node together with its descendants and the edges leading to them.
• height:  1 + the maximum path length in a tree. For this binary tree, it's height would be 1 + 4 (the longest path) = 5/ A node also has a height, which is 1 + the maximum path length of the tree rooted at that node.
• depth: height of the entire tree minus the height of a node. Length of the path from the root to the node. Depth of node 7 is 4, depth of node 14 is 3, depth of node 10 is 2 etc.

    Now, these trees can get quite long, similar to family trees; and because they can get quite long, this is where recursion comes in. Recursion prevents us from having to go through the trees manually, which would probably take quite a long time, and imagine if you screwed up somewhere :p Now these trees have a base case, one that we can predict, manually and does not require recursion. Then, a general case,  one that calls itself and therefore does require recursion.

Here's an example that Danny showed us in lecture:

the if statement, is the base case- if there are no children, return 1. The else statement, then, is the general case- if there are children, go through the tree, count the number of children and return the sum.

    I think recursion is a simple concept, "a method that calls on itself", but learning how to trace and write it requires more patience and practice. Sometimes it's just hard to see what the function does and is therefore difficult to implement into code. I know I definitely need more practice writing the general cases so bye for now!