*********
Recursion
*********

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

Recursive Algorithm
===================
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.

Key components
--------------
#. Base case - the case that the problem can be solved without reusing itself
#. Recursive rule - the rule to reduce the problem toward the base case

Function Call Mechanism
-----------------------
+ 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.

Recursive function in C++
-------------------------
+ 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
  }

Complexity analysis
-------------------

+ number of recurve calls :math:`\times` total resource in each iteration
+ recursion tree to visually assist the analysis

Recursive Data Structure
========================
Recursive Data Structure in C++
-------------------------------
+ A class holds instance or pointer/reference to instance of its own type
+ E.G. Linked-list
+ E.G. Tree, directory structure

Pitfall
=======
+ missing base case
+ recursive rule does not reduce toward the base case
+ skipped base case