Recursion

Recursion is a way of solving problems by breaking them down into smaller, self-similar versions of the same problem. You have likely seen it before, but its true power becomes apparent when dealing with complex data structures or “divide and conquer” algorithms, where an iterative solution can be much harder to implement.

Every recursive function has (at minimum) two parts. A base case, and a recursive case. The base case is intended to solve the smallest possible form of the problem. The recursive case is intended to do a very small amount of work, and then solve a slightly smaller version of the problem by calling the function again.

As an illustration, consider calculating the factorial of a number, \(x!\) (as a reminder, \(4! = 4 \times 3 \times 2 \times 1\). Also, \(0!=1\).). The key thing to note that makes this natural for recursion is that \(x! = x \times (x-1)!\). So, imagine we are writing a function called fact(x) which is intended to calculate this value. Of course we could do it iterative, but we can also approach it recursively:

def fact(x):
  if x == 0:          #base case
    return 1
  return x*fact(x-1)  #recursive case

There are many (many!) data structures problems where a recursive approach is more natural than an iterative approach.

Binary Search

Let’s look at one more non-data-structures problem where we can use recursion, binary search. Recall the iterative version:

def binary_search_iterative(L, to_find):
    low = 0
    high = len(L)

    while high-low > 0
        mid = int( (low + high) / 2)
        if L[mid] > to_find:
            high = mid
        else:
            low = mid
    return L[low]==to_find

The key insight is that binary search is fundamentally recursive: To do binary search on a chunk of a list, you check the middle, and then do binary search on the relevant half. When a problem’s definition is inherently recursive, a recursive solution is often the most elegant.

def binary_search(L, to_find, low, high):
    if high-low == 1:
        return L[low]==to_find
    mid = int( (high+low) / 2)
    if L[mid]> to_find:
        return binary_search(L, to_find, low, mid)
    return binary_search(L, to_find, mid, high)

Most would agree this recursive version is cleaner and more closely matches the definition of the algorithm.

Recursion on Linked Lists

Linked structures are another area where recursion often works better than iteration. You can think of a linked list as being a Node, which points to another linked list. In that sense, linked lists tasks can be often thought of as, “does this Node have what I need? No? OK, call this function again at the linked list starting at next.”

Let’s start by just printing every element of a linked list:

def printAll(head):
  if head is None:
    return
  print(head.data)
  printAll(head.next)

Just like how you should be good at the iterative version of cycling through a linked list, you should be good at the recursive version, too:

def iterative(self):
  tempVar = self.head
  while tempVar is not None:
    # do something with the Node indicated by tempVar
    tempVar = tempVar.next

def recursive(self, head):
  if head is None: #if we're off the back of the linked list
    return
  # do something with the Node indicated by head
  recursive(head.next)

Let’s say we want to insert a new number into a sorted linked list while maintaining the order. An iterative approach can be tricky.

First Iterative Attempt:

# This version has a bug
def insert_iterative_v1(self, num):
    # ... (code for inserting at head) ...
    
    # Find the insertion point
    current = self.head
    while current is not None and current.data < num:
        current = current.next # Advance the pointer
    
    # Now 'current' is where we want to insert, but we've lost the previous node
    new_node = Node(num)
    new_node.next = current
    # ??? = new_node  <-- How do we link the previous node to new_node?

By advancing our pointer to the insertion spot, we lose the reference to the previous node, which we need to modify.

Second Iterative Attempt: To fix this, we can look ahead before advancing the pointer.

# This version is better, but still has issues
def insert_iterative_v2(self, num):
    # ... (code for inserting at head) ...

    current = self.head
    # Look ahead to find the spot
    while current.next is not None and current.next.data < num:
        current = current.next
        
    new_node = Node(num)
    new_node.next = current.next
    current.next = new_node

This is better, but what happens if we need to insert at the very end of the list? The condition current.next.data will fail when current.next is None. Handling all these edge cases (empty list, insert at head, insert in middle, insert at end) makes iterative code complex.

Recursive Solution: Now, let’s try it with recursion. The function will take a node as an argument and return the head of the (potentially modified) list starting from that node.

# This function would be a helper called by a public method
def _insert_recursive(self, num, current_node):
    # Base Case 1: The list is empty (or, we've reached the end of the list). Insert the new node here.
    if current_node is None:
        return Node(num)
    
    # Base Case 2: Found the correct spot. Insert the new node before the current one.
    if current_node.data > num:
        new_node = Node(num)
        new_node.next = current_node
        return new_node
    
    # Recursive Step: The spot is further down. Recur on the rest of the list.
    # The link of the current node is set to the result of the recursive call.
    current_node.next = self._insert_recursive(num, current_node.next)
    return current_node

# Public-facing method to start the recursion
def insert(self, num):
    self.head = self._insert_recursive(num, self.head)

This recursive version elegantly handles all cases (empty list, head, middle, and end) without complex conditional logic. The state is managed through the call stack, resulting in cleaner, more declarative code.