# Testing students on recursion - tracing by hand

After learning recursion in class, students take a test (a few lessons for teaching the subject, and then a test), and are then given a grade. The test is on paper, and I can't change that fact.
All tests are written on paper, but the questions on the test are subject to changes, and those are the changes being asked about.

These students are in a CS major in High School.

Besides asking them to write recursive functions for a variety of purposes (tree traversal\search etc.), their knowledge is also tested by asking them to trace by hand (on paper, without a computer) a given recursive function (usually one that does string manipulations).

For example:

public static int permutation(String prefix, String str){
int n = str.length();
if (n == 0) {
System.out.println(prefix);
return 1;
}
else {
int sum=0;
for (int i = 0; i < n; i++)
sum+=permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
return sum;
}
}


and it is called in some main:

public static void main(String[] args) {
System.out.println(permutation("", "abcde"));
}


This is an example for how their tracing should look like (this image is not related to the permutation example above, but it serves to explain how they trace the recursion)

They essentially trace the call stack (and they know this; they know that effectively that's what they are doing).

However, I have some doubts about this method of testing (specifically the tracing).

So, would testing students like this be useful? By that I mean: does it actually indicate understanding of recursion and\or increase their ability to understand recursive functions they see?

If not, then how else can their knowledge of recursion be tested in a written test?

The tests are given because that's how the students are taught:

• They study a subject (in this case, recursion)
• they are tested on that subject.

There's no bigger goal, no project that they use it in (yet). They learn it because it's part of the curriculum.

Clarification

My question isn't about teaching recursion, nor is it about the specific example I gave. It's about whether the described test method (on an exam) would actually be able to test the students' knowledge about recursion.

• What language is your example in? Commented Jul 26, 2017 at 9:17
• @richard java... but that's not what the question is about. Commented Jul 26, 2017 at 9:18
• I don't know how to react to this. It seems like obfuscated code to me. There is no indication of the intent of the method, so I can only try to understand it one way - the most detailed possible, non-abstract, way. Is the code given in the test this complex? Give an example from a previous iteration of the test. If you replace the method name with "blah" and it is no harder IMO. Are you trying to teach students to infer intent from code, or trying to teach students to code to implement intent. Commented Jul 26, 2017 at 11:03
• @Buffy I'm sorry, I don't quite understand the difficulty. The example is just one for them to trace. Commented Jul 26, 2017 at 11:24
• Hmmm. Recursion within a loop with no hint about intent other than the method name. I'd rather go to the dentist. Not even a specific invocation on which to hang my hat. Commented Jul 26, 2017 at 11:55

## No

This may be a good way to test understanding of function calls, and the stack. However I don't think it helps much with recursion. As when we design we need to abstract. To do this we need to be able to think without having to keep all of the detail in our heads. We need to focus only on externally visible behaviour, not internal details.

## Yes

Having said that. I think it could be useful to look at the stack, if we are considering the consequences of different algorithms, and recursion patterns.

For example both of your examples, the recursion only reduces by one. Therefore the recursion depth is O(n). If you do not have tail-call optimisation then this could lead to a stack-overflow.

Nether of you examples would allow for tail-call optimisation:

• The first is not linearly-recursive, but as long as the input data is small, would not be a problem.
• The 2nd, has all of the complexity in the return path, and in practice n could be very high. This would be a problem. This example could be rewritten to allow for tail-call optimisation.

Note: Java, C#, Python … do not have tail call optimisation (I heard Java may now have it for direct recursion). C, and C++ may have it (gcc does). Scheme and all functional languages do have it. If your language does not have it. Then a tail-call recursive function can be re-written using the trampoline pattern.

• Recursion in OOP languages is a bit harder to recognize for a compiler. What "looks like" recursion may not be since the receiving object may be different from the sending object and so may have a different implementation of the method. Final methods can be recognized, of course. The problem is made harder by the fact that when a class is compiled it doesn't know which subclasses will exist in the future, nor the "precise" class of the invoking object, as it can be from a subclass. Commented Jul 26, 2017 at 10:58
• @Buffy that is an implementation detail of the language/compiler. C++, Eiffel and some others can do tail-call optimisation. Commented Jul 26, 2017 at 12:24
• I'm pretty sure that it is possible only in certain cases. In the face of polymorphism the compiler doesn't know the code that will be executed and so can't optimize it. Look at what happens in a recursive call from a subclass of the class that defined the method initially. The compiler can't roll the tail recursion into a loop if it the body of the loop doesn't even yet exist. That said, some languages try harder to look for the relevant cases, and some require more of the program to be available at compile time. But dynamic linking makes it a hard problem. Commented Jul 26, 2017 at 12:27
• As when we design we need to abstract. They are not designing. Sure, they might be designing next year, but now they just learnt the subject, and they need to be tested (ministry decision...) Commented Jul 26, 2017 at 12:37
• Probably better discussed in the classroom. However, if "this" is in a subclass and the (superclass) code containing the "this" ref is compiled before the subclass is written, the effect of the call can't be determined at compile time. That is to say, "this" is not an object whose most specific class is the class being compiled. But, as you say, some languages look harder for the possible cases. That is what I said, I think. I haven't looked at the internals of Eiffel. Does it require enough source to build a linkable image? Java does not. Commented Jul 26, 2017 at 12:41

Tracing helps students really understand what's happening in the recursive calls. It's also an important tool for when they develop their own recursive functions. If it helps to trace regular function calls, then it helps to trace recursive ones too.

• I agree with this answer, but it would be more useful if it were expanded beyond a bald statement of opinion. :) (I didn't downvote.) Commented Jul 28, 2017 at 3:12