# Recursive way of computing a sum
def rec_sum(nb : int) -> int:
    if nb == 0: return 0
    else: return nb + rec_sum(nb - 1)

"""
RECURSIVE CALL TREE

  15  rec_sum(5) -> rec_sum(4) -> rec_sum(3) -> rec_sum(2) -> rec_sum(1) -> rec_sum(0)
  |                                                                            |
  -  15 <- 10 + 5   10 <- 6 + 4   6 <- 3 + 3    3 <- 1 + 2    1 <- 0 + 1   0 <-
"""

# Iterative way to compute a sum
# Best way as it's wayyyyyy more CPU eficient 
# Try launching them both with perf_counter_ns()
def sum_it(nb : int) -> int:
    result = 0
    for i in range(nb + 1):
        result += i
    return result

import time

def factorial(nb : int) -> int:
       if nb <= 1: return 1
       else: return nb * factorial(nb - 1)


"""
RECURSIVE CALL TREE

  120  factorial(5) -> factorial(4) -> factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)
  |                                                                                          |                                                             |
  -   120 <- 24 × 5     24 <- 6 × 4     6 <- 2 × 3      2 <- 1 × 2      1 <- 1 × 1        0 <-
"""

def facto_it(nb : int) -> int:
    # 1 instead of 0 as
    # 1 is the neutral of multiplication
    result = 1
    for i in range(nb + 1):
        result *= i
    return result

start_time = time.perf_counter_ns()
facto_it(100)
end_time = time.perf_counter_ns()
elapsed_time = end_time - start_time
print(f"Elapsed time: {elapsed_time} nanoseconds")
# 7444ns
start_time = time.perf_counter_ns()
factorial(100)
end_time = time.perf_counter_ns()
elapsed_time = end_time - start_time
print(f"Elapsed time: {elapsed_time} nanoseconds")
# 20112ns

def power(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    else:
        return x * power(x - 1, n)
    
# The tree is n size, for n calls

def powerMonster(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    else:
        if n % 2 == 0:
            return x * powerMonster(x, (n-1)//2) * powerMonster(x, (n-1)//2)
        else:
            return powerMonster(x, (n-1)//2) * powerMonster(x, (n-1)//2)

# sqrt size here


def powerMonsterButBetter(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    else:
        if n % 2 == 0:
            return x * powerMonsterButBetter(powerMonster(x, 2), (n-1)//2)
        else:
            return powerMonsterButBetter(powerMonster(x, 2), n//2)

di = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}

def rom_to_dec(text : str) -> int:
    if len(text) == 1:
        return di[text]
    else:
        if di[text[0]] >= di[text[1]]:
            return rom_to_dec(text[1:]) + di[text[0]]
        else:
            return rom_to_dec(text[1:]) - di[text[0]]

assert rom_to_dec("CXLII") == 142
assert rom_to_dec("CDIII") == 403

import turtle
from random import randint

turtle.pendown()
turtle.left(90)
turtle.speed(0)
turtle.colormode(255)

def ytree(size,n):
    turtle.pencolor(0, 255//n, 0)
    turtle.forward(size)
    if n > 1:
        turtle.left(30)
        ytree(0.8*size,n-1)
        turtle.right(60)
        ytree(0.8*size,n-1)
        turtle.left(30)
    turtle.pencolor(0, 255//n, 0)
    turtle.backward(size)

def go() -> bool:
    if randint(1, 5) == 1:
        return False
    return True

def ygotree(size,n):
    turtle.pencolor(0, 255//n, 0)
    turtle.forward(size)
    if n > 1 and go():
        turtle.left(30)
        ygotree(0.8*size,n-1)
        turtle.right(60)
        ygotree(0.8*size,n-1)
        turtle.left(30)
    turtle.pencolor(0, 255//n, 0)
    turtle.backward(size)

ygotree(80, 7)

ts = turtle.getscreen()
ts.getcanvas().postscript(file="duck.eps")