Recursive functions.py

# The first recursive function we saw. 
# Turns out it has the closed formula f(n) = n(n+2) although we didn't prove it. 

def f(n): 
    if n == 0: return 0
    else: return f(n-1) + 2*n + 1
    
# AKA the factorial function: 

def g(n): 
    if n == 0: return 1
    else: 
        return n * g(n-1)
        
# This one produces the Fibonacci numbers
# It has a closed formula but it's complicated: http://mathonline.wikidot.com/a-closed-form-of-the-fibonacci-sequence 

def F(n):
    if (n==0 or n==1): return 1
    else: 
        return F(n-1) + F(n-2)