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?

Comments

What do you expect?

[halivar]

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.

Re:What do you expect?

[vux984]

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.

But the mechanics of long division in that example are reduced to trivial busywork. That not a complicated enough example to even really see the mechanics properly.

It'd be like using Newton's method on a sample problem that converges to an absolute final answer after a single iteration, or teaching someone how to calculate the area of a trapezoid and using a square as the example problem to solve. Sure the formula works on a square but its not really instructive.

Application is for another lesson. Maybe even another class.

I'd argue that the solution to a problem is a lot easier to understand if you're given a context where the solution is needed FIRST. Starting with a degenerate problem that reduces to a trivial application serves to obscure the 'point' of the solution method.

Re:What do you expect?

[Daniel_Staal]

I'd argue that the solution to a problem is a lot easier to understand if you're given a context where the solution is needed FIRST. Starting with a degenerate problem that reduces to a trivial application serves to obscure the 'point' of the solution method.

This isn't the teaching materials. This is a test question. Yes, the teacher should teach the concept with a better example and explain it fully - but the question is enough to show if the student understands the concept and can apply it correctly. It's also quick to explain and short to answer, both good things for a test question.

This isn't the starting point - this is an ending point. (The end of the class.) The question is enough for that.

Re:What do you expect?

[Anonymous Coward]

Since all recursion can be implemented as iteration, there is really not much legitimate examples.

A typical example is something stupid, like Fibbonaci sequence.

    F(n) = F(n-2) + F(n-1)

except that using recursion here is really bad. Iteration with lookup table saves a lot of time - problem becomes O(n) in time and space. In functional programming, where all functions are pure, this becomes trivial for compiler for "fix", but for procedural language like python, this is a disaster. Both space and time blow up and you can't even calculate n=10000.

An example where recursion is OK would be threading model on some trivially parallel program. But that's about it. I have yet to see another reason to use recursion.

Re:What do you expect?

[sjames]

Not really. Factorial practically begs for a recursive implementation and it's very simple.

Then there's fibonacci, qsort, etc.

Re:What do you expect?

[Anonymous Coward]

Problem is the current generation is not aware of the machine architecture under the hood. If you have an embedded system that does not have a spare register for couinting but has built-ins for jumps, recursion is faster than iteration. If on the other hand you have built-ins for counting iterations, with a JPNZ, loops are more efficient.

The problem isn't the example. It's the lack of machine context - not even a language is the true barrier.

Re:What do you expect?

[ShanghaiBill]

This isn't the teaching materials. This is a test question.

Exactly. This question is not asking for an implementation. It is just testing whether recursion is understood well enough to predict the result. This is a good question. Someone with a basic understanding of syntax and recursion would be able to answer the question correctly. Someone without that understanding would not.

Complaining that recursion was used instead of iteration is just silly, since that is not what is being tested. A proper implementation would use neither. If I was tasked with writing a program to list the digits from zero to six, I would write this:

#!/bin/sh
echo "0123456"

Re:What do you expect?

[gnasher719]

Yeah, right. Fibonacci wants a recursive implementation. Which has exponential time complexity instead of linear.

Re:What do you expect?

[NoOneInParticular]

If you want to really hurt your head, try implementing Ackermann's function using iteration. For a less theoretical example, try traversing a tree. It can be done using a stack and iteration, but the result is much more messy.

Re:What do you expect?

[Anonymous Coward]

let fib n = fib_aux n 0 1 where fib_aux n a b | n >= 1 = fib_aux (n-1) b (a+b) | otherwise = b

There you go, linear time, constant space.

And if you'd actually need Fibonaccis, you'd either use a lookup table for limited precision (~50 entries for 32 bit, ~100 for 64) or something like unfolded version of matrix exponentiation for arbitrary precision.

Re:What do you expect?

[vux984]

If you have an embedded system that does not have a spare register for couinting but has built-ins for jumps, recursion is faster than iteration. If on the other hand you have built-ins for counting iterations, with a JPNZ, loops are more efficient.

That's really more of a compiler optimization issue.

Re:What do you expect?

[vux984]

This isn't the teaching materials. This is a test question.

You are addressing the original article, and you are right on a test its a perfectly fine question. I agree with your argument.

My post was really just addressing the post I responded too, rather than the original article though, and that was in the context of teaching rather than testing.

Re:What do you expect?

[Greyfox]

Building or search a binary tree with recursion is not difficult to code or understand and is something you might legitimately do at some point in a programming career. You can say bad examples are just for teaching materials, but if all students are ever exposed to are bad examples, it's going to be a lot harder for them become good programmers.

Likewise, whenever anyone brings up design patterns, the go-to pattern is inevitably singleton. Want to find a good design patterns book? Look in the index under "S". If Singleton isn't mentioned, it's probably a good design patterns book. If anyone wants to argue this point because you think Singleton is a good design pattern, you're a bad programmer and should consider getting a MBA. Again, it's goddamn trivial to build a factory/listener pattern to build objects from a data file. A factory or listener will generally make it through a code review. A singleton never will. Even if it's the one good example of a time when a singleton might actually be a good fit for something, the code review board will shoot it down.

Re: What do you expect?

[Anonymous Coward]

You use a singleton design pattern when you have to, usually. For example, in a python script I wrote, I had a circular import and worked around it by moving some logic (including imports) into a singleton object. I could have avoided this but the code would had been uglier. Also, the unity game engine requires singleton objects for things like game management logic.

Re:What do you expect?

[west]

Ah, Ackermann's function, the trusted test of "Do the students understand recursion?" of 1st year university courses everywhere.

Re:What do you expect?

[Anonymous Coward]

Well said, couldn't agree more

Re:What do you expect?

[fermion]

I looked at the AP exam a while back. I found it to be, like so many AP exams,too much trivia and minutia for my tastes. I am all for a clever well written exam, such exams can be a wonderful teaching tool, but it can be taken to extreme. Plus we are making the same mistake we made with pascal, choosing a language for pedagogy rather than practical application.

I myself was taught FORTRAN when I was 14 in a one year high school course. The first grading period we solved problems, wrote algorithms, learned the vagaries of pre-pc computing, and learned to behave. Then we spent the rest of year learning FORTRAN, complete with coding sheets I picked up at the university bookstore.

This included recursion, and we used the only reasonable example one can give a high school student. The Fibonacci series. I assume that everyone has coded this by the time they 18. Like the swap function.

It is not so much that there are not simple and meaningful things kids can code to learn the proper technique. It is just that most of these are already part of the library, so kids are going to balk or copy or just not do it. For instance it would be great for kids to learn linear algebra by coding it, but how we can justify it when the row reduction is already part of most libraries.

Here is a little bit of AP trivia. In AP Physics they want kids to collect data and practice a least squares fit by hand. They note that computers do this now, but it is good experience. It is like AP CS. The kids are not being trained in basics, so they really don't know how anything really works. CS should be a craft, physics should be a process, but it is not always being taught that way.

Re:What do you expect?

[Anonymous Coward]

Compilers are an accelerator - not a crutch. But they're used aa a crutch these days. There is very little analysis taught today and whether memory use is linear, geometric or static, and similarly how a particular algorithm affects the stack.

If don't know what's under the hood, you will always be relegated to not understanding the first principles that dictated the need for particular algorithm. Those that refuse to stand on the shoulders of giants are destined to repeat the mistakes of yesterday.

It is true that tail-recursion can be made iterative, but there is a when and where to do so and it has less to do with instructions and more to do with the platform on which it will run.

Oh - I forgot - everyone programs in Java now and so it doesn't matter. Except when I've re-tailored an algorithm for what's under the hood and got better performance from knowing how the machine would implement it on the architecture.

Programming is a balance between the architecture, the hardware and the software. Not just one-size-fits-all. That's why we get these questions anyway - the commonly held belief is that one-size-fits-all.

Eve Duff's device CAN still cause slower code when done automatically by the compiler.

Re:What do you expect?

[XxtraLarGe]

You can say bad examples are just for teaching materials, but if all students are ever exposed to are bad examples, it's going to be a lot harder for them become good programmers.

Sometimes you start out with a trivial example so students can grasp the concept more quickly, then you increase complexity.

Re:What do you expect?

[Baloroth]

This included recursion, and we used the only reasonable example one can give a high school student. The Fibonacci series. I assume that everyone has coded this by the time they 18.

Which is why it's a terrible horrible no good choice for a test question. If they've already seen it, they know what it does, so you're not testing them to see if they understand the code conceptually, you're testing to see if they've seen a Fibonacci generator before.

Re:What do you expect?

[jc42]

Not really. Factorial practically begs for a recursive implementation and it's very simple.

Then there's fibonacci, qsort, etc.

Well, they can be done recursively, but their usual definitions imply the simpler iterative approach. Using them leads to the problem that you often see, not just with young students, but even with experienced "professional" programmers: They learn that recursion is just a complex, obscure way to do iteration.

If you actually want to get across why recursion is important, you really should use examples in which recursion gives a simpler solution than iteration. One of my favorites, partly because people are usually surprised to discover that it's actually best done recursively, is a task that software does a lot: Given a binary number, generate the decimal representation of the number. The natural (iterative) divide by 10 and output the remainder of each step gives the digits in reverse order. This is fine if you're putting the result in a fixed-width field that you know is wide enough, but it's not fine if you're generating ordinary text with just one space before and after the number or if you don't know how many digits the number will have. To generate the number iteratively in the order we usually say or write the digits requires two passes, one to count the digits, and the other to write them. Or you can generate the digits in little-endian order into a large buffer, then use a second iteration through that buffer to output the digits in big-endian order.

