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: http://interactivepython.org/courselib/static/pythonds/Recursion/recursionsimple.html

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!