Testing students on recursion - tracing by hand

Question

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.

Answer 1

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.

Answer 2

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.