But a faster, more elegant way is to write it recursively, with a routine that saves its remainder digit while it passes the quotient to a recursive call of itself. The bottom-level call finds it has a 1-digit number so it doesn't make the recursive call, but simply outputs its digit, and returns to the caller, which writes the 2nd digit, and so on. Students that understand this now know that recursion can sometimes simplify some (but not all) problems.

There are number of other simple problems that are best solved recursively, but this page's margin is to small to hold the list. ;-)

Re:What do you expect?

[Greyfox]

It's recursion. Therefore fundamentally incomprehensible! Heh heh. So you can muddy the water even more with a useless example, or you can demonstrate how it can make certain tasks significantly easier... right up until you have to debug a problem in that code.

For what it's worth, the kids in the AP class at the high school I attended it upstate New York back in the late '80's were doing recursive descent parsers in Pascal. I don't think three decades of being exposed to computers have made the kids any less able to understand that sort of thing, but somehow we seem to have become less able to teach it.

Re:What do you expect?

[ultranova]

But a faster, more elegant way is to write it recursively, with a routine that saves its remainder digit while it passes the quotient to a recursive call of itself. The bottom-level call finds it has a 1-digit number so it doesn't make the recursive call, but simply outputs its digit, and returns to the caller, which writes the 2nd digit, and so on. Students that understand this now know that recursion can sometimes simplify some (but not all) problems.

The problem is, that algorithm can't be tail-call optimized, so it's gonna run out of stack space and crash on reasonable-sized inputs. Which is why recursion should usually be avoided: it's a bad fit for common imperative programming languages, which are almost all stack-based - and don't necessarily guarantee tail-call optimization even in cases where it is possible, for that matter.

Re:What do you expect?

[brausch]

I don't think recursion was part of the FORTRAN standard until pretty recently. There were some specific implementations of FORTRAN compilers that supported it as an option (Data General in the mid-80s for example), but DEC (VAX), CDC, and Cray did not and they were the big three in the scientific/engineering world. The ANSI standards for FORTRAN 66 or FORTRAN 77 did not have recursion.

Re:What do you expect?

[Anonymous Coward]

Recursion IS simple though, most of the time when it's taught the examples are so convoluted that it leaves everyone including the professor scratching their heads. In practice if one thinks it through logically step by step it is usually no tougher than writing a basic for-loop would be. Simple examples are ideal so as not to scare people away from it. How many coders out there struggle with writing recursion CLEANLY? If the principles are taught in order it shouldn't be nearly as much of a problem as it has become.

Re:What do you expect?

[linuxrocks123]

My best attempt to translate that from what I think is Haskell to an imperative pseudocode, in case anyone is curious what's going on:

define fib_aux(int n, int a, int b) returning int:
{
    if(n>=1)
        return fib_aux(n-1,b,a+b)
    else
        return b
}

define fib(int n) returning int:
{
    return fib(n,0,1)
}

If you're having trouble seeing why this works, start with noting that you're basically using b as an accumulator, and go from there.

It's linear time because you're only doing one recursive call per method and you're decreasing n by one with each recursive call.  It's only constant space if you have a smart compiler that can get rid of the stack frames that would be generated in an unoptimized implementation.  The needed optimization is called tail recursion.  Tail recursion is basically a cheat where you count on the compiler to optimize away your recursion into an iterative loop when your recursive call is the final instruction of the function; the optimization logic to do that is not hard.  Python is a notable language that does NOT do this optimization.

Re:What do you expect?

[grep -v '.*' *]

If I was tasked with writing a program to list the digits from zero to six, I would write this:

Sorry, that's an F. You've got a horizontal list there, the end-user wanted a normal-style vertical list instead. Can't you interpret standard specifications correctly???

Off to the short bus!

Re:What do you expect?

[Anonymous Coward]

Your "reasonable" doesn't sound too reasonable. Common 32 and 64 bit ints are only 9 or 20 decimal digits long, only most limited of embedded CPUs will run out of stack computing that.

Not everyone requires arbitrary precision ints.

Re:What do you expect?

[Eunuchswear]

If you want to traverse a tree without recursion you want to check out Morris traversal -- doesn't need a stack.

Re:What do you expect?

[Simon Brooke]

That's a particularly stupid response, even for Slashdot. Since all iteration can be implemented as recursion, why ever use iteration?

Because some problems are more clearly expressed as iteration and some as recursion.

Try, for example, to describe in normal everyday language a route planning algorithm using iteration. Here it is using recursion:

1. Go from here to a junction.
2. Am I at my destination? If so, then stop.
3. Am I closer to my destination than I was at the previous junction? If so, then recurse.
4. Otherwise backtrack to the previous junction and choose the next branch from there.

Re:What do you expect?

[Anonymous Coward]

If your trivial example is of the "recursion as a more complicated way of writing a loop" kind, you'll have lost the interest of three quarters of the students before you have increased the complexity to useful examples.

Re:What do you expect?

[Anonymous Coward]

Fibonacci is an obviously linear problem. Turning it into recursion is an exercise in making simple things complicated. Most of those who learn that lesson will avoid recursion even in cases where it's the only simple solution.

Re:What do you expect?

[Anonymous Coward]

O(log n ) version: compute the nearest integer to Phi^n. where Phi = (1+sqrt(5))(2)

Re:What do you expect?

[ultranova]

Your "reasonable" doesn't sound too reasonable. Common 32 and 64 bit ints are only 9 or 20 decimal digits long, only most limited of embedded CPUs will run out of stack computing that.

But that also means you can use a precalculated table to look up the number of digits, making recursion pointless. Also, how much stack space has whatever function called this one used?

Not everyone requires arbitrary precision ints.

Which is a good thing since they don't exist ;). And besides, in the real world the correct solution for printing the digits of an integer is to use printf. This entire excersize was purely academic in the first place.

Re:What do you expect?

[Anonymous Coward]

Recursion is a stack and iteration.

Re:What do you expect?

[jeremyp]

To be fair, the example gives the same output as would be seen in the example from TFA.

Re:What do you expect?

[JesseMcDonald]

It's recursion. Therefore fundamentally incomprehensible!

I realize you were joking, but there isn't really anything conceptually difficult about recursion. It just means that part of the program refers back to itself. Whenever you have self-similarity in the program's control flow, including the trivial case of repetition, you have recursion.

I think part of the problem is that most students are introduced to specialized loop keywords and "the" stack (a mere implementation detail) first, and only exposed to explicit recursion later as an "advanced" concept. Recursion should come first. Really, which is easier to understand:

void iterative(int n) {
..while (n > 0) {
....print(n);
....n = n - 1;
..}
}

void recursive(int n) {
..if (n > 0) {
....print(n);
....recursive(n - 1);
..}
}

From a modern compiler's point of view (with support for tail-call optimization) these examples are exactly equivalent, but the recursive version doesn't require an understanding of mutation, which is counter-intuitive for many beginners, and makes the control flow explicit where the "while" statement hides the control flow behind a special keyword.

Re:What do you expect?

[CauseBy]

It seems like your third step begs your whole algorithm. How can you know how close you are to the destination if you haven't calculated a minimum route to the destination?

Still, I understand your point, which is valid. Your algorithm is simplified for explanatory purposes but fully formed the example would be fine.

Re:What do you expect?

[Anonymous Coward]

Um, not quite. Formula and proof.

But yes, nearest integer is important.

Re:What do you expect?

[StikyPad]

"A legitimate use of recursion would probably be something a lot more complicated, and a lot harder to grasp"

Not really. Traversing a binary tree is the textbook example of the appropriate use of recursion. The concept is no more difficult to grasp than recursion itself, so not terribly complicated.

There are simpler, though less practical, appropriate examples as well, like factorials or fibonacci sequences. They're doable with for loops, but more elegant with recursion.

Re:What do you expect?

[Anonymous Coward]

You're pissing in the wind there. He clearly doesn't understand context, or he wouldn't have taken your post out of context, so describing the context to him is silly.

Re:What do you expect?

[Anonymous Coward]

Your post is ridiculously underrated. Dear people everywhere who keep talking about hardware-level stuff that nobody knows anymore - you're clueless. Recursion is nothing but pretending you have no stack while you iterate. Just because your code isn't explicitly saving the mutative doesn't mean it isn't there.

Re:What do you expect?

[linuxrocks123]

If anyone wants to argue this point because you think Singleton is a good design pattern, you're a bad programmer and should consider getting a MBA.

That's not a very good argument.

Even if it's the one good example of a time when a singleton might actually be a good fit for something, the code review board will shoot it down.

Where do you work where you have an entire board dedicated to code review?! How do you get anything done!?

The only places where that much red tape is justified is with pacemakers, airplanes, manned space flight, and anything with the word "nuclear" in it. And maybe a few other cases, but you get the idea.

Re:What do you expect?

[WorBlux]

