#!/usr/bin/python
import os
import sys

# Error codes
ERR_BAD_ARGS = 1

def fib_rec(n):
    class RecursiveFib(object):
        def __init__(self):
            self.call_count = 0

        def inner_fib_rec(self, n):
            """
            Compute the nth Fibonacci number, recursively.
            """
            self.call_count += 1
            non_neg_err_str = "fib_rec() takes only integer arguments >= 1"
            if n < 1:
                raise ValueError(non_neg_err_str);
            try:
                n = int(n)
            except:
                raise ValueError(non_neg_err_str);

            if (n==1) or (n==2):
                return 1
            else:
                return self.inner_fib_rec(n-1) + self.inner_fib_rec(n-2)

    recursive_fib = RecursiveFib()
    result = recursive_fib.inner_fib_rec(n)
    print "Recursive Fibonacci(%s) made %s function calls" % (n, recursive_fib.call_count)
    return result

def fib_iter(n):
    """
    Compute the nth Fibonacci number, iteratively.
    """
    if (n==1) or (n==2):
        return 1

    fib_n_minus_1 = 1
    fib_n_minus_2 = 1
    fib_n = 2
    for i in xrange(3,n+1):
        fib_n = fib_n_minus_1 + fib_n_minus_2
        fib_n_minus_2 = fib_n_minus_1
        fib_n_minus_1 = fib_n
    return fib_n

def main():
    if len(sys.argv) < 2:
        usage_and_quit()

    n = sys.argv[1]

    try:
        n = int(n)
    except:
        usage_and_quit()

    #sys.stdout.write("%s\n" % fib_iter(n))
    for i in xrange(1,n+1):
        fib_rec(i)

def usage_and_quit():
    usage(sys.argv[0])
    sys.exit(ERR_BAD_ARGS)

def usage(prog_name):
    short_name = os.path.basename(prog_name)
    sys.stderr.write("%s [n]\n")
    sys.stderr.write("prints nth Fibonacci number, computed two ways\n")

if __name__ == '__main__':
    main()