I would argue that this is a poor example of code practice. It is a good, for some definitions of good, example of both recursion and asking students to trace good. That doesn’t make it a good way to get 0123456 output to the command line. At least not in my opinion. Someone raised on functional programming where recursion is a pretty standard way of doing looping might disagree of course. I tend to think that:
for (int i = 0; i <= n; i++) System.out.print(i);
is a lot easier to understand however.
There is a saying that when all you have is a hammer all your problems look like nails. This seems, in a way, to be the case with recursion and loops. If your first tool of choice (or what you have learned first) for iteration is loops you tend not to think of recursion as a solution. Similarly if you start with recursion (as is common with functional programming) you are a lot more likely to look at recursion as a tool for iteration. Personally I struggled with recursion in the beginning. I just couldn’t wrap my head around it for a while. Now I find it really interesting and in some cases very useful. But I prefer not to use it for simple iteration. There is extra overhead involved with all that stack use and I’m still thinking in terms of minimizing memory from my early days when memory was expensive.
But getting back to the discussion I started on Facebook. We are often forced to use code examples that are not ideal coding practice. WE do that to make things clear and to demonstrate specific concepts in a sort of isolation that we might not normally use. We seem to do that a lot with recursion because the example that require recursion tend to be fairly complex. For example traversing trees is an application that recursion is particularly good at but trying to teach both trees and recursion at the same time can be complex. An other frequent example if the Towers of Hanoi which has a complexity of its own. The Fibonacci sequence? Probably better than some but you can still solve it without recursion.
We move on to the question of when should recursion be taught. With functional programming it has to be early. We procedural programming it doesn’t have to be taught early but people disagree on if it should be. I don’t teach it in my first course. Part of that is time – its a single semester course and I can’t fit everything in. Also I tend to think that recursion should be taught in conjunction with other CS concepts like stacks and context switching and memory usage. That is a big pill for a first semester course in high school.
Some might argue that this is all an argument for teaching a first course with a Functional language. I’m trying to make my mind up about that. I’m also wondering if the most important thing a first course does is cover all the key concepts beginners need for some definition of all the concepts beginners need OR is the most important thing for them to learn enough to want to learn more?
20 comments:
for (int i = 0; i <= n; i++) System.out.print(n);
Is a lot easier.
But it doesn't give the same answer
Unless you mean;
for (int i = 0; i <= n; i++) System.out.print(i);
or even easier;
10 print "0123456"
http://en.wikipedia.org/wiki/Tail_call
That's the reason why recursion in functional programming languages and several other imperative languages "Just Works" and don't use the stack.
I fixed the error in the sample code. Thanks for the catch Robo.
I am perfectly fine on this question IFF you included a second question:
1. What is the result when printNumber(6) is called?
2. What is the result when printNumber(6000000) is called? Explain the difference.
The answer to #2 is of course, "SYSTEM CRASH! STACK OVERFLOW" etc.
I woud argue that the issue isn't about right and wrong, but about understanding both aspects of the problem, as demonstrated by #2. A "good programmer" knows both methods (ie, recursion and loops) and uses both (wisely).
I think that problems with understanding basic recursion often are caused by misconceptions about scope, but understanding scope is pretty fundamental, and actually not that complicated, so it's probably good to learn it correctly early on, and then IMO basic recursion is just a good test for having understood scoping.
Maybe the problem is with introducing recursion via stacks? That is just an implementation detail of some (well, many ;-) compilers and interpreters and as such maybe simply isn't necessary to explain at that point? After all, you probably also don't explain, I dunno, dynamic linker trampolines? You just introduce how to call a "built-in function" without worrying how the system performs that function call.
Also, explaining such high-level concepts in terms of common implementation techniques seems to me to bear the risk of making people think too much in terms of those rather than at the abstract level. In the specific case of recursion, Scheme, for example, guarantees tail call optimization, so in tail-recursive code, the implementation probably won't even use a stack when executing the recursive call--however, scoping still works exactly as you would expect, of course.
When n is negative the two results are different.
try ackermann function.
You cant use loops on it since it is double recursion.
A(m,n) =
n+1 if m==0
A(m-1,1) if m > 0 && n == 0
A(m-1,A(m,n-1)) if m>0 and n>0
Says the person who writes "That don’t make it a good way" 8-)
I agree it is a silly question, however it checks understanding the concept. What would be a better question?
I appreciate the heads up on the don't doesn't typo. Thanks.
Ummm.... printing numbers from 0 to n is a stupid and unrealistic problem, REGARDLESS of whether you're using iteration or recursion. It's completely devoid of any practicality in any case (ref. Astrachan's Law), but as impractical code that potentially makes students understand a process it certainly has value. You could reverse the order of the print and the recursive call and ask the same question again - that gets at a very important question and insight for students.
But again, I think complaining about how it's a silly way to code something when it's not something people would actually code anyway (iteratively or recursively) doesn't make sense.
The problem isn't in the question -- the question simply asks you to "unfold" code, and in the real world, you are often going to be faced with debugging or maintaining other people's sub-optimal solutions.
The problem is far more subtle: within teaching, there's a tendency to deny reality, and claim that test questions aren't a model for teaching. They shouldn't be, that much is true, but the practical reality is that a teacher's first priority is almost always to get the students ready for the exam.
When the questions are at that basic a level, it can be assumed you're not going to have had enough time to work through the volume of examples needed to get an innate understanding of the pattern, so that leads into rote teaching...
My philosophy is: don't teach to use a hammer, unless the situation requires a hammer.
In CS terms: as you stated, recursion is really good in tree or graphs, and should be taught AFTER people are able to use trees and graphs.
In my opinion, and I don't want to start a flame war, the poor teaching or recursion is due to mathematician switching to CS but unable to change their ways. When I learned recursion, it was for a stupid (in term of CS usage) ways: teaching factorial. Honestly, who would do:
function facto(int n) {
if (n<1) {
return 1;
} else {
return facto(n-1) * n;
}
}
Well a mathematician would because in their world, expo is defines as:
/ 1 if n == 0
facto(n){
\ (n-1)! x n if n != 0
See the similarity? Or should I say, same thing, written differently? This is the problem: people still want to keep their religion that maths explain. Therefore, they just use CS as a different language to reproduce the world and they just reproduce what they know instead of thinking in the new ways.
"In CS terms: as you stated, recursion is really good in tree or graphs, and should be taught AFTER people are able to use trees and graphs. "
It's unrealistic to teach everything only in the context it's classically used. Students like simple examples of new concepts and this is a really lovely simple example of recursion.
Personally, I tend to favor teaching recursion along with the rest of the looping structures. I can see the argument for holding off, but honestly to my mind if you can understand that looping an index out of bounds is a bad thing, you can get why an infinite recursion will cause major blowuppage as well. You don't even have to get into stack architecture too heavy, really.
To me, recursion has always been one of those things that's like insurance: you usually don't need it, but when you do, you *really* do. It's a good thing to have under your belt and--more importantly--be able to understand. If you can demonstrate you understand the concept, even in a silly example such as this, then that's a good sigh you're learning to think algorithmically.
As to the example given, yeah, it's a corny example and no, you'd never use recursion for this in the real world. But as a bare-bones test of the concept, I think it works, and to be honest I can't think of a better one off the top of my head. Perhaps it would be meet to follow this up with a discussion question, like: "How would you implement this differently? Explain your reasons."
I see no problem with the question as posed.
In the real world, you'll encounter other people's code that is not necessarily best coding practice, yet you'll have to be able to read and understand what it does. The test question (as posed) is a perfectly reasonable example of this.
I'd offer one should not expect all test questions to be representative of good coding practice, unless of course the subject of the question is regarding good coding practice.. i.e. "What are the possible shortcomings of this programming technique.."
The anonymous poster who said difficulty understanding recursion is often related to scope is on to something. Then, there is a secondary effect of teaching loops first.
I) Students don't really understand how functions and parameters work after you teach them to use functions to break large problems up.
Most languages use call-by-value parameter passing. Students naively assume some combination of global names and call-by-name.
As we speak war story:
I just taught recursion before loops in our intro course, which uses C++ (don't ask --- it isn't my fault). 90% of the questions are things like: how can keep the original value of a variable if the function keeps changing it? This means that students don't understand procedure call, parameters, local variables, and call-by-value. When you talk to them, they really do understand simple recursive examples in terms of when functions are called and what they want to happen. (We're doing very simple problems involving drawing ASCII-art-type patterns.)
I'm hoping, and we'll see, that catching these misunderstandings now will have a big payoff later. If they're able to get programs to work without understanding how functions/parameters really work, then they're just being set up for trouble down the road (i.e., when we see examples with pointers and call by reference done C-style).
We shall see!
II) Down side to loops first.
If you believe, as I do, that every working programmer needs to understand both, then conventional loops first has a serious downside. It's easier to learn (see the above about not understanding functions). Recursion is harder to learn. Students, faced with a tool that is harder to learn will be put off. Couple this with the fact that almost all early recursion examples are easily solved with loops, and you have a situation in which student say to themselves (and out loud) that recursion is just a more complicated to do what they already know, and so they don't need to learn it. And they don't. Really, they have learned about functions! When they DO really need it, they will be hit with all the things they haven't learned so far AND have to deal with complex data structures.
I've taught recursion first and loops first before, though this is the first time I'm doing recursion first in the Tufts C++-based intro curriculum. Students really do learn recursive problem decomposition and coding strategies well ... if you force them to :-) And later in the curriculum, they pick up trees without a blink.
The primary purpose of an exam question is to test the students' understanding of a concept (or concepts), not to be an example of good code practice. You say it is 'good' for its main goal, and not 'good' in other ways that are not its goal. So it fails to do something well that it's not required to do well - that is not a critical issue - but still, the point should not be summarily dismissed. There is still the matter of quality, having good secondary attributes once the primary attributes are taken care of. That's a discussion worth having, too.
Without being offensive or accusatory, I hope I can ask some questions, to stimulate the topic. You pointed out a problem: do you have a solution? In particular, if it were your responsibility to compose a question to test the same understanding as is required to answer the given one, how would you write the question? In general, what can be done to improve the overall situation? Or, do you bring the issue up more for the ensuing conversation, to help find solutions? - Speculating without much grounds here, so please forgive me if I'm wrong: Perhaps part of what bugs you is that exposing student to poor code, without them recognizing it as poor code, is doing them a disservice. So - if there were a question on the exam testing "do you understand where recursion is appropriate?" immediately before this question testing "do you understand recursion, itself?", would it still be so objectionable?
The situation reminds me of Arrow's Impossibility Theorem. There is a set of policies: "a more complex structure is only appropriate where a less complex structure will not suffice or is cumbersome (usually meaning, in a larger problem)", "exams should test understanding of complex structures", "exams should have appropriate code", "exam questions to test a certain concept should not have problems much larger than necessary to test it", is a set of policies that individually are each desirable, but together cannot all be honoured all the time. I think "exams should have appropriate code" is the least important of all those policies, and should be the first one to be chucked out if they can't all be kept. Not that it should be wholly ignored, right from the start: where there is no conflict with the other policies, appropriate code should generally be used. But, that is really the lowest priority of the ones listed, and will be the first to be sacrificed.
"John Bokma said...
http://en.wikipedia.org/wiki/Tail_call
That's the reason why recursion in functional programming languages and several other imperative languages "Just Works" and don't use the stack."
Even so in this example, the recursion done is not a tail call,
A recursive program to compute Fibonnaci numbers is marginally shorter than an iterative program, but much less efficient. If you compute fib(n) as fib(n-1) + fib(n-2), you wind up computing fib(n-2) twice. This duplication of effort leads to a running time that increases exponentially.
Here are two examples that illustrate the power of recursion with arrays rather than trees.
1. Merge sort
To sort an array, divide it in half, recursively sort each half, and merge the results.
2. Permutations
To enumerate all permutations of a[1], ..., a[n], use a loop that interchanges a[1] with each a[i] and then recursively enumerates all permutations of a[2], ..., a[n].
Post a Comment