Rad wrote on Aug 15^th, 2009 at 12:18pm:

The lowest level would probably be binary instructions that the CPU understands natively.  I think that is what people mean when they refer to machine language.

Rad wrote on Aug 15^th, 2009 at 12:18pm:

That is how I understand it.  Assembly is human readable machine language.

Rad wrote on Aug 15^th, 2009 at 12:18pm:

In the case of the C compiler, it converts to binary that can be executed directly by the kernel.  Other compilers, like Java or Perl, might convert to something called bytecode and then the bytecode is interpreted into binary instructions at runtime.


Rad wrote on Aug 15^th, 2009 at 12:18pm:

Allowing you to abstract out a process lets you put more meaning into a single statement.  For example, adding the area of two circles when given the radius might look something like this:

area = 3.14 * r1² + 3.14 * r2²

Now, if you can abstract out the formula for the area of a circle into a function we'll call circleArea(), you could rewrite the above in terms of that function:

totalArea = circleArea(r1) + circleArea(r2)

The second version is more expressive because you say more in less code, and what you are trying to do is much clearer to someone who might read your code later. 

If we can gain some expressiveness by abstracting something simple like calculating the area of a circle, imagine what can be gained by abstracting something complex.

Rad wrote on Aug 16^th, 2009 at 1:54pm:

It's obvious after someone points it out, but I didn't see it either until after I got through SICP.

Rad wrote on Aug 16^th, 2009 at 1:54pm:

Depends on what kind of programming you are doing.  Knowing assembly probably won't improve your shell scripting any.  On the other hand, if you want to write an operating system, it is probably essential.

Rad wrote on Aug 16^th, 2009 at 4:59pm:

I'll try.

In both, you are breaking a problem into smaller sub-problems and then solving the sub-problems.  The difference is that in iteration, you have an answer for each sub-problem before moving onto the next sub-problem.  With recursion, each sub-problem depends on the answer from the next sub-problem, so all the sub-problems wait until the last sub-problem is solved before they can each finish.

There might be a more formal and complete definition somewhere, but that's off the of my head.  It's easiest to see if you look at an example of code from each, so I'll demonstrate with some sudo-code (not syntatically correct for any particular language) to find factorial numbers:

4! = 4 * 3 * 2 * 1
5! = 5 * 4 ...
0! = 1 (this is by definition)

so the iterative solution would be something like:

sub factorial ( inputNum ) {
  answer = 1
  for loopCount = 1 to inputNum {
       answer = answer * loopCount
  }
  return answer
}

Basically this initializes the answer at 1, loops from 1 to the input number, multiplying the answer by the number of the loop we are on each time.  (This particular implementation wouldn't work for negative factorials, but its just to demonstrate an iterative procedure.)

The recursive solution would be something like:

sub factorial ( inputNum ) {
   if inputNum = 0 then return 1
   else return inputNum * factorial( inputNum - 1 )
}

So, if the input number is 0, this version immediately returns 1.  If the input number is not 0, we return the input number multiplied by the factorial of the input number - 1.  The second factorial function call goes through a similar check to see if the input number is 0.  If not, the process repeats until the input number becomes 0.

At that point, 1 is returned.  That allows the next to last call to return 1 * 1, which allows the second to last call to return 2 *1, which allows the third to last call to return 3 * 2, etc until all calls to factorial have returned and we have the correct answer.

Recursion can be a very expressive way to solve problems, but it has some dangers.  For example, we saw that the iterative version doesn't find the correct answer for negative numbers.  The recursive version, on the other hand, won't ever return an answer at all.  If given a negative number, it will enter an infinite loop and, if left running long enough, will take up all available memory and crash the machine it is running on.

The book Higher Order Perl has a great discussion of recursion.  An old version (although still perfectly relevant) is available online:

http://hop.perl.plover.com/

I've actually read (although not necessarily fully comprehended) most of that book.  I learned so much from it that I bought the dead tree version.