## Sometimes very simple examples of recursion are used to introduce students
# to recursive thinking for the first time.  Unfortunately, these examples
# are usually bad examples of recursion.  Recursion really only make sense
# under certain circumstances.  Don't use it to replace loops, use it when
# loops along can't do the job.


# second worst example of recursion ever made:
import sys


# function to calculate n!
def fact(n):
    if (n<2): return 1
    else: return n*fact(n-1)
#
# 0! = 1
# for n>0:  n! = n*(n-1)!

#print(fact(4))
#print(fact(5))
#print(fact(6))

sys.setrecursionlimit(2000)  # YOU SHOULD NOT DO THIS (in general)

#print(fact(1000))  # will overflow call stack

"""  nothing wrong with a loop, even if it's harder to formally prove correct..
ax = 1
for i in range(2,n):
    ax *=i
"""

### The absolute worst example of recursion ever!
# 1 1 2 3 5 8 13 21
# fib(1) = fib(2) = 1
# fib(n) = fib(n-1) + fib(n-2)

def fib(n):
    if n<3: return 1
    else: return fib(n-1) + fib(n-2)
#
"""
for i in range(1,100):
    print fib(i)
    sys.stdout.flush() # force immedidate print
"""

n = int(sys.argv[1])
print(fib(n)) #How long does fib(100) take to return? Stay up late and wait...