# 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.