Recursion

Recursion#

Introduction#

Recussion generally follows Divide-Conquer algorithm:

  • Divide the problem into a number of subproblems that are smaller instances of the same problem.

  • Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.

  • Combine the solutions to the subproblems into the solution for the original problem

Some Cases#

Maximum/Minimum#

def maximum_recursion(A, i):
    if i < 1: 
        return A[0]
    else:
        return max(maximum_recursion(A, i-1),A[i])

A = [2,4,5,9,1]
print(maximum_recursion(A,len(A)-1))

A = [1, 1, 1, 1]
print(maximum_recursion(A,len(A)-1))

9
1

def reverse(s):
    """Return a string in reverse order"""
    res = ''
    n = len(s)

    if n <= 1: # base case
        res = s
    else:
        r = reverse(s[:n-1])
        res = s[n-1]+r
    return res

print(reverse("hello world"))

dlrow olleh

Fibonacci Number#

# using recurrence - duplicately recalculate f(n-2) - bad recurrence using binary recursion - O(2^n)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))

55

# using recurrence - good recurrence using linear recursion - O(n)
def fibonacci(n):
    if n <= 1:
        return (n, 0)
    else:
        (a, b) = fibonacci(n-1)
        return (a+b, a)

print(fibonacci(100))

(354224848179261915075, 218922995834555169026)

# using memoized recurrence - top-down dynamic programming O(n)
def fibonacci(n, r = {}):
    if n in r:
        return r[n]
    elif n <= 1:
        r[n] = n
    else:
        r[n] = fibonacci(n-1, r) + fibonacci(n-2, r)

    return r[n]

print(fibonacci(100))

354224848179261915075

# using bottom-up dynamic programming O(n)
def fibonacci(n):
    r = [0.]*(n+1)
    for j in range(n+1):
        if j <= 1:
            r[j] = j
        else:
            r[j] = r[j-1] + r[j-2]
    return r[n]

print(fibonacci(100))

354224848179261915075
Contents