Yep the unoptimized version is O(Fib(n)) in time and space (yes it's really that bad). Recursive data structures cry out for recursive algorightms. And in general its better suited to functional programing as you arne't really concerned with state.

Re:What do you expect?

[WorBlux]

And there's a reason we don't code in assembly any more. Abstracting away irrelavent details lets you focus more on the things that matter.

Re:What do you expect?

[WorBlux]

Exercise 1.19 asks us to complete a procedure for computing Fibonacci numbers in a logarithmic number of steps. The following code is given:
http://www.billthelizard.com/2...

Re: What do you expect?

[countach]

by the same token Since all iteration can be implemented as recursion, there is really not much legitimate examples of iteration.

Re:What do you expect?

[demonrob]

"Can't you interpret standard specifications correctly???"
where are these mysterious specifications?

Recursion is best used

[Anonymous Coward]

if you can solve a small part of the problem, given that the rest has already been solved the same way.

Re:Recursion is best used

[RightwingNutjob]

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.

Never used recursion

[ccandreva]

I don't think I've ever user recursion in my professional career. Sure, if I ever need to code a BNF grammar I might, but it's just never come up in the real world.

Re:Never used recursion

[Snotnose]

Most of my work is in either embedded systems or Linux device drivers. In both cases recursion is a Really Bad Thing (tm) if you can't promise not to wipe out your stack.

Re:Never used recursion

[Drethon]

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.

Re:Never used recursion

[dfghjk]

It's ALWAYS a Really Bad Thing "if you can't promise not to wipe out your stack." It's just fine otherwise even for embedded and device drivers as the environment is irrelevant to the issue.

Re:Never used recursion

[Anonymous Coward]

Trivial use case: A Mailing list contains either people or other mailing lists
Print the list of all people who will get a mail sent to the list

Re:Never used recursion

[Howitzer86]

Depends on what you're doing. I found it helpful for dealing with trees. But counting 1 to 6? Nah...

Re:Never used recursion

[jdeisenberg]

Yes, I find recursion useful when I have to climb through the DOM for an XML or HTML document.

Re:Never used recursion

[fahrbot-bot]

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.

Re:Never used recursion

[Anonymous Coward]

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.

Re:Never used recursion

[frisket]

I was raised on FORTRAN, but nowadays the kind of work I do (XML) means I use XSLT almost exclusively, so recursion has become natural. Except that XPath2 introduced loops...

Re:Never used recursion

[angel'o'sphere]

I make a bold claim: all modern compilers have tail recursion optimization implemented

Wow ... that felt good!

Re:Never used recursion

[Anonymous Coward]

yeah me too, never used recursion. in fact on production systems and embedded systems, I never use any algorithm that is potentially "unbounded". that was hammered in to us by comp sci profs. really don't need to blow the stack for no good reason!!

(true confession, I use recursion in languages that support it properly through tail call optimization.)

same thing with tree structures and algorithms. recently had an interview question regarding designing a class to support a curious 3-trie. well first off I have not ever programmed professionally any tree classes or libraries in 30 years - always use something already written, known, proven, optimized, tested, etc.

second I wouldn't use memory structs for something like that, I would use an adjacency matrix. much more compact, support many more access and sorting methods, etc. ensuing argument with "Director of Algorithms" convinced me not to work there. She didn't understand it. She asked for an optimization for sorting, what I showed her was better (~33% faster) than what her answer was, she didn't get it and got mad. oh well.

Re:Never used recursion

[arth1]

Most of my work is in either embedded systems or Linux device drivers. In both cases recursion is a Really Bad Thing (tm) if you can't promise not to wipe out your stack.

That's on the high-level side of "embedded". When your code is on PROMs, you generally want to favor saving program space over data space.

And not all recursive programming relies on stack either. In low-level programming, you seldom call your recursive function as a self-calling subroutine you have to return through all the layers to get back out of, but one that calls itself using a hard jump. The return will thus always return you to the original caller. Recursive functions then become more like iterators in high level programming, but still being very much recursive at heart.

Re:Never used recursion

[SuricouRaven]

Every time you search a filesystem, it's probably recursion underneath.

There's a reason filesystems have directory nesting limits.

Re:Never used recursion

[AuMatar]

Never had to walk a tree? Recursion is usually the best solution, unless you're just walking down 1 branch. It's not a frequently used technique, but it's definitely used.

Re:Never used recursion

[complete loony]

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.

Re:Never used recursion

[Anonymous Coward]

> much more compact
Depends on the type of graph.

Re:Never used recursion

[Anonymous Coward]

If your recursive function blows the stack in usermode, at worst it crashes your process. If it happens in an embedded device or a driver, it crashes the whole device/computer.

The problem isn't recursion (nothing wrong with a function calling itself) -- the problem is unbounded recursion. A merge sort is always logarithmic in the number of stack frames it uses, so even a 4G element list will only require 32. If your QuickSort routine only takes 32 stack frames to sort a 4G element list, that's great, but if its worst case is 4G stack frames, that's bad.

dom

Re:Never used recursion

[complete loony]

Write simple code and let the compiler find a faster way to run it. It's a problem that is being actively worked on.

Re:Never used recursion

[plopez]

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.

Re:Never used recursion

[Anonymous Coward]

Then you're not a responsible programmer! I use recursion in lots of code; one example: A strategy for dynamically managing queues. It's a lot easier with recursion than with looping, so you're losing out on a lot of productivity.

Re:Never used recursion

[Anonymous Coward]

Well that would be all fine and good, except the cited example can't use tail recursion. It does the recursion first, and then the print.

Re:Never used recursion

[west]

Is this in fact (reasonably) true? I've shied away from tail recursion, but I'd be pleased to find out that that is no longer necessary.

Re:Never used recursion

[angel'o'sphere]

I don't agree fully with the post but:
http://c2.com/cgi/wiki?TailRec... gcc does it, LLVM does it. But you certainly can find an obscure not gcc based compiler for a niche processor, OS, that not does it.

Re:Never used recursion

[Drethon]

OK now that is cool

Re:Never used recursion

[Eythian]

Last I heard (quite some years ago) the JVM didn't do it by default, as it was considered more important to keep stack traces intact. This might have changed now.

Re:Never used recursion

[readin]

I don't use it often, but when I do it usually doesn't feel like recursion because it recursive step works on a different object. I recall a need to model a network and a coworker trying to use some strange tool and getting very frustrated because it wouldn't do recursion. I whipped up a network model in Java in a few minutes. He asked me if I used recursion and I said "no". I apologized the next day because I realized had in fact used recursion, but hadn't realized it because even though the code I was calling was the same I was calling it on a different object (a different node in the network). In my mind each object had it's own instance of the code so instead of the flow looping back into the top of my method it was entering code on a different object.

It was kind of neat when I realized that. It made recursion seem a lot simpler than it had before.

Re:Never used recursion

[readin]

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.

I would love to escape that kind of career.

Re:Never used recursion

[Anonymous Coward]

Depends on how the tree is structured. If it includes back pointers, recursion isn't needed. The stack only holds information on where you came from - but if that is embedded in the tree, then you don't need recursion.

Did that once for a B-tree implementation due to having a limited stack.

Re:Never used recursion

[The Wild Norseman]

I would love to escape that kind of career.

I'm not really a programmer, but maybe this'll help?

career{that kind} ^[ ^D

Re:Never used recursion

[Anonymous Coward]

Last I heard (quite some years ago) the JVM didn't do it by default, as it was considered more important to keep 25 page long stack traces intact.

FTFY :-)

Honestly, when you get the stack-trace from an unbounded recursion, it'd be just wonderful if it said "<6000 more lines like this>" ...

Re:Never used recursion

[serviscope_minor]

When your code is on PROMs, you generally want to favor saving program space over data space.

I wouldn't say usually. When you have 128k of flash and 2k of ram, the ram looks quite pecious. Even more so when you have 1k of flash, 64 bytes of free ram and a function call stack that only goes (I can't reacall off hand...4?) deep, e.g. PIC12F675.

Re:Never used recursion

[Anonymous Coward]

No, they don't, or at least not in all cases (it gets complicated when you have to handle, e.g., C++ destructors). And even if they do, it's not going to be turned on for debug builds.

Relying on your compiler to optimise something that's not in the language specification (i.e. tail cail optimisation unless you're writing Scheme or something) is foolish.

Re:Never used recursion

[dpidcoe]

I took a programming class in clojure last semester and I remember some oddities due to this. Mainly that clojure has a function called (recur ) that's used to recursivly call the function that uses it. It was necessary to use so that the clojure compiler could optimize it into a loop before the JVM got its hands on the thing.

Re:Never used recursion

[Anonymous Coward]

And there are some programmers who've never used a do/while loop -- recursion is a tool, use it when it makes sense.

Re:Never used recursion

[david_thornley]

I once had to write a modified heapsort, and so wrote a heapsort. It's easy to do with a recursive "heapify" function (looks at the two lower elements in the heap, grabs the greater one, and does the same for that element). It's not difficult iteratively, but I found it not quite as clear. Since the number of calls is about log2 n, n being the number of elements in the heap, there's no likelihood of smashing the stack on any modern general-purpose computer.

Re:Never used recursion

[Tablizer]

Back in my xBase/dBASE days, I sometimes used an alternative to recursion whereby one takes inventory of each branch, and the links and/or contents are put into one big table. A flag is then set for nodes already processed.

It has the advantage that one can gather the basic info first before involved processing. E.i. "inventory". One can also stop processing and restart.

Pseudo-code:

rows = query(select from nodes where processed=False)
// Order clause can be added to tune priority
if rows.count() == 0 {return} //done
for row = each(rows) {
  if row.type = BRANCH {
    processBranch(row)
  } else { // LEAF
    processLeaf(row)
  }
}

A branch is set to "processed" (=True) when all its immediate children are added to the processing list. Sub-branches are taken care of on subsequent loops.

Tablin' was lots of fun because xBase made it easy. The good ol' days.

Re:Never used recursion

[WorBlux]

sounds like tail call elimination to me.

Most programmers can't handle recursion

[Anonymous Coward]

