6 ms·
On the one hand, I'm in total agreement that we shouldn't tell students recursion is hard. It's a very natural analog to proof by induction, after all. It's a
by colomon 16y ago
On the one hand, I'm in total agreement that we shouldn't tell students recursion is hard. It's a very natural analog to proof by induction, after all. It's an important basic component of programming.
On the other hand, "IMHO, recursion is much more natural than iteration and ought to be taught first" is just nuts. I mean, look at the first definition of his example function at http://en.wikipedia.org/wiki/Exponentiation http://en.wikipedia.org/wiki/Exponentiation -- it's iteration, pure and simple. And in most non-functional languages, it's trivial to implement that way, and will probably be more efficient than a recursive solution.
- jinfiesto 16y agoI don't think the example I've given is iterative. It generates a recursive process. You're right on a different point though, this example is much more efficiently implemented iteratively. The point was to illustrate that writing recursive functions is not difficult. I guess we don't see eye to eye on recursion being taught first. :p In my opinion, recursions analog to "the real world" is much more intuitively obvious than iteration.
- fferen 16y agoI think parent was referring to the definition on the Wikipedia page: "When n is a positive integer, exponentiation corresponds to repeated multiplication." And then an equation that suggests an iterative approach.
- colomon 16y agoExactly. Good catch.
- charlieflowers 16y agoActually, I think your example generates an iterative process, not a recursive process. In other words, according to what I read in SICP recently (working through it the first time), I think your example is a recursive function that generates an iterative process. It's an iterative process because incoming function arguments capture a snapshot of its state at any point, and therefore you don't need state that exists deeper on the call stack. The upshot is that iterative processes are more efficient in terms of how much stack space they use. Not trying to nitpick -- I enjoyed your post and it is still relevant. Also, I could be wrong, so someone please correct me if so.
- delinka 16y agoint pow(int b, int e) { return b * ((e==1)?1:pow(b,e-1)); }
- colomon 16y agoYes, the author defines exponentiation in terms of recursion. My point is that is not the natural definition of exponentiation, and my evidence is the Wikipedia page, which (as of the time of my original posting of the link, anyway), gives an iterative definition of exponentiation first -- the exact same one I learned in grade school -- and then several pages later mentions a recursive definition as a one-sentence aside.
- delinka 16y agoI'm having problems finding the examples you mention in the wikipedia article. That notwithstanding, I disagree that either method is "natural." Iteration is just what they taught you as a child. If we taught recursion instead (specifically for exponents), then that would be the "natural" method. The point with my C function is that it's certainly simple to do in a non-functional language.