Recursion

Oops.  I got caught up enough working on Assignment 2 that I forgot to do this.  *smiles innocently*

Recursion (i.e. the ability to recall the function that is currently processing on a different input) is great in terms of its efficiency in breaking down a problem.  We see recursion everywhere because most tasks are basically menial repetitions of other tasks.

Of course, in lecture, the prof keeps talking about a "recursive insight", and whereas I think that it's more like "essentials to problem solving", it's necessary to know how to break down a problem and where you can start to use the same function over again.   For example, the Towers of Hanoi problem was clear in that since with 4 towers the procedure is to run a solve on 4 towers for i blocks, then 3 towers for n-i blocks, then 4 towers for i blocks again, the 4 towers procedure would have to be recursive as it would call itself for the first and third steps.

Now that we're learning about trees, we see that the same structure appears over and over again, which then allows us to recursively parse trees in their prefix/infix/postfix format.  Looking at a prefix example like last time:
+ 2 * 3 4
We actually just define a function that parses things like trees.  Here the head is the operation and the nodes are the arguments (values).
Given a function eval: Store operator as head.  Store value as node.  If operator found before two nodes full, eval(operator).  When 2 nodes appear, use operator on two nodes and store as node.
This becomes recursive when we realize that shit, what if we find something else that needs to be evaluated first, like the *34?

I find the hardest thing about recursion is probably the implementation.  What looks good in pseudocode usually sucks in actual programming - like that function just now.  Looks great, but looping through inputs isn't actually completely possible.  I guess with a string you could just say
String equation = '+2*34'
then the evaluation function would look like
operator = equation[1]
if equation[2] == '+' | '-' | '*' | '/' | etc. etc. so on so forth:
     String temp_eq = copy of equation from +
     node1 = eval(temp_eq)
or something like that, but that really looks nasty in code.

So yeah.  I need to find something else to talk about next week.