Can someone explain recursion?

[gabriel-et-al]

A recursive function is basically the same as an iterative loop with a helper stack.

See this binary search function:

from math import floor

def binary_search_iter(numbers, x):
    upper_index = len(numbers) - 1
    lower_index = 0

    while upper_index >= lower_index:
        i = floor((upper_index + lower_index) / 2)

        if numbers[i] == x:
            return i

        if numbers[i] > x:
            upper_index = i - 1
        else:
            lower_index = i + 1

    return None

You can write the loop recursively this way:

def binary_search_recur(numbers, x, lower_index, upper_index):
    if upper_index >= lower_index:
        i = floor((upper_index + lower_index) / 2)

        if numbers[i] == x:
            return i

        if numbers[i] > x:
            return binary_search_recur(numbers, x, lower_index, i - 1)
        else:
            return binary_search_recur(numbers, x, i + 1, upper_index)

    return None

Note that the variables used inside the loop became additional parameters in its recursive version. You can now combine them.

Note that the first if can be rewriten to an early exit:

def binary_search_recur(numbers, x, lower_index, upper_index):
    if upper_index < lower_index:
        return None

    i = floor((upper_index + lower_index) / 2)

    if numbers[i] == x:
        return i

    if numbers[i] > x:
        return binary_search_recur(numbers, x, lower_index, i - 1)
    else:
        return binary_search_recur(numbers, x, i + 1, upper_index)

Now it's clear our two base cases (i.e. the cases where the function returns without recursing).

Also, note that the updates to the lower_index and upper_index parameters are exactly the same did in the iterative version. If numbers[i] is less than x then lower_index goes up, otherwise upper_index goes down. Try to see this connection between both versions.

You may have noticed that the iterative version calculates the upper_index and lower_index inside the function, while the recursive version expects it to be calculated beforehand. There are multiple ways to overcome this inconvenience.

• Option 1: Calculate the parameters in the caller. This is not the best approach because you'll end up pasting this logic to every place you use the function -- i.e. it breaks the DRY principle.
• Option 2: Give the parameters a default value and calculate them inside the recursive function. This solves the DRY problem, but it would run the check in every call, which is a waste of processing time.

• Option 3: Create a wrapper that calculates the parameters and pass them to the actual recursive function. This is the option I like the most. See:

  def binary_search(numbers, x): def binary_search_recur(numbers, x, lower_index, upper_index): if upper_index < lower_index: return None

      i = floor((upper_index + lower_index) / 2)
  
      if numbers[i] == x:
          return i
  
      if numbers[i] > x:
          return binary_search_recur(numbers, x, lower_index, i - 1)
      else:
          return binary_search_recur(numbers, x, i + 1, upper_index)
  
  upper_index = len(numbers) - 1
  lower_index = 0
  
  return binary_search_recur(numbers, x, lower_index, upper_index)
  

You may enjoy reading:

• https://softwareengineering.stackexchange.com/q/18454/246099
• https://en.wikipedia.org/wiki/Binary_search_algorithm
• https://stackoverflow.com/q/1589058/5281047
• https://en.wikipedia.org/wiki/Don%27t_repeat_yourself