Answers.Body: <h2>No</h2>
  
  <p>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.</p>
  
  <h2>Yes</h2>
  
  <p>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.</p>
  
  <p>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. </p>
  
  <p>Nether of you examples would allow for tail-call optimisation: </p>
  
  <ul>
  <li>The first is not linearly-recursive, but as long as the input data is small, would not be a problem. </li>
  <li>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.</li>
  </ul>
  
  <hr>
  
  <p>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. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-26T10:58:19.427Z
Answers.Text: 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.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-26T12:24:11.527Z
Answers.Text: @Buffy that is an implementation detail of the language/compiler. C++, Eiffel and some others can do tail-call optimisation.
Answers.UserDisplayName: ctrl-alt-delor
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-26T12:27:07.770Z
Answers.Text: 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.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-26T12:37:03.003Z
Answers.Text: `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...)
Answers.UserDisplayName: ItamarG3
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-26T12:37:45.503Z
Answers.Text: @Buffy Eiffel optimises out polymorphic calls, if not need. C++ allows you to choose (but not at the correct part of the design, yuck). However it does not seem as hard as it may seem: If I am called polymorphicly, then call my self, then I am referring to my self, not a different version of my self (the type of `this` can not change. Once I am called the type of this is determined, therefore all calls to ones own methods could be done staticly ).
Answers.UserDisplayName: ctrl-alt-delor
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-26T12:40:20.460Z
Answers.Text: @ItamarG3 If we are not setting them up to design, then what are we doing? (If we just test some abstract thing, for no reason, then we have people that know something well, but have no use for it.)
Answers.UserDisplayName: ctrl-alt-delor
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-26T12:41:23.000Z
Answers.Text: 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.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-26T09:30:00.317Z
Answers.LastActivityDate: 2017-07-26T09:30:00.317Z
Answers.UserDisplayName: ctrl-alt-delor
Answers.Body: <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-28T03:12:53.773Z
Answers.Text: 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.)
Answers.UserDisplayName: Wildcard
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-26T13:11:38.223Z
Answers.LastActivityDate: 2017-07-26T13:11:38.223Z
Answers.UserDisplayName: Edwin Torres
Body: <p>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.<br>
  All tests are written on paper, but the questions on the test are subject to changes, and those are the changes being asked about.</p>
  
  <p>These students are in a CS major in High School.</p>
  
  <p>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).</p>
  
  <p>For example:</p>
  
  <pre><code>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 &lt; n; i++)
              sum+=permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
          return sum;
      }
  }
  </code></pre>
  
  <p>and it is called in some <code>main</code>:</p>
  
  <pre><code>public static void main(String[] args) {
      System.out.println(permutation("", "abcde"));
  }
  </code></pre>
  
  <p>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)</p>
  
  <p><a href="https://i.sstatic.net/FwMn5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FwMn5.png" alt="recursive tracing"></a></p>
  
  <p>They essentially trace the call stack (and they know this; they know that effectively that's what they are doing).</p>
  
  <p>However, I have some doubts about this method of testing (specifically the tracing).</p>
  
  <p>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?</p>
  
  <p>If not, then how else can their knowledge of recursion be tested in a written test?</p>
  
  <p>The tests are given because that's how the students are taught:</p>
  
  <ul>
  <li>They study a subject (in this case, recursion)</li>
  <li>they are tested on that subject.</li>
  </ul>
  
  <p>There's no bigger goal, no project that they use it in (yet). They learn it because it's part of the curriculum.</p>
  
  <p><strong>Clarification</strong></p>
  
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-26T09:17:31.960Z
Comments.Text: What language is your example in?
Comments.UserDisplayName: ctrl-alt-delor
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-26T09:18:16.427Z
Comments.Text: @richard java... but that's not what the question is about.
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-26T11:03:51.880Z
Comments.Text: 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.
Comments.UserDisplayName: Buffy
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-26T11:24:04.230Z
Comments.Text: @Buffy I'm sorry, I don't quite understand the difficulty. The example is just one for them to trace.
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-26T11:55:44.977Z
Comments.Text: 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.
Comments.UserDisplayName: Buffy
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-26T12:07:12.230Z
Comments.Text: @Buffy that's the point. The students supposedly trace the execution of the function, and from that they understand what it does.
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-26T12:21:57.880Z
Comments.Text: Hmmm. Why not [ackermann](https://en.wikipedia.org/wiki/Ackermann_function)(3, 2)?
Comments.UserDisplayName: Buffy
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-26T12:27:04.280Z
Comments.Text: @Buffy better? The question isn't about that specific example, but rather about the effectiveness of testing recursion knowledge like this.
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-26T16:29:55.530Z
Comments.Text: Why not have them identify the base case(s) and/or explain why a function will (or won't) always reach the base case? Tracing the stack only shows they understand function calls. Understanding recursion requires understanding that every function call always works towards some base case, so test them on that instead.
Comments.UserDisplayName: Kyle G
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-26T16:45:30.763Z
Comments.Text: @KyleGullion the question isn't about teaching recursion. It's about whether the described test method (on an exam) would actually be able to test the students' knowledge about recursion.
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-22T16:52:47.247Z
Comments.Text: That seems like a really strange function to me. You're computing an int, and printing the permutation. Given the name I'd expect it to return a permutation string or set or something. Bad code! Bad code!
Comments.UserDisplayName: Victor Eijkhout
Tags: <secondary-education><grading><recursion><exams>
Title: Testing students on recursion - tracing by hand
ThreadText: # Testing students on recursion - tracing by hand
  
  (Asked by: username_0 on 2017-07-26)
  
  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)
  
  [![recursive tracing](https://i.sstatic.net/FwMn5.png)](https://i.sstatic.net/FwMn5.png)
  
  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.
  
  **Tags:** secondary-education, grading, recursion, exams
  
  > **Comments:**
  > **username_1**: What language is your example in?  
  > **username_0**: @richard java... but that's not what the question is about.  
  > **username_2**: 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.  
  > **username_0**: @username_2 I'm sorry, I don't quite understand the difficulty. The example is just one for them to trace.  
  > **username_2**: 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.  
  > **username_0**: @username_2 that's the point. The students supposedly trace the execution of the function, and from that they understand what it does.  
  > **username_2**: Hmmm. Why not [ackermann](https://en.wikipedia.org/wiki/Ackermann_function)(3, 2)?  
  > **username_0**: @username_2 better? The question isn't about that specific example, but rather about the effectiveness of testing recursion knowledge like this.  
  > **username_3**: Why not have them identify the base case(s) and/or explain why a function will (or won't) always reach the base case? Tracing the stack only shows they understand function calls. Understanding recursion requires understanding that every function call always works towards some base case, so test them on that instead.  
  > **username_0**: @KyleGullion the question isn't about teaching recursion. It's about whether the described test method (on an exam) would actually be able to test the students' knowledge about recursion.  
  > **username_4**: That seems like a really strange function to me. You're computing an int, and printing the permutation. Given the name I'd expect it to return a permutation string or set or something. Bad code! Bad code!  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2017-07-26. Score: 4
  
  ## 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.
  
  > **Comments:**
  > **username_2**: 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.  
  > **username_1**: @username_2 that is an implementation detail of the language/compiler. C++, Eiffel and some others can do tail-call optimisation.  
  > **username_2**: 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.  
  > **username_0**: `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...)  
  > **username_1**: @username_2 Eiffel optimises out polymorphic calls, if not need. C++ allows you to choose (but not at the correct part of the design, yuck). However it does not seem as hard as it may seem: If I am called polymorphicly, then call my self, then I am referring to my self, not a different version of my self (the type of `this` can not change. Once I am called the type of this is determined, therefore all calls to ones own methods could be done staticly ).  
  > **username_1**: @username_0 If we are not setting them up to design, then what are we doing? (If we just test some abstract thing, for no reason, then we have people that know something well, but have no use for it.)  
  > **username_2**: 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.  
  
  ---
  
  ### Answer by username_5 on 2017-07-26. Score: 0
  
  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.
  
  > **Comments:**
  > **username_6**: 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.)  
  
  ---
  
  