Mitch's Technical Blog

A Simple Recursive Proof

July 30, 2018
algorithms, notes, python
permalink

Implementing this example strengthened my grasp of recursion and proof by induction.

In the unlikely event you're a computer scientist or mathematician reading this, I apologize for any lapses in rigor (and welcome any gentle corrections).

def get_stamps(n):
    """
    Suppose you have an unlimited supply of 5 cent and 8 cent stamps.
    This algorithm demonstrates by recursion that any postage
    amount of 28 cents or greater is possible, in 1 cent increments.

    Having a total of 8 basis cases (instead of 5) should ensure
    the smallest quantity of stamps (i.e. using as many 8 cent stamps
    as possible) but that is not proved formally here.

    Whether you'll have enough space on the package to apply the stamps,
    I can't say.

    Using 8 basis cases and +8 should ensure the stamp sequence is
    automatically sorted.

    This implementation is adapted from Jeff Erickson's excellent material:

    Algorithms: Appendix I, Proof by Induction, page 8
    http://jeffe.cs.illinois.edu/teaching/algorithms/notes/98-induction.pdf

    Note: Requires python3 (because of .split(sep='+'))

    >>> result = get_stamps(28)
    >>> assert(result == '5+5+5+5+8')
    >>> result_list = result.split('+')
    >>> assert sum([int(r) for r in result_list]) == 28
    >>> result = get_stamps(42)
    >>> assert(result == '5+5+8+8+8+8')
    >>> result_list = result.split('+')
    >>> assert sum([int(r) for r in result_list]) == 42
    >>> result = get_stamps(100)
    >>> assert(result == '5+5+5+5+8+8+8+8+8+8+8+8+8+8')
    >>> result_list = result.split('+')
    >>> assert sum([int(r) for r in result_list]) == 100

    """

    # Populate the basis cases
    assert(n >= 28)

    if n == 28:
        return '5+5+5+5+8'
    elif n == 29:
        return '5+8+8+8'
    elif n == 30:
        return '5+5+5+5+5+5'
    elif n == 31:
        return '5+5+5+8+8'
    elif n == 32:
        return '8+8+8+8'
    elif n == 33:
        return '5+5+5+5+5+8'
    elif n == 34:
        return '5+5+8+8+8'
    elif n == 35:
        return '5+5+5+5+5+5+5'
    else:
        # By definition, we can recursively step down in decrements
        # of 8 and eventually land on one of the base cases
        # Each step "down" means that we must add 8 in order to
        # arrive eventually at the passed in value of n
        return get_stamps(n-8) + '+8'


if __name__ == '__main__':
    from doctest import testmod
    testmod(verbose=True)


Contact: hello at escapefromsql.net