Recursion Algorithm

recursion.py

## Binary Search
def binary_search(data, target, low, high):
  """
    Return True if target is found in indicated portion of a data list.
    The earch only considers the portion from data[low] to data[high] inclusive.
  """
  if low > high:
    return False  # interval is empty; no match
  else:
    mid = (low+high)//2
    if target == data[mid]:
      return True   # found a match
    elif target < data[mid]:
      # recur on the portion left of the middle
      return binary_search(data, target, low, mid-1)
    else:
      # recur on the portion right of the middle
      return binary_search(data, target, mid+1, high)
      
def binary_search_iterative(data, target):
  """Return True if target is found in the given data list."""
  low = 0
  high = len(data)-1
  while low <= high:
    mid = (low+high)//2
    if target == data[mid]:
      return True
    elif target < data[mid]:
      high = mid -1 
    else:
      low = mid + 1
  return False
      
      
# Linear Recursion
def linear_sum(S, n):
  """ Return the sum of the first n numbers of sequence S."""
  if n==0:
    return 0
  else:
    return linear_sum(S, n-1) + S[n-1]
    
    
# Binary Recursion
def binary_sum(S, start, stop):
  """Return the sum of the numbers in implicit slice S[start:stop]."""
  if start >= stop: # zero elements in slice
    return 0
  elif start == stop-1: # only one element in slice
    return S[start]
  else:
    mid = (start+stop)//2
    return binary_sum(S, start, mid) + binary_sum(S, mid, stop)
   
   
   
# Towers of Hanoi
def Hanoi(o, t, d, n):
  """
    o, original disks in peg o
    t, temporary storage peg
    d, target peg
    n, the disks level number
  """
  if n <= 0:
    print("All moves finished")
  if n == 1:
    print("move", n, "from", o, "to", d)
  else:
    Hanoi(o, d, t, n-1)
    print("move", n, "from", o, "to", d)
    Hanoi(t, o, d, n-1)