Most common mistakes students make when writing recursive programs
- 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.
- 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.
- 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)
- 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!
