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

1. Base case - the case that the problem can be solved without reusing itself

2. 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 \(\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 \(\Theta(n)\) and space complexity of \(\Theta(n)\) due to the recursion stack.

Pitfall

• missing base case

• recursive rule does not reduce toward the base case

• skipped base case