def cfR(n):
    print(f'Computing the factoral of {n}')
    if n == 0:
        print('returning 1')
        return 1
    else:
        temp = n * cfR(n-1)
        print(f'returning {temp}')
        return temp

##
##num = 4
##answer = cfR(num)
##
##print(f'factorial of {num} is {answer}')

def move_one_disc(p1, p2):
    print('Move the disc from peg', p1, 'to peg', p2)
    
def move_tower(num_discs, start, end, intermed):    
    if num_discs == 1:
        move_one_disc(start, end)
    else:
        move_tower(num_discs - 1, start, intermed, end)
        move_one_disc(start, end)
        move_tower(num_discs - 1, intermed, end, start)

##move_tower(4, 'A', 'C', 'B')


def fib(n):
    # we assume n >= 0
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

idx = 40
answer = fib(idx)
print(f'The {idx}th fibonacci number is {answer}')

fibnums = [None]*100

def fib_memo(n):
    if fibnums[n] != None:
        return fibnums[n]
    
    # we assume n >= 0
    if n == 0:
        fibnums[n] = 0
        return fibnums[n]
    elif n == 1:
        fibnums[n] = 1
        return fibnums[n]
    else:
        fibnums[n] = fib_memo(n-1) + fib_memo(n-2)
        return fibnums[n]

idx = 40
answer = fib_memo(idx)
print(f'The {idx}th fibonacci number is {answer}')