One thing that struck me, though, was a particularly strong statement against recursion, on page 397 (2nd Edition):

If a programmer who worked for me used recursion to compute a factorial, I’d hire someone else.

To put this in context, McConnell had just presented a few appropriate uses for recursion (quicksort and maze solving [i.e. graph searching]), and is railing against the simple examples one typically learns in computer science classes. He sees recursion as an advanced technique, which should be avoided unless it provides a clear advantage.

McConnell says recursive algorithms are harder to read. I don’t buy that; it depends on your audience. But his biggest beef is with the stack. When a function calls itself over and over again, the stack grows (keeping track of all the variables in all those function calls) and you can run out of memory, the dreaded stack overflow.

In many computer science departments, the first language you learn is Scheme, which doesn’t support iteration, so you can’t compute a factorial (or do any other kind of looping) without recursion. Scheme handles this with tail recursion elimination, where if the last thing a function does is call itself (i.e. tail recursion), the Scheme interpreter overwrites the stack frame– essentially replacing recursion with a loop.

Since most languages don’t do tail recursion elimination, and since it can be harder to write a function as tail recursive, I mostly agree with McConnell– despite my initial reaction. However, I was thinking about what makes some algorithms amenable to recursion while others are a bad idea.

McConnell’s examples of good recursion– quicksort and graph searching– both involve branching. Most tree algorithms are recursive: one might say a tree is a recursive data structure. The recursive algorithm uses the stack to track the branching, which is cleaner than handling your own stack. (A good programmer can replace any recursive algorithm with a stack-based one.) What makes factorials different is that there’s no branching, so the stack is redundant. So we have two classes of algorithms:

• Branching algorithms, which use recursion to track which branches have been visited.
• Linear (non-branching) algorithms, which should be written in a tail-recursive manner to avoid stack overflows, or written with loops when the compiler/interpreter doesn’t support tail recursion elimination.

I should add that branching algorithms are also susceptible to stack overflows, but since the stack is providing a necessary service, it can’t be avoided with a non-recursive algorithm.

So here’s why I end up agreeing with McConnell: to properly write non-branching recursive algorithms, you must (1) write them in a tail-recursive manner, and (2) run them with tail call elimination. After you write a tail-recursive function, it’s easy to accidentally modify it to no longer be tail-recursive, and the difference can be subtle. That’s why Scala provides the tailrec annotation: so a function that’s supposed to be tail recursive won’t compile unless Scala can apply the tail call elimination. If you need the compiler’s help to safely apply a technique, it’s an advanced technique, and shouldn’t be done lightly.

UCU: Utility — Connector — User Interface

• A Utility provides a well-defined service. For example, accessing a file or storing a collection of items. It has a contract which defines what it does, and its correctness is measured against the contract. That contract is some combination of documentation, code (method signatures, interfaces, etc.), and a test suite.
• A Connector is how components are discovered and constructed. Thus this category includes constructors, factory methods, and dependency injection. Connectors should be simple, since a program consists of a rat’s nest of interconnected components. Bad connections are hard to test, and even harder to debug, so the only recourse is to make them hard to be buggy. Constructors should do no extraneous work, except for checking for illegal arguments. When there’s an illegal connection, the program should fail immediately. For example, a constructor for a database utility which takes a database URL should check the syntax of the database URL, but it should not try to connect to the database. (If the database is inaccessible, that’s a problem with the database, not with the program trying to access it.)
• The User Interface (UI) is the part of the program that relates to how the user perceives and interacts with the program. Its correctness is measured against the user’s experience. (Many practitioners prefer the term UX, User eXperience. In this case, because you can program an interface but not an experience, I am using UI to refer to the software.) Humans have different perspectives, and their expectations may change over time. As a result, UIs are developed using rapid prototyping techniques. Like a Broadway stage, the UI should be designed for frequent and rapid changes. UI components that get reused frequently are really utilities, thus classes tend to migrate from UI status to utility status.

For more reading, here are my earlier thoughts, before UCU gelled. And here’s a Google Tech Talk on writing clean, testable code which influenced UCU.

There are a lot of things going on here. Wealthier families are spending nine times as much on their kids as lower-income families, up from five times in 1972. They’re also spending more time with their kids, particularly before Kindergarten. And I suspect that’s the crucial factor.

There are a lot of single-parent families out there where the parent is working multiple part-time jobs just trying to pay the bills. Compare that with my family, where we have a stay-at-home mom and both parents read to kids every day. It’s just not fair. Don’t get me wrong: I don’t feel guilty that I don’t deserve it. I think everyone deserves to have the same opportunities.

The NY Times article says it’s not just about money, but I think that would be a fine place to start. Labor protections have been eroding as full time jobs have given way to less regulated part time jobs. And the free market isn’t going to fix that—not when the jobs can migrate to other countries.

