Slashdot Mirror
AP Test's Recursion Examples: An Exercise In Awkwardness
theodp writes "Yet another example of how AP exams are loaded with poor coding practices," quipped Alfred Thompson, referring to a recursive code example that prints the numbers 0 to 6, which was posted to the (closed) AP Computer Science Facebook group. "We are often forced to use code examples that are not ideal coding practice," Thompson notes. "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 examples that require recursion tend to be fairly complex." So, while asking students to use recursion instead of a loop to print '0123456' serves the purpose of teaching recursion, Thompson opines that it's also a poor example of code practice. "Someone raised on functional programming where recursion is a pretty standard way of doing looping might disagree of course," he adds. "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." So, do you tend to embrace or eschew recursion in your programming?
A legitimate use of recursion would probably be something a lot more complicated, and a lot harder to grasp, than a contrived use that teaches the concept in isolation. It's like teaching a kid long division using 6000 / 10, and disparaging the example saying, "yeah, but you would never use long division for that." Well, no shit, Sherlock. You're teaching mechanics. Application is for another lesson. Maybe even another class.
Depends on what you're doing. I found it helpful for dealing with trees. But counting 1 to 6? Nah...
Recursing a directory/folder structure would be a much better example of not only HOW to use recursion, but when and why it actually makes sense.
TFS asks "do you use recursion?". When it makes sense, such a directory or category tree. That is, when the problem is inherently recursive. It's also good to know that all recursive algorithms can be trivially converted to iterative versions with an explicit stack or queue. This is useful for something that could recourse deeply, like following links to spider the web.
I use recursion fairly often for traversing unconstrained trees. Though I'm lazy and never really looked if there was a better way to do it.
"Better" - maybe. Easier - not so much. Recursion is a good way to investigate an issue from a higher perspective w/o having to deal with implementation details, just to get something working. I use it all the time for rapid-prototyping, problem evaluation and double-checking my non-recursive solutions.
It must have been something you assimilated. . . .
I use recursion in VHDL quite a lot, since functions in that language are completely pure, it is often the right thing to do.
Also when creating hardware there is a step called elaboration, where function are executed (optimised away) before a hardware netlist is created.
I make a bold claim: all modern compilers have tail recursion optimization implemented
Wow ... that felt good!
Cost free eBook I read (by iBook/Kobo/Amazon/ObookO/Gutenberg etc.): "The Green Odyssey" by Philip Jose Farmer.
OutOfMemoryError
In a world where most programmers don't have a clue why they chose a list vs. an array vs. a tree for anything, this is actually an excellent question to test students with.
This is obviously not an optimal solution to the problem it solves, but it is in fact a fairly compact example that can be used to test whether a student understands recursion and can follow code.
The question isn't whether there is bad code on the exam. This was a great question.
The question is, is there also a question relating to excessive or unbound recursion and what will happen if the number is too big.
What about Big-O notation and algorithmic complexity.
I had to implement a compiler and virtual machine last week because I couldn't find anyone else to do it that was available. This is because not enough people understand topics like recursion.
The teacher who posted the article made it very clear that his competence is limited and he himself is quite slow witted by stating the he found recursion hard to understand at first. Why is this even on Slashdot?
I was in an economics class with a good friend. The class was given an assignment in which they had to calculate some nonsense. The teacher said that any language code or pseudocode would be fine.
The friend and I were the only engineers in the class and apparently the only ones to use recursion to get to the answer. He used head recursion and I used tail recursion. Everyone else apparently solved it with itterative loops.
The TA knew my friend and I knew each other and threatened to report us for cheating. I told her to go ahead and show our code to the prof or even a CS prof. The logic that my friend and I were so different in the code that the fact that we both used recursion was the only similarity.
We hadn't cheated and kinda thought it was funny that it looked like we did.
Now, I wouldn't be surprised if we got our code scanned into some database and a computer said we cheated and we would have no recourse.
Help! I'm a slashdot refugee.
It's a fucking technology, not a moral decision. You use each when it's appropriate.
Recursion is a tool best used when (a) the design is made more clear by its use and (b) you can afford the stack overflow and/or issues in languages without proper tail call support. For instance, tree search can often be coded much more understandably and with fewer errors with a recursive solution. The same with factorial and other functions defined recursively. Others, not so much - want to dick about with an array? Use an iterative construct, preferably a high-level one, like map/foreach/etc.
I've not actually used recursion in a long time, mainly because most language designers are too fucking lazy these days to put proper tail recursion into their language designs, the higher level functional iteration constructs are becoming available in the languages I'm using, and data's becoming too big.
That is all.
I'm pretty sure that no student taking that test would perceive that question as being an example of how to write a program. The AP Computer Science exam takes a perverse delight in double checking that every student can read deliberately confusing code. The posted question is just a mild example. I feel that criticisms of questions of that type should be leveled at exactly what's being tested - reading rather than creating code. I know I personally minded that a large number of such questions on the test when I took the exam were fairly spacial in nature - like predicting the bitmap output of a function.
it's all in the implementation.
That's what I'm saying though, it's not all in the implementation, tail call recursion relies pretty heavily on the code being set up (and kept up) properly so that it is possible.
Even if the compiler will always tail-optimize calls (lots of languages it will try, but may not) you can always change code such that a method/function that was tail call optimized suddenly cannot be, and the way ALL compilers are right now you will not know such a potentially crucial change has been made...
Which will not matter in any test scenarios set up, but as soon as it hits the real world it encounters the thing with a million items to iterate over, or possibly a directory structure unimaginable deep, a tree horribly wide... and the program explodes.
Mind you, I *like* recursion, but it is a risky thing to introduce unless you are really, really sure what will be fed into it and how the recursive function will evolve, forever...
Speaking of forever:
Of course, in someplace like Haskell one can just use the "forever" function which loops some action forever rather than implementing an explicit tail-call loop
Um, is that not sneaking in a normal iterative loop with a conditional check that's always true? What would be the difference from the code that generates and "while (1 == 1)"?
"There is more worth loving than we have strength to love." - Brian Jay Stanley
And on the LLVM mailing list this recently, there has been talk of translating recursive code into a loop or stack based state machine in order to allow vectorisation, unrolling, common sub expression elimination, and all of the other optimisations from their bag of tricks.
09F91102 no, 455FE104 nope, F190A1E8 uh-uh, 7A5F8A09 that's not it, C87294CE no. Ah! 452F6E403CDF10714E41DFAA257D313F.
That's the real world and real jobs in most cases. Unless you are doing something really high end most jobs are boring straightforward imperative programming. Something like "Scrape a web form on click, put objects into a container, contact the database via a library, do a transaction, get a response, manipulate the response, present the response to the user. Most programmers do not do parallel processing, high end graphics, tool smithing, or predictive analytics.
Most programmers do not use functional languages either.
putting the 'B' in LGBTQ+
Which is not the example in TFS. It says recurseivePrint(n-1); print(n);, which does NOT build up the solution from the simple case, but swaps a for loop for a loop up and down the stack.
Yes, it is a test question. Yes, if you understand recursion, you can answer the question. However, it is poor code, because the recursion is not tail-recursive; anyone who uses recursion with unknown values ('n' in this case) will write a tail-recursive function.
Since it's a totally artificial question, there is no reason that they couldn't have used a tail-recursive function. Lots of students won't know the difference, but crappy code like this is a stumbling block exactly for the students who really do understand what's going on.
Enjoy life! This is not a dress rehearsal.
> You never know how deep a directory goes.
On Windows, no more than 130. MAX_PATH is 260, so if directory names are single characters you can have up to 130 of a\b\c\
On Linux, MAX_PATH is typically 4096, so directories can be 2048 deep.
If you're using 16 bytes per level, you know your program won't use more than 16X2048 = 32KB. A maximum 32KB of RAM usage is acceptable on any system running any of the major operating systems.
It wouldn't hurt to check PATH_MAX just to be sure, or put in your own recursion limit of 2048.
In the real world it's best to write for a "lowish" common denominator because future staffing is unknown, but best to know HOW to figure out "clever" code if you encounter it. Thus, the best habits for writing code tend to conflict with learning to read any code you may encounter.
The solution is to point out early that writing code is similar to writing documentation: clarity to other readers matters above parsimony etc. Put that on the test.
Table-ized A.I.
I mean, this guy really seems not to get that the excercise was not meant to demonstrate how to print 123456, but that printing 123456, as opposed to e.g. 654321 is a tool to demonstrate/show the order of the execution of command in a self-recursive function.
I mean, i have seen bad coding practices in courses (nervous handling of null pointers, and strong binding OOP comes to my mind), but this question has nothing to do with coding, but is purely the shortes way to test is the student understands what happens if the print comes after the call of the self recursive function.
For example, recursion is often be appropriate when working through some sort of data structure.
Yes, traversing or pretty-printing a Lua table (which may contain tables itself) is commonly needed and should be easy enough for a beginners’ class
Iff you use Lua of course.
I’m old enough to remember 16K of memory being described as “whopping”
They're scoring students on their ability to interpret the code correctly, which has nothing to do with whether recursion is the right approach. This is the sort of thing people will see in job interviews: code that you'll never actually see in the real world, with the question what does this do?
--I'm so big, my sig has its own sig.
-- See?
It's not telling students to use recursion to output that number sequence, it's asking students to read and understand a bit of code that does it. Being able to read and understand other people's badly written code is absolutely essential in todays software industry...