Recursion Examples

Recursion
Recursion
Publish Date:   2022-02-23

Time complexity and space complexity of recursive algorithms. Usually computed by Master Theorem or Induction.

Examples of Recursion

Quick Sort

Commonly used (than merge sort) in practice. Because it’s more efficient in space usage.

Time complexity:

  • Best case: T(n) = 2*T(n/2) + O(n) = O(nlogn)
  • Worst case: T(n) = T(n-1) + T(1) + O(n) = O(n^2)

Space complexity:

  • Best/average: O(logn)
  • Worst: O(n)
import math
 
def partition(arr, l, r):
    i = l - 1
    pivot = arr[r]
    for j in range(l,r):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[r] = arr[r], arr[i+1]
    return (i+1)

def quickSort(arr, l, r):
    if l < r:
        pi = partition(arr, l, r)
        quickSort(arr, l, pi-1)
        quickSort(arr, pi+1, r)

Merge Sort

Time complexity: T(n) = 2*T(n/2) + O(n) = O(nlogn). Space complexity O(logn + n).

import math

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    L = [0] * (n1)
    R = [0] * (n2)

    for i in range(0, n1):
        L[i] = arr[l+i]

    for j in range(0, n2):
        R[j] = arr[m+1+j]

    i = 0
    j = 0
    k = l
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
        
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
        
def mergeSort(arr, l, r):
    if l < r:
        m = l + (r-l) //2
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)
    return arr

Time complexity: T(n) = T(n/2) + O(1) = O(logn)

Space complexity: O(logn)

def binary_search(l, r): # [l,r)
    while l < r:
        m = l + (r - l) // 2
        if f(m):
            return m 
        if g(m):
              r = m # new range [l, m)
        else:
            l = m + 1 # new range [m+1, r)
    return l

Inorder Traversal

Time complexity:

  • Best case: T(n) = 2 * T(n/2) + O(1) = O(n)
  • Worst case: T(n) = T(n-1) + T(1) + O(1) = O(n)

Space complexity

  • Best case: O(logn)
  • Worst case: O(n)
def inorder(root):
  inorder(root.left)
  print(root.val)
  inorder(root.right)

Combination

Time complexity: T(n) = T(n-1) + T(n-2) + … + T(1) = O(2^n).

Space complexity: O(n).

Permutation

Time complexity: T(n) = n * T(n-1) = O(n!).

Space complexity: O(n).

def permutation(arr):
    if len(arr) == 1: return arr
    out = []
    
    for i, letter in enumerate(arr):
        for perm in permutation(arr[:i] + arr[i+1:]):
            out += [letter + perm]
    return out

print(permutation(['1','2','3','4']))

Recursion with Memoization

Time complexity: T(n) = O(2^n) = O(1.618^n)

# recursive
def fibonacci(num):
    if num == 0 or num == 1: 
        return num
    return fibonacci(num - 1) + fibonacci(num - 2)

Time complexity: T(n) = O(n)

# recursive with memoization
def Fibonacci(n):
    memoize = [-1 for _ in range(n+1)]
    return recursion(memoize, n)

def recursion(memoize, n):
    if n < 2:
        return n
    if memoize[n] >= 0: 
        return memoize[n]
    memoize[n] = recursion(memoize, n-1) + recursion(memoize, n-2)
    return memoize[n]
Recursion
  TOC