I've written before about trying to diagnose students' broken or ineffective mental models from the mistakes they make. Here's a mistake that I see frequently from students who are not yet comfortable with recursion.
Say you wanted to write a function to calculate the sum of a list using a loop. Many students could easily write something like
function sum(list) is
variable total := 0
while list /= null do
total := total + list.item
list := list.next
return total
But ask them to write the sum function using recursion, and you might get something like
function sum(list) is
variable total := 0
if list = null then
return total
else
total := total + list.item
return sum(list.next)
Of course, this code always returns 0. It's pretty clear that the writer had the
iterative algorithm in mind, and doesn't understand that each recursive call to sum creates a new instance of the total variable.
When I watch such a student writing code like this, he often declares the variable immediately, before even beginning to think about what the recursive decomposition is going to look like, an almost spinal reflex conditioned by several semesters of writing loops. I can explain recursion until I'm hoarse and draw pictures until my hand cramps up, but I can't compete with the will-o'-the-wisp allure of that variable. Once it's there, it will almost inevitably lead the student to his doom in the bogs of iterative thinking.
One trick to help such a student is to break the cycle where it begins, by getting rid of that variable. Tell him to write the function without using any local or global variables. Or, if he really thinks he needs a variable, to declare it as a constant instead. Of course, there are times when a variable is perfectly appropriate inside a recursive function, but such examples can often be avoided until the student has a better grasp of recursion.
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...
ReplyDeletedef sum(arr)
return 0 if arr.empty?
return arr.pop + sum(arr)
end
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.
The trivial change is this:
ReplyDeletefunction sum(list) is
if list = null then
return 0
else
return list.item + sum(list.next)
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.
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).
ReplyDeleteI would agree, however, that any self respecting software engineer should know how to implement both, and when one is better than the other.
don't let them define any variables! All variables must be parameters!
ReplyDeleteProblem solved.
Also, read SICP
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:
ReplyDeletedef sum(list):
rsum(list, 0)
def rsum(list, acc):
if len(list) == 0:
return acc
else:
acc = acc + list.pop()
return rsum(list, acc)
If your compiler does tail calls optimization correctly, this should be at least as efficient as a C for loop.
@wolter
ReplyDeleteYou 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.
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.
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).
This comment has been removed by the author.
ReplyDelete@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.
ReplyDeleteI 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...
ReplyDeleteWhen 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):
ReplyDelete(def len (my-list)
(eq? (my-list ())
0
(+ 1 (len (cdr my-list)))))
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 :P
In PERL, does the following sound fine?
ReplyDeletesub rec {
$n = shift;
if($n>0){
$sum+=($n);
$n--;
(rec($n));
}
return $sum;
}
Or I can get rid of variable $sum too?
@ 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).
ReplyDeleteA correct function would be :
sub sum {
if(@_) {
my $n = shift;
return $n + sum(@_);
}
else {
return 0;
}
}
or if you wanted a tail recursive function :
sub sum {
my $acc = 0;
sum_aux($acc, @_);
}
sub sum_aux {
my $acc = $_[0];
if(@_ > 1) {
my $n = pop;
$_[0] = $acc + $n;
goto &sum_aux;
}
else {
return $acc;
}
}
Though passing the array by reference is much better performance-wise :
sub sum {
my $acc = 0;
sum_aux($acc, @_);
}
sub sum_aux {
my $acc = $_[0];
if(@{$_[1]}) {
my $n = pop @{$_[1]};
$_[0] = $acc + $n;
goto &sum_aux;
}
else {
return $acc;
}
}
(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]) )
If I would have been told that a function is recursive when it calls itself and then asked to compute the length of a list using a recursive function I would have probably been stumped.
ReplyDeleteFortunately 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.
I think the goal is to have students to choose recursion as being most natural solution to a problem you pose. Did you try something like the following?
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?
@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.
ReplyDeleteBut 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.
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.
ReplyDeleteIt would be great if there were a good repository of such things, both for teachers-of-others and also auto-didacts.
maybe, introduce recursion by starting with functions on trees (height, maximum, number of nodes,...)
ReplyDeletethis 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.
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.
ReplyDeleteIn that case, why not start with trees, to get people comfortable with using recursion first? Or is this a first course on programming?
ReplyDelete