tag:blogger.com,1999:blog-2564777502681463717.post2532658920263058700..comments2018-09-12T06:38:12.634-04:00Comments on Teaching, Playing, and Programming: Hey, you got your loop in my recursion!Chris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-2564777502681463717.post-18348032324743854402010-08-24T15:28:01.714-04:002010-08-24T15:28:01.714-04:00In that case, why not start with trees, to get peo...In that case, why not start with trees, to get people comfortable with using recursion first? Or is this a first course on programming?Zacharyhttps://www.blogger.com/profile/06055515765180704709noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-55689948144362532012008-09-19T12:55:00.000-04:002008-09-19T12:55:00.000-04:00I think examples like this throw students of recur...I think examples like this throw students of recursion off because the recursive solution isn't obviously better than the iterative solution. It's when you get into traversing data structures like trees (or applications of such, like parsing) that suddenly recursion makes sense. It allows you to use the call stack instead of having to manage your own stack. The recursive algorithm is obviously simpler. In the list example, recursion is actually a bad idea, because with a long enough list (and without some form of optimized tail recursion) you'll blow your call stack. That can be tough for beginners to debug.Chip Overclockhttps://www.blogger.com/profile/11195242013008369733noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-71078981882737389762008-09-16T12:03:00.000-04:002008-09-16T12:03:00.000-04:00maybe, introduce recursion by starting with functi...maybe, introduce recursion by starting with functions on trees (height, maximum, number of nodes,...) <BR/>this will have the advantage that there is no obvious way of doing this with iteration, and then when recursion is understood, one can point out that that list fns can also be defined this way.harshahttps://www.blogger.com/profile/05812023360605459339noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-35514767532110048442008-09-15T15:24:00.000-04:002008-09-15T15:24:00.000-04:00I very much appreciate trying to distill some help...I very much appreciate trying to distill some helping rule-of-thumb from all the examples you've encountered; such rules help me learn and grow.<BR/><BR/>It would be great if there were a good repository of such things, both for teachers-of-others and also auto-didacts.Raoul Dukehttps://www.blogger.com/profile/07354740962526930549noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-78002907783583824582008-09-14T18:18:00.000-04:002008-09-14T18:18:00.000-04:00@rgrig: It depends on the course. When I'm teachi...@rgrig: It depends on the course. When I'm teaching the first or second course where they see recursion, I certainly provide more explicit structure along the lines of what you suggest.<BR/><BR/>But more often, I'm teaching a course where they've seen recursion in either three or four previous courses. Then I'm more likely to provide a brief review of how to design a recursive algorithm, and go through an example or two, before asking them to do a similar example. For example, I might go through a recursive length function and then ask them to do a recursive sum function.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-90252855333950116322008-09-14T17:38:00.000-04:002008-09-14T17:38:00.000-04:00If I would have been told that a function is recur...If I would have been told that a function is <I>recursive</I> when it calls itself and then asked to compute the length of a list using a recursive function I would have probably been stumped.<BR/><BR/>Fortunately I've first been exposed to recursive definitions of all kinds of sets in math and, once I recognized that trees are basically the same, it was easy to see how (some) recursions work.<BR/><BR/>I think the goal is to have students to <I>choose</I> recursion as being most natural solution to a problem you pose. Did you try something like the following?<BR/><BR/>A list is either empty or contains one element and a smaller list. Here are some examples. Now suppose we have to compute the length of a list. Could you do it assuming that you already have a function that computes the length of the smaller list?rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-47329414597250729662008-09-14T14:28:00.000-04:002008-09-14T14:28:00.000-04:00@ animesh : Your function doesn't make sense, ...@ animesh : Your function doesn't make sense, it will do absolutely anything but give the sum of the element of the list passed to the function... Besides it won't even give the same result with the same input (because $sum is global, you should never use global vars in Perl except if you know what you're doing).<BR/><BR/>A correct function would be :<BR/><BR/>sub sum {<BR/> if(@_) {<BR/> my $n = shift;<BR/> return $n + sum(@_);<BR/> }<BR/> else {<BR/> return 0;<BR/> }<BR/>}<BR/><BR/>or if you wanted a tail recursive function :<BR/><BR/>sub sum {<BR/> my $acc = 0;<BR/> sum_aux($acc, @_);<BR/>}<BR/><BR/>sub sum_aux {<BR/> my $acc = $_[0];<BR/> if(@_ > 1) {<BR/> my $n = pop;<BR/> $_[0] = $acc + $n;<BR/> goto &sum_aux;<BR/> }<BR/> else {<BR/> return $acc;<BR/> }<BR/>}<BR/><BR/>Though passing the array by reference is much better performance-wise :<BR/><BR/>sub sum {<BR/> my $acc = 0;<BR/> sum_aux($acc, @_);<BR/>}<BR/><BR/>sub sum_aux {<BR/> my $acc = $_[0];<BR/> if(@{$_[1]}) {<BR/> my $n = pop @{$_[1]};<BR/> $_[0] = $acc + $n;<BR/> goto &sum_aux;<BR/> }<BR/> else {<BR/> return $acc;<BR/> }<BR/>}<BR/><BR/>(be careful with this version since the referenced array is modified, to call it without disturbing the argument, you have to copy it yourself with something like sum([@arr]) )Chaddaïhttps://www.blogger.com/profile/16447976353069828503noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-69944091078666017622008-09-14T13:09:00.000-04:002008-09-14T13:09:00.000-04:00In PERL, does the following sound fine?sub rec { ...In PERL, does the following sound fine?<BR/><BR/>sub rec {<BR/> $n = shift;<BR/> if($n>0){<BR/> $sum+=($n);<BR/> $n--;<BR/> (rec($n));<BR/> }<BR/> return $sum;<BR/>}<BR/><BR/>Or I can get rid of variable $sum too?Animesh Sharmahttps://www.blogger.com/profile/07485653184282867837noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-36194406152259968802008-09-13T14:57:00.000-04:002008-09-13T14:57:00.000-04:00When I was first learning about functional program...When I was first learning about functional programming and it's heavy use of recursion, one small example really helped me bend my mind around the whole new way of thinking. It was written in Scheme and was a small function for computing the length of a list ... Here it is (if you'll pardon my lisp):<BR/><BR/>(def len (my-list)<BR/> (eq? (my-list ())<BR/> 0<BR/> (+ 1 (len (cdr my-list)))))<BR/><BR/>This totally changed my way of thinking about recursion ... Anyways, I kept it in the back of my head ever since and it helped quite a lot :Phoria314https://www.blogger.com/profile/12405514858485175201noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-21852357671095541732008-09-13T13:47:00.000-04:002008-09-13T13:47:00.000-04:00I completely share Jason opinion ! As a developer ...I completely share Jason opinion ! As a developer I much prefer a stack overflow to an infinite loop and even as an user I positively hate the programs that fail to fail or succeed and just heat my cpu for nothing...Chaddaïhttps://www.blogger.com/profile/16447976353069828503noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-60594311134249809192008-09-13T13:37:00.000-04:002008-09-13T13:37:00.000-04:00@lalala: A tail-recursive version with an explicit...@lalala: A tail-recursive version with an explicit accumulator is great, but it's a step that most beginners just aren't going to take on their own. If you ask them to write it that way in the first place, that's one thing, but if you ask them to write a sum function that simply takes a list, they will very rarely think of writing a helper function that takes both a list and a number. At least not until they've already seen that patter a couple of times.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-63682746056419581922008-09-13T13:21:00.000-04:002008-09-13T13:21:00.000-04:00This comment has been removed by the author.jrockwayhttps://www.blogger.com/profile/06224927170245069942noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-79183462804505049032008-09-13T13:01:00.000-04:002008-09-13T13:01:00.000-04:00@wolterYou would rather have a non-terminating loo...@wolter<BR/><BR/>You would rather have a non-terminating loop than bottom out your recursion stack? Sorry, but you're flat-out wrong. Failing as loudly and as obviously as possible is always preferable to ambiguity. <BR/><BR/>Hitting the bottom of your recursion stack segfaults the program or throws an exception (dep. on language), meaning pagers go off and you can get to work fixing the problem. Non-terminating loops just look like code that's taking a really long time to complete.<BR/><BR/>And in more modern languages, you can usually recover from recursing too deeply with a simple top-level exception handler. Being safe against non-terminating loops, otoh, requires multiple threads and no actual guarantees (you have to guess at how long a loop should run before giving up on it).Jasonhttps://www.blogger.com/profile/15925896326631717517noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-54051846753222852412008-09-13T12:14:00.000-04:002008-09-13T12:14:00.000-04:00You should pass an accumulator to the recursive fu...You should pass an accumulator to the recursive function to make it tail-recursive and avoid putting a huge number of function calls on the stack:<BR/><BR/>def sum(list):<BR/> rsum(list, 0)<BR/><BR/>def rsum(list, acc):<BR/> if len(list) == 0:<BR/> return acc<BR/> else:<BR/> acc = acc + list.pop()<BR/> return rsum(list, acc)<BR/><BR/>If your compiler does tail calls optimization correctly, this should be at least as efficient as a C for loop.lalalahttps://www.blogger.com/profile/05503697385450790146noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-70049840685117444212008-09-13T11:24:00.000-04:002008-09-13T11:24:00.000-04:00don't let them define any variables! All variables...don't let them define any variables! All variables must be parameters!<BR/><BR/>Problem solved.<BR/><BR/>Also, read SICPlearnsicphttps://www.blogger.com/profile/08111904749174572310noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-33017499106993057412008-09-13T10:49:00.000-04:002008-09-13T10:49:00.000-04:00While recursion does have its strengths, in most s...While recursion does have its strengths, in most situations it can just as easily be implemented through iteration, and the "blowuppiness" of a messed up termination condition makes it less attractive than the iterative alternative (stack overflow vs a non-terminating loop).<BR/><BR/>I would agree, however, that any self respecting software engineer should know how to implement both, and when one is better than the other.Wolterhttps://www.blogger.com/profile/15099002911138835539noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-51755247002886059452008-09-13T10:09:00.000-04:002008-09-13T10:09:00.000-04:00The trivial change is this: function sum(list) i...The trivial change is this:<BR/><BR/> function sum(list) is<BR/> if list = null then<BR/> return 0<BR/> else<BR/> return list.item + sum(list.next)<BR/><BR/>For an exercise like this, I'd ask them to do it on paper first - I think a lot of people 'get' recursion far faster when they've got a way to visualize whats happening.Edhttps://www.blogger.com/profile/17054315827168499437noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-37328142894877574702008-09-13T10:02:00.000-04:002008-09-13T10:02:00.000-04:00I never use recursion as it usually makes my head ...I never use recursion as it usually makes my head hurt; however you inspired me to try and make a sum-of-elements-in-a-list recursively...<BR/><BR/>def sum(arr)<BR/> return 0 if arr.empty?<BR/> return arr.pop + sum(arr)<BR/>end<BR/><BR/>Yes, it's destructive, but having to think recursively is hard for me. Usually if I find myself in recursive code I refactor it into an iterative loop, I could learn to gain from a greater understanding methinks.Glenn Francis Murrayhttps://www.blogger.com/profile/11258496854058381722noreply@blogger.com