Testing students on recursion - tracing by hand
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.