tag:blogger.com,1999:blog-18677687.post8669221086768462455..comments2024-03-27T15:13:24.764-04:00Comments on Computer Science Teacher: Recursion – Love it or hate it?Alfred Thompsonhttp://www.blogger.com/profile/05575057876858763822noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-18677687.post-74848939709275526672015-03-11T17:01:56.586-04:002015-03-11T17:01:56.586-04:00A recursive program to compute Fibonnaci numbers i...A recursive program to compute Fibonnaci numbers is marginally shorter than an iterative program, but much less efficient. If you compute fib(n) as fib(n-1) + fib(n-2), you wind up computing fib(n-2) twice. This duplication of effort leads to a running time that increases exponentially.<br /><br />Here are two examples that illustrate the power of recursion with arrays rather than trees.<br /><br />1. Merge sort<br /><br />To sort an array, divide it in half, recursively sort each half, and merge the results.<br /><br />2. Permutations<br /><br />To enumerate all permutations of a[1], ..., a[n], use a loop that interchanges a[1] with each a[i] and then recursively enumerates all permutations of a[2], ..., a[n].Anonymoushttps://www.blogger.com/profile/04930517554574531000noreply@blogger.comtag:blogger.com,1999:blog-18677687.post-1535630186281603472015-02-10T01:02:53.241-05:002015-02-10T01:02:53.241-05:00"John Bokma said...
http://en.wikipedia...."John Bokma said...<br /><br /> http://en.wikipedia.org/wiki/Tail_call<br /><br /> That's the reason why recursion in functional programming languages and several other imperative languages "Just Works" and don't use the stack."<br /><br />Even so in this example, the recursion done is not a tail call,WorBluxhttps://www.blogger.com/profile/17237331780596277891noreply@blogger.comtag:blogger.com,1999:blog-18677687.post-14646796655611091112015-02-09T13:15:37.116-05:002015-02-09T13:15:37.116-05:00The primary purpose of an exam question is to test...The primary purpose of an exam question is to test the students' understanding of a concept (or concepts), not to be an example of good code practice. You say it is 'good' for its main goal, and not 'good' in other ways that are not its goal. So it fails to do something well that it's not required to do well - that is not a critical issue - but still, the point should not be summarily dismissed. There is still the matter of quality, having good secondary attributes once the primary attributes are taken care of. That's a discussion worth having, too.<br /><br />Without being offensive or accusatory, I hope I can ask some questions, to stimulate the topic. You pointed out a problem: do you have a solution? In particular, if it were your responsibility to compose a question to test the same understanding as is required to answer the given one, how would you write the question? In general, what can be done to improve the overall situation? Or, do you bring the issue up more for the ensuing conversation, to help find solutions? - Speculating without much grounds here, so please forgive me if I'm wrong: Perhaps part of what bugs you is that exposing student to poor code, without them recognizing it as poor code, is doing them a disservice. So - if there were a question on the exam testing "do you understand where recursion is appropriate?" immediately before this question testing "do you understand recursion, itself?", would it still be so objectionable?<br /><br />The situation reminds me of Arrow's Impossibility Theorem. There is a set of policies: "a more complex structure is only appropriate where a less complex structure will not suffice or is cumbersome (usually meaning, in a larger problem)", "exams should test understanding of complex structures", "exams should have appropriate code", "exam questions to test a certain concept should not have problems much larger than necessary to test it", is a set of policies that individually are each desirable, but together cannot all be honoured all the time. I think "exams should have appropriate code" is the least important of all those policies, and should be the first one to be chucked out if they can't all be kept. Not that it should be wholly ignored, right from the start: where there is no conflict with the other policies, appropriate code should generally be used. But, that is really the lowest priority of the ones listed, and will be the first to be sacrificed.<br />hobyrnehttps://www.blogger.com/profile/17287316452345344211noreply@blogger.comtag:blogger.com,1999:blog-18677687.post-52066046641329814852015-02-09T13:15:03.133-05:002015-02-09T13:15:03.133-05:00The anonymous poster who said difficulty understan...The anonymous poster who said difficulty understanding recursion is often related to scope is on to something. Then, there is a secondary effect of teaching loops first.<br /><br />I) Students don't really understand how functions and parameters work after you teach them to use functions to break large problems up.<br /><br />Most languages use call-by-value parameter passing. Students naively assume some combination of global names and call-by-name.<br /><br />As we speak war story:<br /><br />I just taught recursion before loops in our intro course, which uses C++ (don't ask --- it isn't my fault). 90% of the questions are things like: how can keep the original value of a variable if the function keeps changing it? This means that students don't understand procedure call, parameters, local variables, and call-by-value. When you talk to them, they really do understand simple recursive examples in terms of when functions are called and what they want to happen. (We're doing very simple problems involving drawing ASCII-art-type patterns.)<br /><br />I'm hoping, and we'll see, that catching these misunderstandings now will have a big payoff later. If they're able to get programs to work without understanding how functions/parameters really work, then they're just being set up for trouble down the road (i.e., when we see examples with pointers and call by reference done C-style).<br /><br />We shall see!<br /><br />II) Down side to loops first.<br /><br />If you believe, as I do, that every working programmer needs to understand both, then conventional loops first has a serious downside. It's easier to learn (see the above about not understanding functions). Recursion is harder to learn. Students, faced with a tool that is harder to learn will be put off. Couple this with the fact that almost all early recursion examples are easily solved with loops, and you have a situation in which student say to themselves (and out loud) that recursion is just a more complicated to do what they already know, and so they don't need to learn it. And they don't. Really, they have learned about functions! When they DO really need it, they will be hit with all the things they haven't learned so far AND have to deal with complex data structures.<br /><br />I've taught recursion first and loops first before, though this is the first time I'm doing recursion first in the Tufts C++-based intro curriculum. Students really do learn recursive problem decomposition and coding strategies well ... if you force them to :-) And later in the curriculum, they pick up trees without a blink.Anonymoushttps://www.blogger.com/profile/01358742589659765528noreply@blogger.comtag:blogger.com,1999:blog-18677687.post-2672206992009277052015-02-09T12:43:15.496-05:002015-02-09T12:43:15.496-05:00I see no problem with the question as posed.
In t...I see no problem with the question as posed.<br /><br />In the real world, you'll encounter other people's code that is not necessarily best coding practice, yet you'll have to be able to read and understand what it does. The test question (as posed) is a perfectly reasonable example of this.<br /><br />I'd offer one should not expect all test questions to be representative of good coding practice, unless of course the subject of the question is regarding good coding practice.. i.e. "What are the possible shortcomings of this programming technique.."unixguyhttps://www.blogger.com/profile/16080376538044726883noreply@blogger.comtag:blogger.com,1999:blog-18677687.post-17528988587988225712015-02-09T11:25:09.926-05:002015-02-09T11:25:09.926-05:00Personally, I tend to favor teaching recursion alo...Personally, I tend to favor teaching recursion along with the rest of the looping structures. I can see the argument for holding off, but honestly to my mind if you can understand that looping an index out of bounds is a bad thing, you can get why an infinite recursion will cause major blowuppage as well. You don't even have to get into stack architecture too heavy, really.<br /><br />To me, recursion has always been one of those things that's like insurance: you usually don't need it, but when you do, you *really* do. It's a good thing to have under your belt and--more importantly--be able to understand. If you can demonstrate you understand the concept, even in a silly example such as this, then that's a good sigh you're learning to think algorithmically.<br /><br />As to the example given, yeah, it's a corny example and no, you'd never use recursion for this in the real world. But as a bare-bones test of the concept, I think it works, and to be honest I can't think of a better one off the top of my head. Perhaps it would be meet to follow this up with a discussion question, like: "How would you implement this differently? Explain your reasons."Just Kellyhttps://www.blogger.com/profile/12949112327630835091noreply@blogger.comtag:blogger.com,1999:blog-18677687.post-57874667585580125352015-02-09T10:51:09.713-05:002015-02-09T10:51:09.713-05:00"In CS terms: as you stated, recursion is rea..."In CS terms: as you stated, recursion is really good in tree or graphs, and should be taught AFTER people are able to use trees and graphs. "<br /><br />It's unrealistic to teach everything only in the context it's classically used. Students like simple examples of new concepts and this is a really lovely simple example of recursion.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-18677687.post-19773343983716853542015-02-08T21:32:13.484-05:002015-02-08T21:32:13.484-05:00My philosophy is: don't teach to use a hammer,...My philosophy is: don't teach to use a hammer, unless the situation requires a hammer. <br /><br />In CS terms: as you stated, recursion is really good in tree or graphs, and should be taught AFTER people are able to use trees and graphs. <br /><br />In my opinion, and I don't want to start a flame war, the poor teaching or recursion is due to mathematician switching to CS but unable to change their ways. When I learned recursion, it was for a stupid (in term of CS usage) ways: teaching factorial. Honestly, who would do:<br /><br />function facto(int n) {<br /> if (n<1) {<br /> return 1;<br /> } else {<br /> return facto(n-1) * n;<br /> }<br />}<br /><br /><br />Well a mathematician would because in their world, expo is defines as:<br /><br /> / 1 if n == 0<br />facto(n){<br /> \ (n-1)! x n if n != 0<br /><br />See the similarity? Or should I say, same thing, written differently? This is the problem: people still want to keep their religion that maths explain. Therefore, they just use CS as a different language to reproduce the world and they just reproduce what they know instead of thinking in the new ways.Bobnoreply@blogger.comtag:blogger.com,1999:blog-18677687.post-10524330752777820262015-02-08T19:15:05.210-05:002015-02-08T19:15:05.210-05:00The problem isn't in the question -- the quest...The problem isn't in the question -- the question simply asks you to "unfold" code, and in the real world, you are often going to be faced with debugging or maintaining other people's sub-optimal solutions.<br /><br />The problem is far more subtle: within teaching, there's a tendency to deny reality, and claim that test questions aren't a model for teaching. They <i>shouldn't</i> be, that much is true, but the practical reality is that a teacher's first priority is almost always to get the students ready for the exam.<br /><br />When the questions are at that basic a level, it can be assumed you're not going to have had enough time to work through the volume of examples needed to get an innate understanding of the pattern, so that leads into rote teaching...Titchhttps://www.blogger.com/profile/03003350618976942468noreply@blogger.comtag:blogger.com,1999:blog-18677687.post-82364100234674179612015-02-08T17:38:51.930-05:002015-02-08T17:38:51.930-05:00Ummm.... printing numbers from 0 to n is a stupid ...Ummm.... printing numbers from 0 to n is a stupid and unrealistic problem, REGARDLESS of whether you're using iteration or recursion. It's completely devoid of any practicality in any case (ref. Astrachan's Law), but as impractical code that potentially makes students understand a process it certainly has value. You could reverse the order of the print and the recursive call and ask the same question again - that gets at a very important question and insight for students.<br /><br />But again, I think complaining about how it's a silly way to code something when it's not something people would actually code anyway (iteratively or recursively) doesn't make sense.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-18677687.post-27569323656532812302015-02-08T17:10:56.935-05:002015-02-08T17:10:56.935-05:00I appreciate the heads up on the don't doesn&#...I appreciate the heads up on the don't doesn't typo. Thanks.Alfred C Thompson IIhttps://www.blogger.com/profile/06011086242006020298noreply@blogger.comtag:blogger.com,1999:blog-18677687.post-35684863491504378622015-02-08T17:06:13.484-05:002015-02-08T17:06:13.484-05:00I agree it is a silly question, however it checks ...I agree it is a silly question, however it checks understanding the concept. What would be a better question?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-18677687.post-14823481904915777262015-02-08T16:57:09.313-05:002015-02-08T16:57:09.313-05:00Says the person who writes "That don’t make ...Says the person who writes "That don’t make it a good way" 8-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-18677687.post-46249174160579016482015-02-08T16:35:24.309-05:002015-02-08T16:35:24.309-05:00try ackermann function.
You cant use loops on it ...try ackermann function.<br /><br />You cant use loops on it since it is double recursion.<br /><br />A(m,n) =<br />n+1 if m==0<br />A(m-1,1) if m > 0 && n == 0<br />A(m-1,A(m,n-1)) if m>0 and n>0Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-18677687.post-86673182208517524792015-02-08T15:57:30.522-05:002015-02-08T15:57:30.522-05:00When n is negative the two results are different.When n is negative the two results are different.Clarence Odbodynoreply@blogger.comtag:blogger.com,1999:blog-18677687.post-43837387478999709822015-02-08T15:23:39.090-05:002015-02-08T15:23:39.090-05:00I think that problems with understanding basic rec...I think that problems with understanding basic recursion often are caused by misconceptions about scope, but understanding scope is pretty fundamental, and actually not that complicated, so it's probably good to learn it correctly early on, and then IMO basic recursion is just a good test for having understood scoping.<br /><br />Maybe the problem is with introducing recursion via stacks? That is just an implementation detail of some (well, many ;-) compilers and interpreters and as such maybe simply isn't necessary to explain at that point? After all, you probably also don't explain, I dunno, dynamic linker trampolines? You just introduce how to call a "built-in function" without worrying how the system performs that function call.<br /><br />Also, explaining such high-level concepts in terms of common implementation techniques seems to me to bear the risk of making people think too much in terms of those rather than at the abstract level. In the specific case of recursion, Scheme, for example, guarantees tail call optimization, so in tail-recursive code, the implementation probably won't even use a stack when executing the recursive call--however, scoping still works exactly as you would expect, of course.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-18677687.post-83434122052580687782015-02-08T15:22:53.601-05:002015-02-08T15:22:53.601-05:00I am perfectly fine on this question IFF you inclu...I am perfectly fine on this question IFF you included a second question:<br /><br /><br />1. What is the result when printNumber(6) is called?<br />2. What is the result when printNumber(6000000) is called? Explain the difference.<br /><br />The answer to #2 is of course, "SYSTEM CRASH! STACK OVERFLOW" etc.<br /><br />I woud argue that the issue isn't about right and wrong, but about understanding both aspects of the problem, as demonstrated by #2. A "good programmer" knows both methods (ie, recursion and loops) and uses both (wisely).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-18677687.post-84360186660239408122015-02-08T15:16:59.182-05:002015-02-08T15:16:59.182-05:00I fixed the error in the sample code. Thanks for t...I fixed the error in the sample code. Thanks for the catch Robo.Alfred C Thompson IIhttps://www.blogger.com/profile/06011086242006020298noreply@blogger.comtag:blogger.com,1999:blog-18677687.post-14626539575375338462015-02-08T15:15:09.975-05:002015-02-08T15:15:09.975-05:00http://en.wikipedia.org/wiki/Tail_call
That's...http://en.wikipedia.org/wiki/Tail_call<br /><br />That's the reason why recursion in functional programming languages and several other imperative languages "Just Works" and don't use the stack.John Bokmahttp://johnbokma.comnoreply@blogger.comtag:blogger.com,1999:blog-18677687.post-11704044625481238002015-02-08T15:08:22.497-05:002015-02-08T15:08:22.497-05:00for (int i = 0; i <= n; i++) System.out.print(n...for (int i = 0; i <= n; i++) System.out.print(n);<br /><br />Is a lot easier.<br />But it doesn't give the same answer<br /><br />Unless you mean;<br />for (int i = 0; i <= n; i++) System.out.print(i);<br /><br />or even easier;<br />10 print "0123456"<br /><br /><br />Robohttps://www.blogger.com/profile/13528181899988384630noreply@blogger.com