Recursion¶

Definition¶

Defining a problem or an entity in terms of itself. E.g. An ancestor is either parents or parents’ ancestor.

An algorithm that breaks down the problem to smaller pieces and reuses itself to solve sub-problems.

Many algorithms have both recursive and iterative versions. E.G. binary search

FYI: In functional programming, recursion will replace loop/iteration totally.

Each function call creates a new stack frame in the stack memory.
The stack frame contains:
- Function arguments.
- Local variables.
- Return address.
The stack frame is popped out of the stack memory when the function returns.
Stack overflow: When the stack memory is full. Usually caused by infinite recursion.

A function/method calls itself (directly or indirectly).
Forward declaration not mandatory except for mutual recursion (A calls B and B calls A)
Record keeping (parameters, return values, global/dynamic variable)
Helper functions (extra parameters for record keeping)
if statement

int factorial(int n) {
  if (n <= 1) // base case
    return 1;
  return n * factorial(n - 1);  // recursive rule that calls itself
}