I recommend avoiding it where possible. The average programmer* has long forgotten what little they ever learned about recursion and don't encounter it in their daily work. Using it is, therefore, guaranteed to cause problems for them when attempting to maintain code that contains it. Beyond that, the ones who are clever enough to vaguely remember something about how to use recursion will often either use it where better methods are possible or forget to put in safeguards to prevent overflowing the stack.

* Sturgeon's Law comes distinctly to mind here.

Re:Most programmers can't handle recursion

[Anonymous Coward]

Most programmers can't safely be given the task of using a buffer, with or without recursion. Buffer use often ruins the stack. Should we avoid using buffers? We must teach both buffers and recursion using real world examples and stress the importance of guarding the stack.

Re:Most programmers can't handle recursion

[Anonymous Coward]

>Should we avoid using buffers?

The average programmer is already not using buffers, at least in the sense you mean. The most commonly used languages have mandatory bounds checking implicit in their array semantics to protect average programmers from themselves.

It's an essential skill for the professional

[Anonymous Coward]

Reading and modifying other people's awkward code.

Tests aren't about good practice? Say it isn't so.

[Anonymous Coward]

Horrifyingly, math tests still ask students to do long division when in the real world it's quicker and more reliable to use a calculator. There's this thing about questions on tests, they aren't there to teach you. They are there to test what you know.

Common recusion usages

[Anonymous Coward]

Quicksort, the standard sorting metod is normally implemented using recursion. Similarly algorithms that traverse tree and related structures are often implemented recursively.

Testing != Teaching

[Anonymous Coward]

Has this idiot ever looked at an AP Calc exam? There is no time in my professional career when someone handed me a sheet of paper and told me to integrate e^x^2 from -inf to +inf. There is no time in my professional career when I ever needed to do that integral.

Yet there it was on my AP Calc exam.

Does this mean the AP exam was teaching me "bad math practice?"

No, of course not. The AP exam wasn't trying to teach me a goddam thing, it was trying to test my understanding of the tools at large.

TL;DR: Blogger is an ignoramus, thanks so much for bringing it to everyone's attention.

Re: Testing != Teaching

[Anonymous Coward]

Fwiw, someone gave me that exact integral for my interview at Nvidia. Sad but true. At least I remembered how to do it.

Re:Testing != Teaching

[Anonymous Coward]

Surely you mean e^-x^2....

Re:Testing != Teaching

[Actually, I do RTFA]

The integral of e^x^2 from -inf to +inf happens to just as solvable as e^-x^2. Kinda trivially obvious.

Although I could've sworn it's unbounded... need to think about it.

Re:Testing != Teaching

[Anonymous Coward]

Nope: e^-x^2 has limits of 0 at +/- inf, while e^x^2 goes to Inf. Also, I'm pretty sure that this would not be on the AP Calculus exam regardless as evaluating it requires either double integration (which is not generally covered until mulitvariable calculus) or alternatively complex analysis. The easiest way to get that this is sqrt(pi) is to multiply the integral by itself (with y in place of x) and then to do a change of variable from (x,y) to r dr d theta and get int_0^2pi int_0^inf e^{-r^2} r dr d theta which gives int -e^{-r^2}/2|_0^inf d theta = 2 pi (-e^{-inf}/2 - -e^0/2) = pi and then concluding that the original integral was the square root of this.

Re:Testing != Teaching

[Anonymous Coward]

That is a "Gaussian Integral". The answer is the square root of pi. You can look it up on wikipedia or mathworld if you are interested.

Re:Testing != Teaching

[u38cg]

happens to just as solvable

Er, no.

Re:Testing != Teaching

[gordo3000]

if your career involved physics, you would run across that integral all the damn time. And just understanding the trick of squaring the integral and then implementing a change of variables can help later on with different problems. I always found that question to be the simplest way to check if you have learned about the value of doing a change of variables.

but then, (and I'm reaching into the way back machine here) I don't recall AP Calc of either level ever testing a gaussian integral. Maybe you really mean e^x^2 and they were just checking if you knew to ignore any work and just realize it is divergent and positive in both directions?

Recursion practicalities

[mveloso]

For most stack machines recursion is bad because the stack cannot grow without bounds and you have no idea where that boundary is. That's the practical problem with recursion.

Re:Recursion practicalities

[Layzej]

Tail recursion should be used if stack is a concern.

Re: Recursion practicalities

[Anonymous Coward]

Thank god the compilers I was using when at uni 15 years ago aren't doing tall recursion.
I was taught Haskell in my first semester, then was taught C, of C hadn't trashed the stack with my recursion I'd sti'd have tried to use it for so many of my problems.
Not that I didn't know the alternatives, but recursion was how I'd been thinking to dive 99% of my previous 6 months of uni work.

Re:Recursion practicalities

[Anonymous Coward]

Can the compiler create tail recursion out of the cited problem? The recursion is before the print.

Re:Recursion practicalities

[Layzej]

(define (showNumbers x output)

(if (zero? x)

ouput

(showNumbers (sub1 x) (concatenate x output ))))

Re:Recursion practicalities

[Simon Brooke]

This is kind of nonsense.

In most current compilers for ALGOL derived imperative programming languages (such as C, Java, C#, Pascal...), it's true, because, TRADITION! But it's not true of the underlying hardware, and it's not true of any compiler which implements its stack as a linked list. In principle there is no reason at all why you should not allocate all your available store to stack. There's also no reason why you cannot dynamically implement your stack in your heap.

These are all language (and run-time) design choices, and just because the people who specified ALGOL in 1958 - when I was three, goddammit - were working on machines which were (by modern standards) desperately poor of both mill and store, doesn't mean that we need to continue to copy the design choices they made then.

Re:Recursion practicalities

[cwsumner]

If there is no need to store the local datasets from each pass-through, then use a loop (iteration).
If there is a requirement to store each local dataset, such as a need to "unwind" afterward, then recursion might be useful.

But don't fool yourself that recursion releases you of the need to be aware of memory used. Most programs will crash if the stack is "blown away". And even if the OS can push the stack(s) into a swap file in other storage, it will slow the program down so far that the user will probably forcibly halt the program.

Maybe that's ok for your program, but mine right now is for dropping hot asphalt into dumptrucks. If it crashes, people could be killed.
(Of course there are other safeties! But I must program as if there were not...)

Poor choice for recursion

[cfalcon]

If something is super fast, the overhead from all the subroutine calls (specifically, the stack manipulation) will make it shit compared to a loop. I think the idea that everything is magical happenings (like idealized math) until late in CS is a definite issue.

Still, for a simple recursive demonstration, that's fine. It would be better to then show which should be looped and which should be recursive. But the fact that you can loop billions of times but I doubt you could recursively call a billion deep should be kept in mind- this is a fundamental limit of function calls.

Re:Poor choice for recursion

[Anonymous Coward]

To be fair, printing some string to the console will be so slow you won't notice any overhead from function calls.

Re:Poor choice for recursion

[Anonymous Coward]

Not sure if this is flame bait, but Computer Science IS idealized math. What you refer to is more properly Software Engineering, albeit many CS programs have abandoned proper CS.

Frequently use recursion

[Anonymous Coward]

A lot of the data I work with is tree-like or more generally directed graphs and recusive techniques are absolutely essential for handling them. Often the recusive function contains iteration, ie:

                      def do_something(node):
                                      for child in node.children():
                                                  do_something(child)

Recursive .vs. iteration isn't a style choice, it's a matter of selecting the right tool for the job from the constructs the language du-jour offers.

But in template metaprogramming...

[Mr Z]

Public Service Announcement comes on the television. Pages of code scroll by on a computer screen in the background. A strung out looking programmer stares into space, bleary eyed, obviously stressed, pulling his hair out. A voiceover begins...

Using recursion as a simple looping construct in an imperative programming language isn't normal. But, in C++ template metaprogramming, it is.

Template metaprogramming, not even once.

;-)

(Actually, I do a fair bit of template metaprogramming in C++. It can be handy for a certain class of problem.)

Re:But in template metaprogramming...

[Jeremi]

(Actually, I do a fair bit of template metaprogramming in C++. It can be handy for a certain class of problem.)

That "certain class of problem" wouldn't happen to be "how to guarantee my continued employment by ensuring that nobody else can understand the codebase", would it? ;^)

Re:But in template metaprogramming...

[Mr Z]

*chuckle* It's a power so great, it can only be used for good or evil!

Actually, it's useful for compile-time optimization of performance critical code. For example, I have a CRC calculation template class that generates its lookup tables at compile time based on the specified polynomial, shift, direction and field size. Need a new CRC in a different wacked out field? One line of code and it's there.

Previously, in C (or C++ w/out template metaprogramming), I'd need to either write a separate program to generate the lookup table for me offline and manually graft that into the code, or generate the lookup table at startup.

The consuming code is fairly clear, so in principle it makes other code easier to write. Of course, if there were something wrong with my implementation, debugging it is potentially more challenging.

Re:If you're going to criticize...

[OSULugan]

You should check preview before posting. The HTML parser removed the "<" from the quoted code, making your example wrong as well.

A functional programmer

[Phillip2]

"Some one raised in functional programming"

Would a) not have combined a recursion with a side-effect, b) we have been sure to make a tail call and c) probably used higher-order functions anyway.

None of which is relevant. This is poor coding style because this is Java which isn't functional and has no tail call optimisation. But, this is a standard problem with assessment; it can be very hard to come up with good and realistic examples, while limited to the knowledge that the students have at the current time. Try and you might, at times, you show less than optimal code, because to write better code you have to teaching something else entirely.

Re:A functional programmer

