Recursion Flashcards
What is a recursive subroutine?
A subroutine which is defined within itself, and calls itself.
What must all recursive subroutines have?
A base case (stopping condition), met at some point in the execution of the program.
What happens if a subroutine calls itself without a base case?
It will never terminate, infinitely looping which will lead to a stack overflow error due to more and more stack frames being pushed onto the call stack.
What other way can a problem often be solved if it can be solved recursively?
Through iteration.
What is the main difference between recursion and iterative solution?
Iterative solutions are often easier to program, whereas recursive ones are more compact in code.
What happens when you call a recursive subroutine?
The program counter and all local variables are pushed onto the stack.
What happens when you return a value from a recursive subroutine?
The stack is popped restoring the program counter and local variables.
What is a program counter?
A pointer storing the line number of the next instruction.
What are some pros of using recursion?
- Simplified code
- Reduced code length
- Intuitive for Tree and Graph problems
What are some cons of using recursion?
- Higher memory usage
- Difficult to debug
- Limited by stack size
- Less control over execution
- Risk of infinite recursion
What is an alternative method of solution achieving the same functionality of recursion?
Iteration.
What are some uses of recursion?
- Traversing hierarchical structures
- Divide-and-conquer algorithms
- Backtracking problems
- Fractals and mathematical problems