The inequalities can be solved through services. My family has benefited from parent training and pre-K services (ECFE, for Early Childhood and Family Education), which the school district provides at little or no cost. (Not counting taxes.) Studies have found negligible difference in education between stay-at-home parenting and high quality day care. (What they’ve found is that good parents are better than bad day care, and good day care is better than bad parents.) If parents work, they need affordable, high-quality day care that will prepare kids for Kindergarten.

Some people will call this Socialism, and claim that it will loose to capitalism in the long run. Well, now we have long term data. If you look at countries that do take care of their kids—such as the Scandinavian countries—they’re doing fine. At best, they’re doing much better than the US; at worst, it’s hard to argue that they’re being held back.

There are those who say we can’t afford this. I say we can’t afford not to. For every Steve Jobs or Bill Gates, there are thousands of micro-entrepeneurs who have the drive to build businesses that employ a few people, but collectively do just as much innovation. We need both kinds of entrepreneur. Both exist right now because of quality, affordable, available education. We as a society need to stop penny-pinching away the investments that pay for themselves. Parents understand this for their own kids. Why can’t we agree on it for all kids?

In all seriousness, it’s disingenuous to expect businesses to create jobs. Whether a business sees itself as maximizing profit or maximizing value for a customer’s dollar, employees are expensive and therefore job creation needs to be avoided.

As a software developer, I’ve probably eliminated at least as many jobs as I’ve created. Mostly I’ve eliminated work, which allows people to work on other things and changes the nature of the job. That’s a productivity increase, but not one that gets measured in government statistics. I think I’ve generally made life better for those who have used my software, and the same is true for computer programmers in general. But there’s no guarantee that new jobs (e.g. webmaster) will outnumber the old ones (e.g. phone answering service.) My sense is that most job-creating innovation comes from individuals making incremental improvements to their own jobs, or even inventing their own jobs. And for that kind of innovation you need a middle class with enough of a safety net to take risks.

But it’s not just me. Recently NPR interviewed millionaires affected by the latest tax proposal, and they didn’t manage to find a single one whose hiring decisions would be significantly influenced by changes in the tax rate.

Make refried beans with black beans, using the following modifications to give it a rich mole flavor.

1. Add 0.5 tsp cinnamon when adding the oregano to the onion and cumin.
2. Chop 3 fun-sized chocolate candy bars in the food processor along with the rest of the refried beans.

Serve in soft-shelled tacos or as burritos. This is rich enough that salsa and cheese shouldn’t be necessary, but fresh lettuce and tomatoes are a nice addition. For chocolate, I used two Nestle Crunch bars and one Milky Way.

Another new pattern: the expansion of the iPhone product line down to free-with-a-contract pricing. Apple did this not by creating a new “low-end” model, but by keeping the 3GS around for another year. This move seems so obvious that I’m disappointed in myself for not having predicted it. Operations wise, the 3GS doesn’t just use cheaper components, but because Apple has been making it for two and a half years, they’ve surely streamlined the manufacturing process.

The most important cost savings is the value of simply keeping the factory doors open. For technology components manufacturers, costs break down into two categories: fixed and operational. The fixed costs can be huge. A new chip fab (factory) costs over a billion dollars. Companies like Intel spend the first several years just paying for the R&D and the factory. An Intel processor doesn’t actually start making them any money until they have a newer high-end chip, and the “obsolete” chip gets sold at discount prices. Without the fixed costs, the discount prices have a healthy profit margin.

Video game consoles are built around this model. They keep roughly the same price and the same specs over their lifetime. For the first few years, consoles are a huge bargain: the manufacturers actually loose money on them. Near the end of their lifetime, the components are laughably obsolete, but the price is justified by the huge library of video games they run. This drives their design. Hard disks were added only reluctantly, since their platters don’t get cheaper. Chips are good. And custom anything (processors, controllers, cases) is the best, as R&D is a pure front-end cost which keeps the console distinctive in later years.

Apple knows streamlined manufacturing, and it shows in the iPhone 4’s design. Using an antenna and two panes of glass for the case minimizes materials costs. As does a small battery. Small and thin, few buttons: it’s not just for looks, it’s to maximize the factory’s lifetime. The iPhone 4 was designed to be a third-world discount product. But for now, it’s cheaper to keep making the 3GS in an old factory than to put old components in an iPhone 4.

Of all the paradoxes of Steve Jobs, this is perhaps the most important. He was a perfectionist who didn’t miss deadlines.

This raises many interesting questions, but from an evolutionary standpoint, I see one big one. If IQ is mostly genetic, and it is a major influence in life success (both of which are claimed), why isn’t everyone high-IQ? Is there an evolutionary advantage to a lower IQ (e.g. lower caloric requirements, thus more likely to survive a famine; or lower birthrate?)

This also raises some interesting quandaries. It’s standard practice to do genetic testing on fetuses, to screen for particularly nasty disorders. It’s possible to sequence the entire fetal genome. By the time my kids are grown up, there’s a good chance they’ll be able to do prenatal IQ testing which won’t be as accurate as a real IQ test, but will have decent predictive power.