Recursion—Defining a subroutine in terms of itself. The subroutine calls itself.
Recursion ≠ iteration
Danger: the call stack may be exhausted
The call stack is a stack onto which we place a new stack frame each time a new subroutine is called. The stack frame contains information such as:
- the state of each variable in the calling subroutine
- a return address to start executing once the called subroutine is finished