Recursion – Misconceptions and Challenges

 Most common mistakes students make when writing recursive programs

  1. Base case for terminating the recursion is missing or is never reached.
    • Make sure the base case exists in the code and it is executed. The base case is typically a conditional statement with a return.
  2. There is recursion related run time error.
    • Each time a recursive call is made, a new “stack frame” is created. Every new stack frame created needs memory. If recursion does not terminate correctly, the program runs out of memory causing a run time error.
    • If the programming environment provides limited memory, a stack overflow error can be triggered even in a correct program.  Test the program on smaller problems sizes and understand why a larger stack is needed. Set system parameters accordingly. Does not happen often in a beginner class.
  3. Program does not terminate
    • Make sure the problem size decreases and there is a correct base case (calls not terminating is a form of an infinite loop)
  4. Slow performance due to excessive re-computations
    • —  See recursive Fibonacci code
    • —  Make sure there are no unnecessary re-computations. In many situations, storing already computed results solves the problem

How to understand recursion

  • Trace the calls to see how the computation done in the program unfolds. Draw a tree structure to represent calls and show what results flow back.
  • Sometimes students gain confidence by working out small examples.
  • Trust the abstraction and that recursion works correctly.
  • Practice and make use of available resources.  Here is a link with additional information on recursion:

 Fully understanding recursion means smiling at the joke that “in order to understand recursion, you must understand recursion.”

  • A recursive function calls itself and thus understanding recursion to understand recursion seems like a call to itself.
  • But, in a recursive program, the problem size decreases and once a base case is reached, no more calls take place. Results are “sent back up” and are combined and the original problem is solved!