*********
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

Example: Recursive Linear Search
=================================
Linear search can be implemented recursively in multiple ways. Here are three
common approaches:

Method 1: Using a Helper Function
----------------------------------
This approach uses a helper function with an additional parameter to track the
current position. The main function provides a clean interface while the helper
function handles the recursion.

::

  // Main function with clean interface
  int searchFirst(int *array, int size, int toSearch) {
    return searchFirstHelper(array, size, toSearch, 0);
  }

  // Helper function that does the actual recursive work
  int searchFirstHelper(int *array, int size, int toSearch, int start) {
    if (start >= size)  // base case: hit the end
      return -1;
    if (array[start] == toSearch)  // base case: found the element
      return start;
    return searchFirstHelper(array, size, toSearch, start + 1);  // recursive rule
  }

Method 2: Using Default Parameters
-----------------------------------
This approach eliminates the need for a helper function by using a default
parameter. This provides a cleaner solution with a single function.

::

  int searchFirst1(int *array, int size, int toSearch, int start = 0) {
    if (start >= size)  // base case: hit the end
      return -1;
    if (array[start] == toSearch)  // base case: found the element
      return start;
    return searchFirst1(array, size, toSearch, start + 1);  // recursive rule
  }

Method 3: Comparing from the End
---------------------------------
This approach compares the tail element in each recursive call and reduces the
array size instead of using an index. This eliminates the need for an extra
parameter.

::

  int searchLast(int *array, int size, int toSearch) {
    if (size == 0)  // base case: empty array
      return -1;
    if (array[size - 1] == toSearch)  // base case: found the element
      return size - 1;
    else
      return searchLast(array, size - 1, toSearch);  // recursive rule
  }

Key Differences
---------------
+ **Method 1**: Most structured; separates interface from implementation.
+ **Method 2**: Most concise; single function with default parameter.
+ **Method 3**: Searches from the end; reduces size instead of incrementing index.

All three methods have the same time complexity of :math:`\Theta(n)` and space
complexity of :math:`\Theta(n)` due to the recursion stack.

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