[angel'o'sphere]

Of course Java has tail call/recursion optimization. (*facepalm*)

Re:A functional programmer

[Anonymous Coward]

This is the 2nd time in this thread that you've made this claim without providing proof. Well this time you specifically said Java, so I'll give you proof that you're wrong so you can shut the'o'hell up.

Try the following on Java 1.8:

static int sum(int a, int b) {
  if (a < 1)
    return b;
  return sum(a - 1, b + 1);
}
public static void main(String[] args) {
  try {
    System.out.println(sum(1000000, 0));
  } catch (StackOverflowError e) {
    System.out.println("caught StackOverflowError");
  }
}

p.s. gcc 4.8.2 only compiles this example to a tail recursion for -O2 or higher.

Re:A functional programmer

[frank_adrian314159]

Java has facilities that could be used for tail recursion optimization, but Java language implementations aren't required (maybe aren't allowed, due to the language specification) to use it. It's available, but not dependable.

Re:A functional programmer

[Phillip2]

Strictly, Java would never have TCO. It would have to be the JVM. And, no it doesn't have TCO, although, I do believe that there are plans for it. I don't remember where I read that, so don't quote me.

It is for this reason that, for instance, Scala and Clojure both implement their own limited form of TCO (the self-recursive tail-call), which they do by compiling to an iterative form.

It is easy to demonstrate this with a method that calls itself. In java, it will crash with a stack overflow error. With TCO, it should loop indefinately.

Re:A functional programmer

[Phillip2]

Nope. It's just not there. I think you mean JVM, anyway, rather than "java language implementation" which is rather ambiguous.

It's not a surprise. Java was never functional. Why have an optimisation which essentially rewrites recursion as a form of iteration, when the programmer is going to use iteration anyway?

This is changing now, I think, that the JVM is becoming more important than Java.

Re:A functional programmer

[angel'o'sphere]

Actually I'm not sure the compiler/jit knows what to do if the recursive call is unconditional.
This post clearly shows that TRO is pretty simple on JVM bytecode already, so I doubt the Java compiler or JIT does not implement this optimization: http://programmers.stackexchan...

Re:A functional programmer

[Phillip2]

That TCO is implemented by both Scala and Clojure sort of demonstrates the point really. I mean, why would they bother if the Java Compiler did it already?

In fact, both Scala and Clojure implement it in the same way -- they remove the function (method) recursive call. In otherwords, you see a recursive call in Clojure/Scala but there is not one in the byte code. Method calls in Java consume stack. Try the answer that I gave you earlier. Otherwise, can you please show me the part of the JVM spec which describes TCO on the JVM. It has to be there, because TCO changes the way that you program.

There is a nice write-up on Java and how it does not implement TCO here at DrDobbs.

http://www.drdobbs.com/jvm/tai...

Re:A functional programmer

[angel'o'sphere]

If you want to abbreviate it, it is TRO, and not TCO. At least the former is the term I learned in school 30 years ago.

I'm uncertain now if the Java compiler does it. However it has absolutely nothing to do with the JVM spec. How do you come to that idea?

I see, drdobbs also uses TCO ... perhaps we have now to cope with two names ;)

I'm pretty sure Java 5 and later Java 6 compilers where supposed to implement TCO. Perhaps it got dropped, did not check that, its a bit difficult on the iPad :) Your link claims it is not even implemented in Java 8, I wonder if the JIT does it, kr if that was the way how it was supposed to be done and that got dropped.

Anyway, Scala, Groovy, Clousure at al implement their own compiler for various reasons. It is ok, to generate Java Source and then invoke the Java compiler as proof of concept. But bottom line generating your own byte code is much more efficient.

Anyway I stand corrected for now that Java has no build in TRO/TCO in the Java compiler.

Re:A functional programmer

[Phillip2]

TRO I would guess stands for Tail Recursion Optimisation, which is a special case of the Tail Call Optimisation. It is always possible to drop state for the stack after a tail call, even if it not recursive. This allows, for example, implementing mutually recursive functions without blowing up the stack.

Both Scala and Clojure only implement the self-recursive TCO. In general, they both try to compile into Java in a naturalistic way -- so a function call in either compiles to a byte code method call. The JVM is Turing complete, so they could implement anything that they want, but they'd have to loose the close relationship between their language and the JVM. So, they only do this for the tail recursion call. This gets 90% of the benefit for the least effort.

Re:A functional programmer

[Simon Brooke]

(apply str (take 7 (range)))

Re:A functional programmer

[Simon Brooke]

Tail Call Optimisation is not implemented in Clojure, and the reason given in the documentation is precisely that interoperability with Java prevents this. Instead there's a recur special form, which, in my opinion, is a bit of an ugly hack.

This is a Computer Science Test...

[rockmuelle]

... not a programming test. Recursion is a key concept in CS and is the foundation of many techniques and principles. Sure, no one uses it in practice that often, but that doesn't mean you shouldn't know it if you're learning CS.

If you want to train people for job interviews, send them to a trade program. If you want them to understand the field, you have to teach them the fundamentals.

I never use the central limit theorem directly when doing stats, but knowing how it underlies the methods helps provide a better understanding of results.

-Chris

Re:This is a Computer Science Test...

[Pseudonym Authority]

I'm glad that someone realizes this. Too many people are proud to be code monkeys and thing that shitting out an XML library in Java is the height of computing.

directory recursion simple example of WHY and how

[raymorris]

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.

Recursion should be used sparingly.

[Anonymous Coward]

"Smart" programmers sometimes forget that a strong emphasis on readability and maintainability are very important facets of being a great software engineer.

You may be "smart" today to show how clever you are, but the next guy in has to re-learn your "cleverness."

Re:Recursion should be used sparingly.

[plopez]

A very good point. More than once I have incidents in my career where I have thought to myself "I can be really clever about this." My follow up question is "SHOULD I really be clever ablout this?"

Re:Recursion should be used sparingly.

[cwsumner]

A very good point. More than once I have incidents in my career where I have thought to myself "I can be really clever about this." My follow up question is "SHOULD I really be clever ablout this?"

Ah! ... A person who has grown some wisdom. 8-)
Anyone young who reads this, remember it. It will save you much grief.

I'm weary of recursion

[bytesex]

Normal loops risk never ending.
Loops made by recursion risk ruining your stack to boot.
Recursion is mostly a hobby of mathematicians and in practice is a tool that should be used ultimately sparingly.

Re:I'm weary of recursion

[tuffy]

Languages that guarantee tail call optimization won't have a problem implementing an infinite loop using recursion.

Re:I'm weary of recursion

[SuperKendall]

Languages that guarantee tail call optimization won't have a problem implementing an infinite loop using recursion.

Yes but it's all to easy for the unwary to make a small change to the code and now it can't be tail optimized... I don't believe there's any compiler that warns you "hey this is close to being tail optimized but it's not currently".

Re:I'm weary of recursion

[tuffy]

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 and making sure to get it right. I'm just saying that recursion isn't guaranteed to blow up one's stack in all cases - it's all in the implementation.

Article misrepresents the test

[gnasher719]

The test doesn't actually ask you to write a recursive function. It shows you a function and asks you what it does. _That_ is a basic skill that any real-world programmer must master: Look at some code that might be coded badly, and figure out what it does.

The minor detail that the bad code uses recursion is irrelevant. And just like I don't learn bad practices from bad code that I see, I don't think anyone would learn bad programming style from this example. Anyone who can figure out what the code does will know how to get the same result with simpler code.

Re:Article misrepresents the test

[Anonymous Coward]

that may be coded badly? Most of the code I have seen over last years was bad, usually so bad that it was painful to look at it. I have seen good code few times in my life. Actually one could disregard those incidents because they were not reproducible, there was no intention of surrounding designers to use them as best examples for practice etc. People that wrote those were very good and could also explain why they had to do things the way they did which is more than most of other people could do.

Re:Article misrepresents the test

[gnupun]

The minor detail that the bad code uses recursion is irrelevant.

Stop parroting the stupidity of the article writer. There is nothing bad about this code. The code is utterly simple and is being used to test whether the student:
a) Can read code
AND
b) Has a decent understanding of recursion

Anyone who can figure out what the code does will know how to get the same result with simpler code.

Again, the test writers are not trying to find an optimized way to display "0123456." They are instead interested in testing whether the student has basic competence in understanding/using recursion.

TFA is either written by a troll or a moron.

What's the problem here?

[Chysn]

It's an exercise in determining the behavior of the function, not instruction for the right way to achieve what the function does. In the real world, you have to be able to follow sub-optimal code and know what it does. Anybody with the skills to follow this function will know one or more better ways to achieve the same result.

Re:What's the problem here?

[Anonymous Coward]

I'd rather certify my pilot using experience flying a plane or flying a plane simulator than experience driving a tank.

What's the point in scoring people on their ability to do it wrong?

Re:What's the problem here?

[Chysn]

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?

If the shoe fits...

[Anonymous Coward]

I tend to use recursion if it fits the problem well, and the cost of doing it iteratively would (seem to) be higher than the expected imposition on the stack. This varies with the language and whether the implementation supports tail recursion optimisation.

But I've always felt that certain people's fascination with recursion was about on par with certain (possibly other) people's fascination with, say, hashing's O(1) lookup complexity without regard for the size of the associated constant, that in some implementations would easily allow for quite a large N in structures with O(log N) lookup complexity, possibly to the point of running out of memory first. Or, say, the default use of hashmaps with generic and expensive hashing algorithms in some languages, even for structures with but a few members, so even linear search might be competetive.

