Recursion #

Recursive tracing #

m(648)
    m(72)
        m(9)
        return 9

My trace

m(348)
    a = m(34)
        a = m(3)
            return 33
        a = 33
        b = m(4)
            return 44
        b = 44
        return 3344
    a = 3344
    b = m(8)
        return 88
    b = 88
    return 334488

pow example #

My solution

pow(b, e):
    if e == 0:
        return 1
    return b * pow(b, e - 1)

Trace

pow(3, 4)
    3 * pow(3, 3)
        3 * pow(3, 2)
            3 * pow(3, 1)
                3 * pow(3, 0)
                    return 1
                3 * 1
                return 3
            3 * 3
            return 9
        3 * 9
        return 27
    3 * 27
    return 81
81

The runtime of this is \( T(n) = T(n - 1) + 1 \) , so this is \( \Theta (n) \) .

The runtime of the optimized verion is \[\begin{aligned} T(2n) &= T(n) + 1 \\ T(2n + 1) &= T(2n) + 1 \end{aligned}\] which results in a runtime complexity of \( \Theta (\lg n) \)

pow(m, n):
    if n == 0
        return 1
    else if n % 2 == 0
        tmp = pow(m, n/2)
        return tmp * tmp
    else
        return m * pow(m, n - 1)

printBinary example #

def print_binary(n):

    def _print_binary(n, out):
        if n == 0:
            print(out)
            return
        elif n % 2 == 0:
            out = "0" + out
        else:
            out = "1" + out
        _print_binary(n // 2, out)

    _print_binary(n, "")


if __name__ == '__main__':
    print_binary(42)

101010

isPalindrome exercise #

def isPalindrome(s):
    if len(s) == 0 or len(s) == 1:
        return True
    elif s[0] == s[-1]:
        return isPalindrome(s[1:-1])
    else:
        return False

if __name__ == '__main__':
    print(isPalindrome("madam"))
    print(isPalindrome("racecar"))
    print(isPalindrome("step on no pets"))
    print(isPalindrome("able was I ere I saw elba"))
    print(isPalindrome("Java"))
    print(isPalindrome("rotater"))
    print(isPalindrome("byebye"))

True
True
True
True
False
False
False

Public/private pairs #