Recursion

I made some comment to Kris recently about how I wish I had more formal computer science training. I took all of two programming classes in college, and learned the rest on my own. I believe I do okay, since programming is essentially solving one big logic problem, but every so often I solve a problem with brute force instead of creating an elegant solution.

Kris offered to help me out with the formal computer science education, and suggested we go through his Algorithms book. I agreed, figuring it would happen not before next year, given all of my copious free time.

When I was at Hackday yesterday, Kris pinged me and asked if PHP could handle recursion, which cracked me up (the answer being, uh, yes, of course). When I said yes, he asked me if I could write a recursive function that printed out a series of numbers, from one to the single function argument N. The two keys to this problem were recursion and single parameter.

Counting down from N to 1 was easy. I figure both are easy, but counting down is clearly the easier:

function kris($n = 1) {
  print "$n ";
  if ($n > 1) {
    kris($n - 1);
  }
}

Oddly enough, counting up was harder for me. I told Kris he couldn't offer any hints, and eventually I figured out a convoluted solution using a static variable. My solution clearly showed me my lack of CS education. Kris' solution was much simpler:

function kitt($n=1) { 
  if ($n>1) { 
    kitt($n-1);
  }
  print "$n ";
}

As Kris commented, people forget you can do the recursion first, and the action second, when writing recursive functions.

A candidate at Kris' work was unable to solve the problem, and he wanted to see if I could, especially since I was commenting on the CS education I didn't have. I did solve it, but not correctly.

Next time, I'll have the trick. This time? I felt like an idiot.