On the gripping hand, this guy's complaint says more about his inability to find reasonable examples to illustrate recursion than it says about the existence of such examples. I might mention codingbat.com as a counter-point, for example.

Re:If you're going to criticize...

[bytesex]

Has there been a correction in the article? The code in the article now prints i, making it correct.

We all use recursion

[Okian Warrior]

I don't think I've ever user recursion in my professional career. Sure, if I ever need to code a BNF grammar I might, but it's just never come up in the real world.

Whether you use it or not, recursion plays an increasing role in our daily lives.

If it weren't for recursion, you wouldn't have that computer! Or that chair you're sitting on. Or that coffee...

As a python coder, rarely do I use recursion loops

[Jiilik Oiolosse]

For the example given, this is a list comprehension one-liner. (print(n) for n in range(7))

However, I do use recursion for looping in one situation - if my loop is running non-blocking as part of a larger event loop. Example below (excuse the dots leading underscores, slashdot doesn't let me format python). Normally, you'd just use while True for a loop like this.

loop = asyncio.get_event_loop()
def eventDispatcher(self):
__ev = poll_for_event() # non blocking, return None if no event
__if ev: loop.call_soon(do_something(ev))
__loop.call_soon(eventDispatcher)
loop.run_forever()

Embracing or eschewing recursion

[jgotts]

Most programming is mainaining somebody else's, usually poor, code.

Do not use recursion if it makes you feel clever, or if you're showing off your mastery of some programming language's syntax. Don't use recursion for efficiency. Writing efficient code rarely matters. By rarely I'm not saying never!

Use recursion if it results in the most understandable and easy to grasp code for someone, probably currently in junior high, 10-15 years from now.

In 15 years processors, IO, and storage will be many times faster and the bottleneck costing your former employer millions in lost profits will be your tightly-coded routines buried deep within the infrastructure.

Re:Embracing or eschewing recursion

[Anonymous Coward]

Most programming is mainaining somebody else's, usually poor, code.

Don't we all think that code from someone else is poor?

Re:Embracing or eschewing recursion

[sourcerror]

Don't use recursion for efficiency.

I don't think it's ever more efficient using recursion instead of loops, it's usually the opposite. With recursion there's an overhead of maintaining the stack, so converting it into a loop makes it more efficient.

Re:Embracing or eschewing recursion

[ArcadeMan]

Not someone else, everyone. If I could have a word with my younger self, I'd kick him in the ass.

Re:Embracing or eschewing recursion

[SuricouRaven]

Recursion makes stack handling magically work - with looping the programmer has to keep track of the resulting mess, usually involving arrays of a size not known until after the algorithm completes. Complicated code invites bugs.

Re:Embracing or eschewing recursion

[Anonymous Coward]

For inherently recursive algorithms, like depth-first tree walks, using recursion and hardware stack can be a lot more efficient than iteration with manually maintained stack.

inb4 "But what about stack smashing" - in case of a balanced binary tree, for example, 64 stack frames will walk you more nodes than any common CPU can address.

Accidental unbounded recursion is as much of an omghorrifying bug as accidental unbounded iteration, except you'll notice faster.

Re:Embracing or eschewing recursion

[Anonymous Coward]

This..
I've seen code that is supposedly "iteration" which is essentially implementing a stack, and I guarantee that the folks who wrote the compiler generate more efficient code than you do implementing your own push/pop mechanism.

It's trivial to implement a "depth check" in your recursive routine so that if you do get in a situation (corrupt tree structure with a self linked node or a cycle), you don't die gruesomely. Or, if the tree's not supposed to be too deep, you can just check if the new node you're at duplicates any of the previous nodes.

[From someone who wrote a recursive B-tree handler on a PDP-11/70 in 1979, in FORTRAN and PDP-11 Assembler, no less]

Re:Embracing or eschewing recursion

[Actually, I do RTFA]

Processors aren't likely to be any faster. Your single-threaded code or race conditions when run on 8096 cores are likely to be the major bottlenecks.

Re:Embracing or eschewing recursion

[cfalcon]

No, what will cost them the lost profits will be the managers all hopped up on some shitty fucking trend that tells them to recode your tightly-coded routines with something that is super slow and awful (but trendy) and they believe it's no big deal because they think hardware is still advancing like it's the 80s.

"Quick, redo it all in a fad language!"

Awkard?

[Headw1nd]

Not sure about the test, but the summary was certainly awkward.

Recursive thinking

[Anonymous Coward]

Iterative implementation.

Unless the particular language of implementation has good support for tail recursion.

Do I tend to embrace or eschew recursion? Neutral

[Anonymous Coward]

I'm neutral. I code both ways, compile with -S and see which one looks better in assembler.

...use recursion instead of a loop...

[nuckfuts]

Recursion is a loop.

Re:...use recursion instead of a loop...

[Anonymous Coward]

Unwinding frames in the event of error handling becomes tricky because you're messing with a language implemented stack. You don't have direct control over the data structure and must rely on language supported unwinding semantics. Depending on language this can be a nightmare especially when there are cascading errors. A user controlled loop doesn't inherently have this problem.

Re:...use recursion instead of a loop...

[cwsumner]

Recursion is a loop.

Recursion is a loop with a stack that You Cannot See.
It the "Cannot See" that mathemeticians like and experianced programmers hate.

It's like a car that runs on steam and uses the sides and doors as radiators. You can't see it and it all works great, until something breaks and you are scalded to death!

The Correct Answer

[Njorthbiatr]

OutOfMemoryError

Re:The Correct Answer

[Anonymous Coward]

OutOfMemoryError

Maybe - but more often you'll see that when you run out of heap memory, or if you are very lucky and your system isn't completely degraded, when you run out of native memory. When you run out of stack (such as from recursion) you usually get: java.lang.StackoverflowError

One solution is to add -Xss as a java parameter to increase the stack space. Another to fix your code not to recurse that deep, however, that's not always possible when integrating multiple frameworks together (even OSS ones ... I'm looking at you Spring with your recursive error handling, ugh!).

Actually in a functional language ...

[angel'o'sphere]

... you would use a variation of a map function, for-each function or what ever and use a labda or a closure and _not_ recursion.

Re:Actually in a functional language ...

[Shados]

Cool. Now someone implemented the forEach function. How did they without imperative loop construct?

Re:Actually in a functional language ...

[Anonymous Coward]

... you would use a variation of a map function, for-each function or what ever and use a labda or a closure and _not_ recursion.

How did you implement map() without recursion? If you used a library, the fact that you hid the recursion in a library call doesn't mean it isn't there.

Re:Actually in a functional language ...

[angel'o'sphere]

Who cares how it is implemented? As you know we have two options.
My point is: if the assignment is to print either 0...6 or 6..0 then you write something like:

        [0..6].each {
                print it
        }

No one would write a loop here or try to put that away into a recursive function. So if the poster is concerned about 'bad programming habits/examples' he he should not make his claims.

Re:Actually in a functional language ...

[Shados]

If I go through college and replace all my assignment with libraries, I'm barely going to have to code. Writing a Chess AI? No one would bother, there's some already implemented. Learning how to write sorts? Pffft.... sort is built in virtually every collection type of all mainstream languages, or at least its in the mainstream libraries. .each is there even in most imperative languages, so you wouldn't be learning for loops either.

Obviously from the article's context, the assigment is to implement it, not use library functions. So you'll either be using some kind of imperative loop, or you're going to use recursion.

Re:Actually in a functional language ...

[angel'o'sphere]

The original assignment was to use RECURSION!
The poster of the article said: this is bad practice! You should use a LOOP.
I say: the poster is an idiot. Especially with his claim regarding functional languages.
Of course in a test you program a recursive function if it is asked for ... it is actually not that hard anyway.

Re:Actually in a functional language ...

[JesseMcDonald]

Now someone implemented the forEach function. How did they without imperative loop construct?

forEach(iterator, function):
..if (!iterator.at_end()):
....function(iterator.get())
....forEach(iterator.next(), function)

A better question would be: How do you implement a loop construct without recursion?

Keep in mind that recursion is nothing more or less than the ability to return to a previous point in the control flow of a program. The stack overhead associated with a lack of tail-call optimization and the special treatment of iterative constructs are merely implementation details, whereas recursion is a fundamental concept in computer science without which most programs would be impossible to express.

Re:Actually in a functional language ...

[Shados]

that was the whole point i was getting across. It was a rhetorical question =P

Different hammers for different apps

[Anonymous Coward]

Your example of the hammer is apt. However it is easy to distinguish what type of app is right for recursion and what type of app is better suited for a loop algotithm.

If you're calculating the area of an irregular shape using Simpson's rule, you probably want to use a loop to do the calculation. Imbedding your logic doesn't seem appropriate in this case. You are using the loop counter to defind how detailed your calculation should be.

If you're creating, updating, and traversing tree structures, recursion simplifies your logic immensely. Here's a case where recursion is appropriate. You are using the end test in your recursion to determine when you have reached the leaf node in the tree.

These two examples of looping and recursion show that the code used in the AP test question depends on what type of application is involved in the question.

Recursion examples

[ArcadeMan]

Before looking at recursion examples, students should first learn recursion examples.

Re:Recursion examples

[Anonymous Coward]

Nope. It's turtles all the way down.

Re:directory recursion simple example of WHY and h

[phantomfive]

It's "the right tool for the job" category.

Also, there is an overlap where either iteration or recursion work equally well, and it comes down to preference (clearly the author does not prefer recursion, almost ever, but other people find recursion natural even for iteration. Certainly for mathematicians it is more intuitive than the bizarre syntax of the for() loop that we all had to learn).

