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