Like a "Hello World" program

[myid]

In the real world, we don't generally write a computer program that just outputs the message "Hello World". But that's usually the first program when we're learning a new programming language. This simple program teaches us how to create the source code, compile, and run the program. Later we learn how to write more complex programs in that language.

In the same way, we don't use recursion to output a string 0 to 5. But this simple problem teaches the student how recursion works. After the student understands how recursion works, s/he can do more complex and realistic problems using recursion.

The question is actually excellent

[LostMyBeaver]

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?

Re:If you're going to criticize...

[Anonymous Coward]

Yeah, see the author's comment in reply to someone who pointed out the error.

Yolo

[Anonymous Coward]

function recursivePrint(i) {
                if (i = 6) {
                    console.log(i);
                    i++;
                    recursivePrint(i);
                }
            }
            recursivePrint(0);

Reminds me of college :)

[MMC Monster]

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.

Embrace or avoid?

[frank_adrian314159]

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 question is actually a class of questions

[maas15]

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.

Understanding poorly written code is important

[stevelind]

In the example, the AP test is actually asking the student to describe what the code *does*. It does not ask them to write bad code, only read it. Everyone who develops software must be able to figure out bad code, so we will know what to delete ;)

Re:Understanding poorly written code is important

[Hognoxious]

Another non-story from theodp. But at least he's concise.

Not all in the implementation

[SuperKendall]

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)"?

Re:Not all in the implementation

[tuffy]

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.

Writing code such that the last call in the function is always another call to itself isn't some deep mystery, though. The only question is whether the language is guaranteed to optimize that case.

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)"?

Since Haskell has no built-in "while" statement as such, you're going to need to either write an explicit recursive loop or just use one that's already been pre-built for running some action forever. It's just more obvious what's going on by using the latter.

Re:directory recursion simple example of WHY and h

[Anonymous Coward]

You never know how deep a directory goes. I never use recursion except when it's tail optimized. Sure, the code for recursive tree traversals looks so much nicer, but they have hidden stack overflow bugs.

Is there ever a time when it's safer to use recursion compared to a loop?

Lack of compiler support !!!

[bradley13]

I would use recursion a lot more frequently if compilers supported tail recursion. Not for simple iteration, perhaps, but there are plenty of cases where recursion is a better solution that a loop. For example, recursion is often be appropriate when working through some sort of data structure.

The problem is: The most common languages don't optimize for tail recursion. This means that even shallow recursion will eat memory. If the depth of the recursion is unknown, then the lack of optimization for tail-recursion means that your program may run out of memory - not because of any programming error, but due to a defect in the compiler.

There is nothing inherently difficult about handling tail recursion. Scala does it just fine, running on the JVM. I can only imagine that those responsible for mainstream languages figure no one will use it. Well, we, can't, because your compilers don't support it properly...

Re:Lack of compiler support !!!

[ockegheim]

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.

not even a ninja

[hirundo]

> So, do you tend to embrace or eschew recursion in your programming?

"To iterate is human, to recurse divine.” -- L. Peter Deutsch

Since the guy who has to debug and extend my code is human (me), I take pity on him and recurse only as needed.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:Tests aren't about good practice? Say it isn't

[plopez]

Nah. I often do "back of the envelope" arithmetic operations in my head in less time than it takes to pull out a phone with a calculator app, fire up a laptop, etc. I find it works well when comparing unit costs in the supermarket.

Yes, but...

[bradley13]

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.

Re:Yes, but...

[SQLGuru]

When I was learning recursion (eons ago, it seems), I was informed that both head and tail recursion could be "unrolled" to a loop of some sort (for, while, do....while, do...until, etc.) And recursion imparts a lot of overhead (push to stack, context switch, process, pop from stack), so you should unroll recursive functions as often as possible.

So, in this example, I don't think most people would think to use recursion at all --- head, tail, or mid recursion.

Re:Yes, but...

[david_thornley]

Some languages, like Scheme, will automatically unroll tail recursion. (It looks to me like an implementation detail, but it's in the specification.) Some uses of recursion could be unrolled, but would require an explicit stack, meaning that the unrolling wouldn't buy you much.

In Scheme, I'd use recursion for this problem, because that's what the language offers. In more procedural languages, nobody would use recursion.

Re:Yes, but...

[StikyPad]

int recurPrint(int start, int stop) {
    if (stop < start) {
        std::cout << "Nice try!";
        return 1;
    } else if (start < stop) {
        recurPrint(++start, stop);
    } else {
        for (int i=0; i<=stop; i++) {
            std::cout << i;
        }
        std::cout << "\n";
        return 0;
    }
    return 0;
}

Re: Yes, but...

[countach]

Depends on the programming language. In Scheme ALL iteration is reduced to recursion. But then, if the compiler is a clever one, it just turns into unrolled jumps. It's all the same I the end.

Re: Yes, but...

[countach]

Errrm did you stop to think that the term tail-recursive contains the term recursive? Nah, didn't think so.

LOL

except on Windows, Mac, Linux and FreeBSD

[raymorris]

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

Re: except on Windows, Mac, Linux and FreeBSD

[Anonymous Coward]

Sorry, Windows has supported paths up to ~65000 chars since Windows 2000 at least. . Bugs often crop up with super deep directory trees though, due to the max_path misunderstanding.

Ditto javascript

[Anonymous Coward]

However, I do use recursion for looping in one situation - if my loop is running non-blocking as part of a larger event loop.

I do the same thing in Javascript to asynchronously add autocomplete dropdown entries to an edit box, four at a time on each paint tick:

worker.postMessage(tagset); /* Asynchronously remove duplicate tags and sort */
        worker.onmessage = function (ev) { /* tags array and template of an option element */
                var d = document.getElementById(dl),t = d.firstChild.content,w = ev.data,
                observer = new MutationObserver(function(mo) {
                        t.firstChild.setAttribute("value",w.shift());
                        t.firstChild.removeAttribute("label");
                        if(w.length<1){observer.disconnect()} /* add the next tag to datalist */
                        if(w.length % 4 != 0){d.appendChild(t.cloneNode(true))}
                        else requestAnimationFrame(function(){d.appendChild(t.cloneNode(true))});
                }),
                config = {childList:true};
                t.firstChild.setAttribute("value",w.shift());
                t.firstChild.removeAttribute("label");
                observer.observe(d,config); /* watch for tags being added to datalist */
                d.appendChild(t.cloneNode(true)); /* add the first tag to the datalist */
                worker.terminate();
        }

Entirely relevant

[mjhans]

I'd argue this is one of the best questions you could possibly ask a to-be programmer.

"Here's some contrived, shitty code that some jackass wrote, without comments, before leaving. What on earth does it do?"

Inherent Conflict in writing vs. reading

[Tablizer]

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.

Re:Inherent Conflict in writing vs. reading

[PPH]

clarity to other readers matters above parsimony

Is that one pass or multiple pass parsimony?

Fibonaci

[Ragica]

I thought it was the law of programming that recursion be introduced with a Fibonacci sequence generator. I believe this AP thing is breaking the law of programming.

umm...

[duck_rifted]

There's a use case where any simple problem that can be solved with recursion should be: template metaprogramming. Have the AP exam authors not heard of compile time constants or do they think that the people taking their exams won't recognize templates? Either way, this should be a non-issue for people in a position to write those exams. The fact that this is even a topic of discussion diminishes the AP exams in my eyes.

Re:umm...

[david_thornley]

Do you really want to teach template metaprogramming to high school students, however advanced? If you're talking about C++, it takes a good deal of study to get familiar enough with the language to attempt template metaprogramming, and then it's a really awkward programming language that has nothing much to do with regular C++. I'd rather teach recursion with Scheme.

(Yes, there will be high school students who know enough C++ and are ambitious and intelligent enough to attempt template metaprogramming. How many will there be in one school district?)

Re:umm...

[duck_rifted]

Are you kidding? TMP is central to modern C++! It's necessary for introspection, for example, which is in turn necessary for type safety in relativistic progra... Oh. Yeah, I see what you mean.

Re:directory recursion simple example of WHY and h

[Garridan]

Indeed, recursion is just looping with a stack. When you need a stack, recurse. Otherwise, loop. Contrary to TFS, there is clear reasoning behind a competent programmer's choice. The viewpoint of this being a capricious choice made at the "preference" of the programmer suggests that the submitter doesn't understand the vast differences in the internal impelementations of various languages.

Re:If you're going to criticize...

[Tablizer]

would print out "666...

No wonder conservatives are upset about Common Core

Re:If you're going to criticize...

[Anonymous Coward]

Anyone acting as a stickler for syntax should not be making that mistake in a public post that they presumably glanced over more than once.

Surely you mean that anyone acting as a stickler for syntax should not be making that mistake in a public post that _he_ presumably glanced over more than once.

covered already on /.

[fikx]

This talked about this as well...

Re:except on Windows, Mac, Linux and FreeBSD

[pspahn]

... MAX_PATH is 260 ...

and

It wouldn't hurt to check PATH_MAX ...

Recursion error?

Re:directory recursion simple example of WHY and h

[Anonymous Coward]

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.

Why the FUCK would you ever want to keep an explicit stack? Did your language implementers have brain worms? Stack and Heap are the same, it's just RAM. Function call stacks belong in heap. Each program has its own virtual memory region. So, there's no reason not to increment the stack pointer AWAY from zero (or have it start at max address, and increment down) so that you don't artificially limit the program with stack overflow. Counting upwards, I just trap SEGFAULT and if the instruction pointer was at a function stack allocation, then allocate a page of RAM mapped to the next sequential address required, and resume. There, now your code is free to recurse even in C without stack overflow limited by language implementation.

For fuck's sake people, it's 2015. I'm so fed up with the bullshit: I can make this recursion "iterative" with an explicit stack -- NO YOU FUCKING MORON, THAT IS RECURSION! You're FIGHTING against a MORONIC language implementation by manually implementing FUNCTION calls properly.

too many calls

[bugs2squash]

wouldn't:

public void printNumbers (int n) { if (n > 0) printNumber(n-1); System.out.print(n); }

Have been better, ie. shorter, fewer loops (or stack frames if no TCO)

Re:directory recursion simple example of WHY and h

[Anonymous Coward]

Recursing a directory structure is not a good application of recursion.

It would, if directory structures were trees. But they aren’t; they may (and usually do) contain symlinks, some of which may form cycles.

For dealing with directory structures in real world, you pretty much have to use an iterative approach coupled with a “have we crawled this yet” set.

depends, symlinks are a file

[raymorris]

You should of course decide how to handle symlinks. In most cases I've come across, a symlink is just a file - not something to be followed. Rsync's default behavior is an example of this - it by defaults copies the symlink, rather than recursing into wherever the symlink points. As I recall, tar is the same.

You need to handle symlinks and perhaps bind mounts based of application requirements.

Re:except on Windows, Mac, Linux and FreeBSD

[Anonymous Coward]

Windows is only limited to 260 characters in the ANSI API. In the Unicode API you can (should) prefix the path with \\?\, in which case the limit is raised to 32767 characters.

Also, symlinks.

Windows MAX_PATH, Linux PATH_MAX

[raymorris]

Windows defines MAX_PATH as 0x00000104 I'm sure someone will correct me if I'm remembering incorrectly.

Re:directory recursion simple example of WHY and h

[Actually, I do RTFA]

Stack and heap are different because of the use case. A stack has a much simpler memory manager. So you want to use a sstack whenever you can.

Now, if there's a language that lets you think as little as you have to when using the heap and get the performance of using the stack, please do let me know which.

First tool

[ceoyoyo]

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.

If you learned assembly, you just roll your eyes.

So strange!

[drolli]

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.

not quite. ntfs, SOME apis to 32,768. Others 260

[raymorris]

Not quite. The UNICODE APIs and NTFS support up to 32,768. Other APIs are still limited to 260 at least as of Windows 7. Explorer can't handle larger than 260, or at least recently couldn't. So long as the older APIs remain, the maximum safe length is 260. Longer paths may work sometimes, but behavior is undefined in general.

parallelism, for one. Normally a queue. Large data

[raymorris]

>. Why the FUCK would you ever want to keep an explicit stack? Did your language implementers have brain worms? Stack and Heap are the same, it's just RAM

Granted if you're doing it explicitly you'll more likely use a queue than a stack. But not necessarily. For example, you might process all children in parallel if you're working on a GPU or cluster. The parallelization library will then need an explicit stack.

Note to "it's just RAM" isn't always true. If you're crawling the web, your list of links to be visited will be in a database, not in RAM.

This is really stupid

[gweihir]

Do not use recursion in cases where iteration is simpler. Use recursion in places where iteration is impossible or much harder. The classical introductory examples of recursion like Fibonacci numbers and evaluation of simple arithmetic terms are perfect for the task. If you use recursion for things better done iteratively, you will only confuse people.

Off-by-one error

[Anonymous Coward]

You left out '0'. It should be '0123456' instead.

Use recursion when the problem is recursive

[spaceyhackerlady]

Regardless of the final implementation, there are problems where the simplest, clearest solution is a recursive one. You type it in to the computer as fast as you can type, it compiles and runs correctly the first time, and then, if you need to change it, you have a place to start.

On a job interview some years ago I was asked to write C code to reverse a string. I wrote it recursively: interchange the first and last elements, then reverse what's inside.

They liked my creativity. I got the job. :-)

...laura

Re:Use recursion when the problem is recursive

[Anonymous Coward]

Did they at least ask you if you knew how much memory your version requires, and then follow up by asking how you could improve that to O(1) extra memory?

Re:Use recursion when the problem is recursive

[spaceyhackerlady]

Yes, they did.

In another job interview I was asked to write a program to generate prime numbers. I clarified a couple of requirements ("is memory usage an issue?"), and implemented the Sieve of Eratosthenes. It works, you know why it works, any idiot can read the code and understand it, and if testing shows you need something better (in some sense), you know where to start.

...laura

Non-trivial

[sgunhouse]

To the question at the end of the article - I use either depending on language and appropriateness to the problem. Languages like CBM BASIC didn't support functions, so you had to find a way to use loops even if it wasn't optimal.

However, there are lots of non-trivial examples, so why settle for something trivial? It was always a bit of work writing a factorial in older BASICs, recursion is just so much simpler. Or maybe terms of Pascal's triangle? The Fibonacci series perhaps - while there is actually a formula for that, most people won't know it. Lots of possibilities.

I can give you three

[fyngyrz]

I have yet to see another reason to use recursion.

I'll give you two problems that yield to recursive approaches very nicely indeed.

The first is pixel-based area fill. The second is the expansion phase of object-oriented PCB trace routing. The third is in the repeated bloom steps of the optimum N-color picker for any >N color space, where N is 16 or more. They're all three very efficient in terms of number of lines, they're quite fast, and they do the job perfectly. You can certainly approach these tasks other ways; but I have yet to see anything as elegant.

These do require an architecture where stack space isn't a problem. Which -- IMHO -- would be any decent architecture out there.

Then comes to mind a remark by an old associate of mine. He would say: "Live recursively... die recursively." I always thought that would make a great t-shirt, if for no other reason than its inherent opacity to the common person. :)

Event-driven recursion

[Anonymous Coward]

In event-driven programming, event recursion, in which a handler for an event triggers the same event, can often be a solution that combines the benefits of both looping and recursion: Compared to classical recursion, it doesn't generates an ever-growing memory stack, because the function calls are actually processes sequentially; and compared to classical loop, it provides time-windows for other tasks to be processed in between the sequential calls (pseudo-multitasking), as well as more elegant ways to exit the loop under complex conditions (raising exceptions from within a loop to exit prematurely always looks hackish).

only once in a while

[Anonymous Coward]

A few times for tree traversals, but not for linear patterns which dont need complications/obfuscation to a simple enough process.

Even when on trees can easily pattern it recursively, but without using a recursive call (finite depth or non-valued descent is usually the case due to other processing self-limitations)

I don't understand why the example doesn't output:

[Anonymous Coward]

543210

Re:I don't understand why the example doesn't outp

[AC-x]

Because System.out.print(n);

It's a test of reading bad code, not writing it

[AC-x]

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

Re:I don't understand why the example doesn't outp

[Anonymous Coward]

I think it's because the printNumber(n-1); call does not allow the System.out.print(n) to happen until n>=0 and so it is recursed n times before the first System.Out.Print(n) happens, resulting in the output being reversed.

Re:I don't understand why the example doesn't outp

[bugs2squash]

That's why it's on the test

can do!

[thrig]

I am afraid I must recurse myself from this discussion.

Re:I don't understand why the example doesn't outp

[PPH]

This.

The printNumber function is repeatedly called until the base case is reached. Then the deepest called instance returns first (when n<0), reaching the Print statement and returning. As each call to printNumber is popped off the stack, the parent function output value is printed.

Indefinite Data Sets

[Edrick]

Recursion works best on data sets where we do not know finite beginnings & ends, and the levels, stages, relationships, etc...are theoretically infinite. A common example is any data structure with a parent/child relationship. This can include a family tree, files on disk, job hierarchy, etc...

Knowing when to use recursion is as important as understanding how to use it. The same goes for iterative approaches. When working with very large data sets, the wrong algorithm can lead to slow, inefficient performance that dooms a project at worst, and slows it down at best.

A very costly common mistake I often see in the real world is when an iterative solution is used in a situation where recursion is the most efficient way to go. Testing with lazy problems like listing the numbers from 0-6 using recursion reinforces potentially bad habits and is almost as bad as teaching recursion using those examples. Simple examples are OK, but should represent the fundamentals that are bring taught.

A better problem for the AP exam would be to provide a problem and NOT tell the students how to solve it. Score the results on if the right algorithm was used and its correctness from there. In the real world, no one tells you how to solve problems, and for a college-level course, the tests shouldn't either.

Wrong complaint

[Anonymous Coward]

The question was not how to print "0123456" but what does it mean for a program to call itself and what happens if parts of the program are left hanging, so to speak. If there's a complaint, it might be that the recursive call is not in the tail position.

Re:directory recursion simple example of WHY and h

[Anonymous Coward]

Explicit stack or queue may allow for parallel optimizations by the compiler.

Stack and heap have a difference with the kind of memory mapping (TLB/MMU) that is possible to be used. It usually doesn't matter until you've reached a large amount of stack memory being used.

Re:directory recursion simple example of WHY and h

[sribe]

Sure, the code for recursive tree traversals looks so much nicer, but they have hidden stack overflow bugs.

32-bit thinking in a 64-bit world? Old habits die hard ;-)

Lisp and scheme

[countach]

In a tail recursive programming language there is absolutely nothing wrong with using recursion to do things that some people might think is an appropriate use of it. In Scheme, looping constructs are implemented in terms of recursion.

Re:If you're going to criticize...

[ildon]

Oh the painful irony.